Упрощение задачи

Подход, принятый в этой работе должен упростить проблему, по существу в проблему поиска во взвешенном графе. Многие из основных идей, если возможно не подробнocти, были вдохновлены работой, предстваленной в [STEF95], и несколькими ранними работами.

5.1.1 Ограничение пространства поиска

Первый шаг в нашем упрощении ограничение числа возможных размещений и числа возможных перемещений между этими размещениями.

5.1.1.1 Ограничение области поиска

Область поверхности, где наше транспортное средство может перемещаться фактически бесконечно во всех направлениях. Ясно, что мы должны ограничить себя несколько меньшей областью, чтобы выполнить поиск пути на компьютере. Кроме того, мы хотели бы, чтобы эта область была как можно меньше без того, чтобы подвергать сомнению оптимальность пути. И потому что мы хотим уменьшить использование памяти, и потому что это будет иметь положительный эффект связанный с уменьшением числа возможных путей, которые мы потенциально будем должны исследовать при поиске оптимального.

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

При таком подходе может даже оказаться, что не имеется никакого возможного пути, но это неизвестно, пока мы фактически не пробовали, и не сумели найти этот путь. Таким образом, необходимо прибегнуть к использованию некоторой эвристики, чтобы определить подходящий размер области. Это знание применительно к заданому приложению будет очень полезно иметь. Например, протяженность самого большого препятствия, которое мы ожидаем, которое мы будем хотеть обойти вокруг, могла бы быть хорошой исходной точкой для руководства к действию. Плюс расстояние между источником и адресатом. Практические тесты показали, что в небольших областях, первое из этих двух рассмотреных расстояний является намного более важным, в то время как при больших масштабах второе доминирует. Простая эвристика для компромисса может быть создана как b=a+(1+c)*d. Где b - длина диагонали ограничивающего прямоугольника ( от источника и до адресата), d - расстояние между источником и адресатом, c - константа масштабирования ( в большинстве случаев c=1/3, кажется, работает хорошо). В заключение, a - приблизительный размер самого большого препятствия.

В некоторых приложениях, можно взамен дать возможность конечному пользователю, вручную определить область поиска и таким образом уходить от проблемы полностью (насколько мы заинтересованы). И последние замечание, всегда возможно увеличить область поиска и повторить поиск пути в случае, если мы не преуспели в нахождение пути в выбранной области поиска. 5.1.1.2 Разделение пространства на ячейки

Выберем (дискретизируем) бесконечное число позиций в непрерывным пространстве на конечное число точек. Чтобы облегчить представление, при дискретизации наиболее удобно назначать эти точки в регулярной сетке. Область пространства называемая ячейкой, закрывает каждую точку.

Рисунок 3 - Регулярная квадратная плоская сетка

Рисунок 4 - Регулярная гексоганальная плоская сетка

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

Как упомянуто в 3.1 мы сведем нашу проблему к задаче взвешенного графа. Теперь мы определим вершины графа, как 'центральные точки' ячеек.

5.1.1.3 Ограничение перемещений на гранях

Следующий шаг должен ограничить число возможных перемещений из данной ячейки. Если возможно идти от одной вершины до другой без того, чтобы пройти через другую точку вершины, мы будем говорить, что они соединены (направленной) гранью. Вершина, из которой грань идет, называется источником. Вершина на другом конец называется адресатом. Тривиально, всегда имеется грань от заданной ячейки до самой себя; мы будем пренебрегать этим случаем в дальнейшем как пребывание в одной точке - не очень полезный сегмент 'оптимального пути'. Ячейки или вершины, которые являются адресатами всех граней данной ячейки, называются соседями. Какие ячейки рассматривать как соседей данной ячейки, надо решить. Идеально, все ячейки должны быть соседями всех других ячеек (так называемый 'полный' граф). Однако, это означало бы наличие невероятного числа граней. Поскольку для каждой ячейки требовалось бы, определить так много граней сколько имеется других ячеек, мы например получили бы 10¹²/2 граней для графа с одним миллионом ячеек.

Рисунок 5 - ячейка с гранями к восеми соседям

Резюме: мы ограничили число перемещений от каждой вершины до восьми граней (или меньшего количества) и закончили определение представления направленного графа в пространстве.

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

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

5.1.2