Пределы ошибок

Каковы ошибки, свойственные нашему представлению? Позвольте нам рассмотреть различные возможные источники ошибок:

Ошибка Растеризации: Какая ошибка действительно представлена в растровом формате? Это - не тривиальный вопрос.

Рисунок 10 - Зигзагообразный путь между двумя вершинами

Пускай все другое пространство содержит непроходимую местность и используют сетку растеризации такую, что путь содержится в двух соседних ячейках. Если процесс растеризации имеет усредняющий характер, тонкий зигзагообразный путь исчезнет полностью из нашего представления, и мы могли бы неправильно вести себя полагая, что не имеется никакого возможного пути. Если, с другой стороны, мы используем процесс растеризации, который выбирает значение ¥ локальной стоимости, представляемой каждым пикселом. Затем любой пиксел, содержащий зигзагообразную линию получил бы издержки местности, равные такому перемещению вдоль длины зигзагообразного пути. Разница между полученной самой лучшей стоимостью пути (прямая линия между центрами ячеек) и фактической (зигзагообразная линия) таким образом пропорционально разнице расстояний между ними. Однако, это разница может быть большей, когда путь более тонкий и с большим количеством зигзагов. Два случая, представленные здесь - конечно очень маловероятные экстремумы. В дальнейшем, мы просто примем, что растровые пикселы достаточно маленькие, чтобы учесть все существенные характеристики местности. Кроме того, принимается, что они классифицированы таким способом, при котором средняя ошибка в решении становится незначительной. Кроме того, принимается, что, в статистическом смысле, математическое ожидание суммы (знаковых) средних ошибок множества произвольных путей равно нулю.

Ошибки в данных: различные входные данные могут иметь неустранимые погрешности. Это должно быть обработано вне нашей модели, и мы примем, что все наши входные данные будут точными. Однако, мы можем обратить внимание, что полученный путь - конечная сумма издержек граней. Если функция стоимости грани - кусочная линейная функция входных данных (то есть она позволяет только ограниченные 'переходы') то она тоже дает ошибку.

Ошибка дискретизации ячейки: Какова величина ошибки вытекающая из ограничения перемещения по пути между ячейками только через вершины? Давайте рассмотрим частный случай однородной стоимости перемещения. Начальная и конечная точка должны каждая относиться к ячейке. Перемещение по 'позициям' ограничено вершинами в центрах ячейки, см. рисунок 11. Следовательно, мы имеем абсолютный верхний предел для ошибки как максимум расстояний между всеми возможными позициями внутри ячейки и центр. Ясно, что это половина длины диагонали. Следовательно, предел в ошибки дискретизации ячейки - длина диагонали одной ячейки. Для более сложного случая с переменной стоимостью перемещения, мы можем умножать на самую высокую стоимость перемещения вдоль граней пути для опытной (а-постеори) верхней границы. Мы затем должны знать оптимальный путь, чтобы найти самую высокую стоимость по нему. Мы могли бы использовать самую высокую стоимость на всем графе взамен для априорной оценки, но если мы имеем препятствия, то она - ¥, которая не делает очень полезной оценки.

Истинный и ограничивающий путь

Рисунок 11 - ошибка дискретизации ячейки ограниченна диагональной длиной

Ошибка ограничения грани: Какая величина ошибки получается, когда мы ограничиваем перемещение между ячейками только к соседним ячейкам? Снова при рассмотрении однородного случая стоимости перемещения получаемая ошибка иллюстрируется рисунком 12 (обратите внимание, что ограниченный путь может быть разрешен без того, чтобы изменить стоимость, см.

Рисунок 12 - ошибка ограничения грани в однородной местности

В самом плохом случае - очевидно, когда общая длина диагональных граней равняется общей длине осевых граней. Поскольку соотношение между длиной диагонали и осевой грани - O2, то есть иррациональное число, то самый плохой случай может происходит в 'пределе' бесконечно длинного пути. Если истинный путь имеет длину l_t, и наш ограниченный путь имеет длину l_r, мы получаем из простой геометрии:

Другими словами, мы имеем верхний предел ошибки приблизительно 8 %, для однородного графа. Для неравномерных графов, мы можем получить опытную ошибку, при помощи умножения на общую стоимость вычисленного пути.

Ошибки функции стоимости: модель реального мира базируется на ряде попыток определения величины различных свойств мира. Неправильная модель порождает ошибки. Попытки точно измерить эти ошибки очень трудны из-за запутанного характера мира. Здесь не сделано никаких попыток, так как это очень зависит от множества 'нюансов'. Подобно детальной спецификаций транспортных средств, классификации типов местности, и так далее и тому подобное. Возможно единственый действительно удовлетворительный способ измерения этих ошибок, фактически выполнить тесты и сравнить их с вычисленными результатами.

В заключение, отметим, что трудно говорить о абсолютном пределе погрешности (особенно априорной границы). С другой стороны мы имеем причины верить, что сделанные аппроксимации обладают малыми 'усреднеными' ошибками. Так как аппроксимации, носят по большей части 'усредненный' характер, то устойчивость также стабильна.

5.2