Определение оптимального пути в Евклидовом трехмерном пространстве

5. Алгоритмы поиска

Мы свели нашу проблему в более общую проблему нахождения минимального по стоимости пути во взвешенном, направленном графе. Это иногда упоминается как проблема 'самого короткого пути' вместо 'минимальной стоимости', см. [CORM90] и [CHER93]. Существуют методы решения таких проблем, и несколько подходов кратко представлены в кратком обзоре 4.1. Проблема состоит в том, что большинство методов или имеет очень плохое быстродействие для больших или более сложных графов, или только производит приблизительные решения с более или менее уверенностью. Практический алгоритм для нашей задачи затем исследован более подробно.

Существует ряд методов решения графа связанных с задачей минимизации. Здесь, применимость для представленной задачи исследована для некоторых наиболее общих подходов.

При данном подходе должен выполняться полный перебор, перечисляя все возможные пути и выбирая путь(и) с самой низкой стоимостью. Любой метод, используемый, чтобы создать эти пути может быть иллюстрирован деревом решений. Мы могли бы например выполнять полный перебор, используя алгоритм 'поиска в глубину', см. [CORM90] стр. 477.. 483. Кратко: начнем 'трассировку' пути решения с листа в дереве решений, производящем первый путь. Затем мы создадим указатель возврата на первую точку решения, где мы еще не исследовали все возможные 'решения' и наченм новый перебор по дереву для нового пути. Чтобы ограничивать число путей для перебора, мы можем непосредственно отбрасывать любые пути, которые имели бы 'циклы'. Продолжайте по этому способу, пока все дерево пройдено. Другими словами, начните в исходной вершине, перейдите по граням к другим вершинам (которые еще не прошли), и повторяйте, пока вершина адресата не достигнута.

В каждой точке решения, мы имеем выбор из восьми направлений. Назовем число вершин N. Поскольку любая ячейка может быть посещена больше, чем один раз (иначе имелся бы цикл), мы можем устанавливать, что каждый возможный путь имеет в большинстве случаев N-1 граней, то есть дерево поиска имеет глубину O(N). Так как число ветвей восемь на каждом уровне, мы получаем в большинстве 8^{N -1} возможных путей, то есть мы имеем O(8^N) путей, чтобы исследовать в самом плохом случае. Таким образом, этот подход берет экспоненциальное время, чтобы найти решение. Это ясно не очень хорошо. Алгоритм очень плохой так как не различает между огромным большинством возможных путей, которые, вряд ли, будут оптимальны и те очень немногие, которые являются вероятными кандидатами.

Альтернатива алгоритму 'в глубину' для выполнения полного перебора так называемый алгоритм поиска 'ширина вначале', см. [CORM90], стр. 469.. 477. Он получил название по способу, которым он расширяет 'фронт поиска' из точки начала (в решающем дереве). Этот вариант не дает больших преймуществ по сравнению с предыдущим методом. Однако, здесь есть основной класс алгоритмов поиска на графе, основанный на методике так называемой 'релаксацией', см. [CORM90], при котором используют идеи, очень схожие с алгоритмом поиска в ширину, но с некоторыми определяющими уточнениями. Наиболее общие из них, применимы для текущей задачи, классические: алгоритмы Дийкстры и Беллмана-Форда. Они оба определяют все оптимальные пути из 'одиночного источника' к всякой другой вершине. Алгоритм Дийкстры быстрее, но необходимо, чтобы не было никаких отрицательных издержек грани; которые мы имеем, как удостоверелись в разделе три. A* алгоритм эффективное эвристическое уточнение алгоритма Дийкстры, который имеет лучшую среднюю эффективность, когда надо найти оптимальный путь между двумя вершинами (и не от одной вершины до всех других). Потому что он обеспечивает хорошое, предсказуемое быстродействие без того, чтобы подвергать сомнению, этот алгоритм, выбран для нашей реализации теста; см. раздел 4.2.

Линейное программирование часто используется, чтобы решить задачи связанные с различными сетевыми потоками и проблемы распределения ресурсов. Возможно рассмотреть нашу задачу как задачу линейного программирования, сводя ее, например, к задаче потока минимальной стоимости или эквивалентной задаче. Для ссылок см. [LUEN84] и [CSEP95]. На практике, задача становится очень 'огромной', и таким образом обычные методы оптимизации, используемые для таких проблем кажется, не очень эффективными для так больших проблем. Например, так называемый симплексный метод - классический книжный метод для решения задачи линейного программирования. Однако, установление сходимости для симплексного метода нетривиально и время поиска, не может быть установлено априорно. Кроме того, и как ожидается, итеративная матрица (см. [LUEN84], становится, очень разреженной, и огромной (квадрат числа ячеек). По этим причинам этот подход не рассмотрен здесь, хотя при наличии большого обьема памяти и быстродействующего процессора задача разрешима.

Этот общий метод минимизации может быть очень полезен для приблизительного решения многих 'трудных' проблем минимизации, используя псевдослучайный поиск. Например NPC проблема известная как 'путешествующий продавец' может быть действительно 'решена', используя моделирование обжига, см. [PRES92]. Метод находит вдохновение в способе, которым характер непосредственно достигает minimas. Имя исходит из процесса, где горячему металлу медленно позволяют охлаждать и заморозиться в минимальную энергетическую кристаллическую конфигурацию решетки.

Функция, f - для минимизации называется целевой функцией. В нашем случае, f - стоимость пути. Метод начинается с начальным 'предполагаемым' решением. Например, мы могли бы использовать 'прямую линию' пути между источником, и адресатом (это может быть и не допустимый путь). Затем решение итерационно улучшено, применяя произвольные возмущения в пути. Возмущаемый путь принят как новое начальное решение с вероятностью: . Таким образом, имеется вероятность принятия некоторых возмущений, который фактически увеличивают целевую функцию. Это необходимо, чтобы избежать 'захвата' локальным minimas. Параметр T системы, часто называемый 'температурой', используется, чтобы управлять этой вероятностью и понижается, пока допустимое решение не было найдено. Очень трудно создать хорошую функцию возмущения. Она должно иметь свойство и, введения малых, произвольных, 'возможных' изменений и в то же самое время позволять всем возможным решениям быть достигнутым. Часто T также используется, чтобы непосредственно управлять 'масштабом' возмущений. Точно, как T управляется, и как определить, когда остановиться очень трудно. Некоторая эвристика или адаптивная логика управления часто использована. Как простой пример мы могли бы использовать фиксированный T до, скажем 100 итераций в строке, не сумевших производить лучшее решение. Затем T разделен на два, и мы продолжаем в том же самом режиме. Мы останавливаемся, когда масштаб возмущений (как функция T) достаточно мал, и лежит ниже желательной точности решения. Этим способом, крупномасштабная оптимизация вначале выполняется (большое T, дающие большие возмущения) и затем оптимизация выполняется на непрерывно более низких масштабах, пока в заключение не сделана 'локальная' оптимизация.

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

Для дальнейшей информации относительно моделирования обжига, см. [PRES92] или [CSEP95]

A* алгоритм добавляет эвристику, чтобы улучшить классический алгоритм Дийкстры, который позволяет нам находить наиболее оптимальный путь по стоимости в направленном графе с неотрицательными весами граней.

Дийкстры алгоритм

Этот алгоритм сначала был представлен в [DIJK59]. Более современная интерпретация и доказательство правильности может быть найдено в [CORM90]. Здесь будет дано краткое описание алгоритма вместе с некоторыми замечаниями относительно свойств этого алгоритма, но без доказательств или теоретических выводов.

Дан граф G = (V, E) и исходная вершина sV. Здесь V множество вершин и E множество граней в G. Далее мы имеем функцию веса грани w(u,v) 0 (u,v)E. Алгоритм делит все вершины V, на два непересекающихся множества V = R Q. Множество R, содержит такие вершины, чьи веса в заключительном наиболее коротком пути были определены и множество Q=V-R. Когда вершина перемещается из Q в R, мы говорим, что она 'удаляется'. Некоторые описания алгоритма называют Q 'открытым' множеством и R 'закрытым' множеством. Для каждой вершины v, мы храним оценочное значение минимума для самого короткого пути, g[v]. Поскольку мы заинтересованы вовсе не в нахождении наименьшего значения стоимости пути, а скорее фактического множества вершин, которая составляет этот путь, мы также сохраняем, для каждой вершины грань предшественника, ed[v], которая является гранью исходящей от соседней вершины в текущем самом наилучшем пути от рассматриваемой вершины. Этот массив может затем использоваться, чтобы восстановить путь по указателям возврата от вершины адресата, см. 4.2.3. В случае, если имеется более чем один оптимальный путь, только последний обнаруженный путь будет запомнен согласно этому алгоритму. В разделе 4.2.5 описан, способ чтобы изменить это, дабы 'выбрать' более визуально приятный путь в таких случаях неоднозначности.

The algorithm, in pseudo-code, proceeds as follows:

Алгоритм на псевдокоде:

Dijkstra(G,w,s) - граф, функция стоимости, исходная вершина

R = Q = {} - пока в обоих множествах ничего нет

for all vV do - для всех вершин надо кое-что вычислить

g[v] = - инициализация стоимости пути

Q.Insert(v) - вставим вершину в открытое множество

( здесь должна быть вставка в Q вершины s со стоимостью 0 )

while (Q {}) do - пока есть точки в открытом множестве

u = Q.ExtractMin() - извлечь вершину с минимальной стоимостью - u

R = R {u} - занести в закрытое множество

for vNeighbors{u} do - для всех соседей вершины u

if (g[v] > g[u] + w(u,v)) then - если стоимость соседа v больше,

чем стоимость грани +

стоимость вершины u, то

Q.DecreaseKey(v, g[u] + w(u,v)) - установить стоимость

вершины v

ed[v] = (u,v) - и присвоить указатель возврата с v -> u

Множество Q должно быть выполнено в виде приоритетной очереди со следующими операциями: Q.Insert (u) - вставляет вершину в очередь, Q.ExtractMin () - извлекает и удаляет элемент vQ с самым маленьким g[v], Q.DecreaseKey(v, a) - уменьшает ( присваивает ) g[v] к a, и обновляет очередь.

Алгоритм работает при помощи повторяющегося извлечения вершины vQ с минимальной стоимостью самого короткого пути, g[v]. Поскольку все стоимости граней положительны, мы не сможем найти любой более короткий путь к вершине v, проводя путь от любой другой вершины отличной от u. Таким образом мы определили самый короткий путь до v и можем удалить вершину в R. Мы затем проверим, имеются ли соседи данной вершины относительно данного оптимального пути со стоимостью более низкой, чем текущая стоимость самого короткого пути для данного соседа. Если это так, то мы модифицируем (или 'ослабляем') оценку самого короткого пути и грань предшественника для соседа(ей), соответственно. Поскольку мы неоднократно можем выбирать наименее дорогостоящую вершину, и 'ослаблять' ее, то алгоритм принадлежит классу 'жадных ' релаксационных методов.

Для практической реализации, мы можем разделить Q на два непересекающихся подмножества, U и PQ, где, для того чтобы стартовать, U содержит все вершины за исключением s, и PQ используется вместо Q выше. Вершины затем перемещаются из U в PQ, когда они первый раз были посещены. Мы можем использовать некоторый флаг, для того чтобы обозначать, была ли вершина ранее посещена или нет (то есть если она находится в U) и таким образом не должно сохраняться в U явно. Всегда хранение приоритетной очереди PQ как можно меньшего размера, может быть очень полезно для быстродействия; см. 4.2.5.

Поскольку мы только заинтересованы в самом коротком пути между двумя вершинами, мы будем впустую тратить время, чтобы вычислять все пути от одной вершины до всех других вершин, как это делает алгоритм Дийкстры. Наиболее очевидное уточнение состоит в том чтобы прекратить поиск тогда, когда вершина адресата t, удаляется. Знание о позиции адресата не используется вообще во время поиска, и 'глупо' его не использовать. A* алгоритм, представленный в [NILS82], учитывает это, добавляя эвристику, чтобы перенести направление поиска к адресату и таким образом возможно закончить поиск быстрее. Единственное различие между алгоритмами заключается в каком порядке вершины удаляются на каждом итерационном шаге, то есть каким образом они упорядочиваются в приоритетной очереди. Основная идея состоит в том, что вместо того, чтобы использовать g[v] (фактическая стоимость от источника до текущей вершины) чтобы упорядочить очередь как в алгоритме Дийкстры, новая стоимость, f[v] = g[v] + h[v] используется заместо старой, где h[v] - эвристика. Можно доказать, что, если h[v] является недооценкой (или в большинстве случаев равной) фактической наименьшей стоимости пути для перемещения от v до t, тогда A* производит оптимальное решение (точно так же как в случае Дийкстры). Строгое доказательство выходит за рамки данного документа; смотри в [NILS82]. Как только упорядочение приоритетной очереди изменено, характеристики с самого плохого случая такие же как для Дийкстры, но мы можем ожидать, что средняя эффективность будет намного лучше для графов 'реального мира', если мы сможем создать хорошую эвристику, h[v].

Вообщем, время прохождения 'расстояния от u до v' является 'самой маленькой стоимостью' и будет самой лучшей оценкой, которую мы можем сделать для h[v], когда недооценку от действительной стоимости нужно учесть. Какова оптимальная оценка 'расстояния', зависит от структуры графа. Истинное Евклидово расстояние можно использовать, но оно часто меньше, чем фактическая длина граней по самому короткому пути (см. рисунок 12). Вместо этого, так как структура графа однородна, мы можем фактически вычислить точное, 'оптимальное' расстояние. Если мы только имеем ортогональные грани, это будет так называемое расстояние 'Манхэттанна': |x| + |y|. В нашем случае, с диагональю грани также, это будет выглядеть таким образом: 'диагональная длина края'' * min(|x|,|y|) + 'осевая длина края' * ||x|-|y||. Это очень хорошо посравнению с использованием Евклидова расстояния так как не требуется вычисление квадратного корня.

Мы можем придержать вычисление h[v] для каждой вершины, до тех пор пока это не станет фактически необходимым, то есть когда она первый раз попадет в очередь поиска. Таким образом, тот же самый флаг какой используется для слежения за тем, если вершина находится в U (см. 4.2.1) также будет указывать на то, надо ли h[v] инициализировать. Поскольку большинство вершин никогда не будет посещено вообще, это поможет сохранить нам немного времени.

Обратите внимание, что, если стоимости граней местности без препятствий меняются в больших пределах (например, дороги очень мало стоят, в то же время как равниные типы местности дорого стоят), тогда добавляя эвристику, базирующуюся на 'самой маленькой стоимости местности' вообще-то обеспечивается наибольшая недооценка. В этих случаях A* - незначительной уточнение и будет вести себя подобно алгоритму Дийкстры. Альтернативой было бы использование 'типичной стоимости местности' вместо самой маленькой стоимости. Это нарушило бы утверждение что эвристика недооценивает реальную стоимость и таким образом ставит под угрозу гарантию оптимальности. В некоторых приложениях, такой способ может быть дать более быстрые решения. Фактически, мы могли бы использовать f[v] = g[v] + c*h[v], где c - 'управляющая' константа масштабирования. При c=0 мы имеем алгоритм Дийкстры, при c=1 мы имеем A*, при c>1, мы имеем модифицируемый 'приблизительный A*'. При больших значениях c решение находится быстрее (в среднем), но при этом оно более 'направлено на адресат'. Хорошую интерактивную обучающую программу на Java, которая иллюстрирует данное свойство, можно найти в [WAVE96]. При равной стоимости местности, эвристика h=0 дает для нашего специального графа фронт поиска, который расширяется в форме шестиугольника, в то время как A* с истинной Евклидовой эвристикой дает более груше-подобную форму.

Пример совершенно иного применения A* может быть найдено в [SONK93].

Результат типичного поиска проиллюстрирован на рисунке 14. Круг обозначает адресат пути. Серые ячейки, те которые никогда не будут посещены в процессе поиска по алгоритму. Темно-серым обозначено препятствие. Стрелки указывают на те грани которые характеризуют 'на данный момент лучший из всех известных' путей по всем исследованным ячейкам, то есть значения ed[v] для вершин указаны острием стрелок. Для удаленных ячеек (не маркированы) данный путь будет оптимален до этих ячеек. Более толстые темные стрелки указывают наиболее дешевый путь к адресату.

Рисунок 14 - маленькая часть дерева A* поиска

Если нас интересовало только нахождение стоимости минимального пути, тогда мы могли бы пропустить сохранение значений ed[v] ( и таким образом сохранили бы по байту с каждого узла). Теперь можно легко использовать указатели возврата ed[v] от вершины адресата для нахождения оптимального пути. Мы начинаем с ячейки адресата и затем идем в противоположном направлении по отношению к направлению грани, сохраненной в текущей ячейке, это продолжается до тех пор пока мы не достигаем исходной ячейки. С помощью данного перебора просто обратить последовательность ячеек, посещенных в течение трассировки указателей возврата, для того чтобы произвести уже 'нормальный' путь от источника до адресата.

При простой реализации A* производит один, из возможного большого числа оптимальных путей. Однако, это не всегда может быть один наиболее визуально приятный путь. Его можно получить при помощи уклона (предпочтения), меняя порядок, при котором соседи равной стоимости, удаляются из приоритетной очереди. При этом могут получаться визуально более приятные пути в областях, где однородные стоимости граней. См. рисунок 15. Точно какие направления предпочтены и в том, какой порядок является конечно высоко зависимым от реализации.

Наклоный путь Рандомизированный путь Визуально приятный путь

Рисунок 15 - Три одинаковых по стоимости пути в графе с однородными издержками края

Наиболее интуитивный способ, чтобы избежать уклонения, казалось бы в том, что бы регулярно, или даже беспорядочно, переставлять порядок, при котором расширения поиска пути к соседним ячейкам исследованы. Однако, в практических тестах, это не производит удовлетворительные уточнения. Вероятное объяснение - то, что эта схема только вводит новый порядок предпочтений, которые являются статическим относительно графа. Как альтернативу, введем случайный элемент. С вероятностью 0.5, примем новый путь, которые не уточнил бы текущий самый лучший путь, но не ухудшил его (то есть новые пути по стоимости равняются текущей самой лучшей стоимости). Это дает удовлетворительный результат (если не совершенный) как отмечено на примере на рисунке 15. Число 0.5 было выбрано, потому что вероятность наличия двух в равной степени хороших расширений данного пути на реальной карте - (эвристически, если Вы будете) намного больше, чем наличия трех или более. Таким образом, когда мы приходим в точку, где мы должны выбрать между двумя в равной степени хорошими путями, мы можем использовать подбрасывание монеты, игнорируя возможность третьего равного пути стоимости и все еще ожидать результат без значительного уклона.

При выполнении A* алгоритма, наиболее важным фактором (с точки зрения и использования памяти и времени для вычисления) является то, как выполнена приоритетная очередь. Давайте обозначим число ячеек N. В течение каждого прохода по основному циклу, PQ.ExtractMin вызывается только однажды. Когда узел был извлечен, он не будет пройден снова, так что цикл выполняет максимум N раз. Только операции, за исключением PQ.ExtractMin, внутри цикла, которые не выполняются за постоянное время, находятся внутри просмотра соседей. Цикл сканирования соседей непосредственно выполняется больше восьми раз, то есть он не увеличивает время больше чем на 'постоянное' количество операций внутри цикла. Из-за специального характера нашего представления графа, мы можем легко 'находить' соседей за постоянное время. Не-постоянные операции по времени возможны внутри цикла просмотра соседей - PQ:INSERT и PQ.DecreaseKey. Так что весь алгоритм отнимает O(N)*min{8*PQ.Insert, 8*PQ.DecreaseKey, PQ.ExtractMin времени.

Самый простейший метод, который часто используется при небольших задачах, состоит в том, чтобы использовать сортированый связаный список для приоритетной очереди. Однако, в то время как операция PQ.ExtractMin для этого берет O(1) времени, операции PQ.Insert и PQ.DecreaseKey берут O(N) времени. Таким образом, целый алгоритм прошел бы за O(N²) времени. Для этой цели, лучше использовать хорошо - известную приоритетную очередь - так называемую кучу Фибоначчи. Поскольку теория и реализация этих куч несколько сложна, то их описание здесь опущено см. [CORM90] стр. 420.. 439. Типовая реализация может быть найдена в [BOYE97]. Операции с кучей Фибоначчи выполняются за различное время в зависимости от внутреннего состояния переменных. Например, вставки могут вначале идти очень быстро, затем после нескольких вставок, приходит время делать некоторую 'очистку дома', которая может забрать значительно большее количество времени. Таким образом, 'амортизационные' издержки используются взамен, и время, требуемое, чтобы выполнить последовательность операций усредняется по всем операциями, выполняемыми в течение алгоритма; см. [CORM90] глава 18 для дальнейшего рассмотрения. Удовлетворитесь здесь только замечанием, что издержки амортизации стоят для кучи Фибоначчи: O(1) для PQ.Insert, O(1) для PQ.DecreaseKey и O(log(N)) для PQ.ExtractMin. Таким образом самая лучшая известная реализация A* (также как алгоритм Дийкстры) выполняет за O(Nlog(N)) времени. Константы, скрытые внутри нотации O совершенно большие для куч Фибоначчи, хотя, поэтому они не очень полезны для маленьких куч.

А как насчет памяти? На старте, каждая вершина, v, нуждается в значении для g[v] и h[v], который таким образом требует O(N) памяти. Кроме того, каждый элемент в приоритетной очереди занимает некоторую память. Тривиальная верхняя граница максимального числа элементов в очереди - N, так что общая занимаемая память имеет верхнюю границу O(N). Практически, максимальный размер очереди имеет тенденцию, чтобы быть значительно меньше чем N, см. например рисунок 23 в разделе 5.4 (где вершина в очереди была отмечена белым). С другой стороны, при реализации кучи Фибонначи, каждый элемент, сохраненный в очереди забирает довольно большое (хотя линейное) количество памяти.

Для нашего приложения мы больше заинтересованы потреблением времени как функцией расстояния, d, между источником и адресатом. Некоторые модели для зависимости N от d были обсуждены в 3.1.1.1. В большинстве случаев N имеет квадратичную зависимость от d и при этом, что алгоритм выполяется за O(d²log(d)) время. Таким образом на каждом 'реальном' компьютере когда верхняя граница расстояний, d_max, после, которой мы быстро исчерпаем память. В разделе 4.3 показан метод как увеличить d_max.

Пример реализации A* алгоритма на C++ приведен здесь. В качестве функции веса w(u,v), функция EdgeCost, определенная в 3.2.2 используется. Эвристика A* реализована таким образом:

DWORD SearchGraph::CostNorm(CellRef crSrc, CellRef crDst)

// Возвращает недооценку стоимости пути от crSrc до crDst

// в массиве dwMinEdgeCost сохранены стоимости всевозможных граней

{

int iDX = abs(crSrc.X()-crDst.X());

int iDY = abs(crSrc.Y()-crDst.Y());

returndwMinEdgeCost[edDiagMod]*min(iDX,iDY) + 

dwMinEdgeCost[edAxisMod]*abs(iDX-iDY);

}

Класс FibHeap стандартная куча Фибоначчи из узлов FibHeapNode. Каждый такой 'узел' сохраняет вершину и ассоцированые с ней g и h значения. Куча Фибоначчи создана после увеличения порядка значения f = g + h. В дополнение к (очень большой) структуре данных, требуется для поддержания кучи Фибоначчи, FibHeapNode также имеют следующие поля данных:

cr для сохранения ссылки на ячейку узла

g стоимость на данный момент самого лучшего пути к cr

h мин. оценка стоимости пути от cr до адресата

Массив Nodes - справочная таблица, используемая, чтобы найти либо указатель в FibHeapNode для вершины, которая находится на данный момент в PQ, или специальные значения обозначающие, что вершина уволена или не посещена. Когда найдено, что вершина не посещена, то она находится в U, когда найдено что она уволена, то она находится в R (см. 4.2.1), иначе она находится в PQ. Память для FibHeapNode выделена вначале, когда вершина помещена в PQ и освобождается, когда она увольняется. Каждый узел FibHeapNode требует намного больше памяти, чем вход в Nodes[] (34 байта против 4 в нашей реализации). Число вершин в PQ в любое время в среднем намного меньше, чем общее число вершин (наши тесты показывают почти логарифмическую зависимость, хотя при самом плохом случае зависимость будет линейной, это вряд ли произойдет). Таким образом это может сохранить больше памяти, по сравнению со способом распределения FibHeapNode для каждой вершины из одного большого блока. Чтобы подавлять непроизводительные затраты при управлении памятью, последний уволенный узел FibHeapNode из PQ кэшируется для повторного использования при вставки следующего нового узла, когда он должен быть вставлен впервые, таким образом это сохраняет много new и delete операций.

DWORD SearchGraph::AStarPath(

EdgeDir *&pedEdges, // Выход: список направлений грани

int &iNumEdges,// Выход: число граней в pedEdges

CellRef crBeg,// Вход: исходная ячейка

CellRef crEnd// Вход: ячейка адресат

)

{

 PFibHeapNode *Nodes = new PFibHeapNode[dwTotalCells];

 EdgeDir *ed = new EdgeDir[dwTotalCells];

 PFibHeapNode pU, pV, pReuse = NULL;

 FibHeap PQ;

 CellRef crU, crV;

 DWORD dwCost;

 int iV, i;

// Установим, что все узлы не посещены

 for (i = 0; i < dwTotalCells; i++)

 Nodes[i] = notvisited;

// Вставка исходного узла

 Nodes[IndexOf(crBeg)] = pU = new FibHeapNode;

 pU->cr = crBeg;

 pU->g = 0;

 pU->h = CostNorm(crBeg, crEnd);

 PQ.Insert(pU);

// Пока можно посещаем все

 while ((pU = PQ.ExtractMin()) != NULL) {

// Если достигли адресата выйдем

 crU = pU->cr;

 if (crU == crEnd) {

 dwCost = pU->g;// Окончательная стоимость 

 delete pU;

 break;

 }

// Проверка возможных путей от U к его соседям

 for (EdgeDir edp = 0; edp < NUMEDGEDIRECTIONS; edp++) {

// Вычисление кандидата с новой наименьшей стоимостью

 dwCost = pU->g + EdgeCost(crV, crU, edp);

// Если значение больше ограничения

// ( т.е. вне карты), то пропустим его

 if (dwCost >= infinity) continue;

iV = IndexOf(crV);

 pV = Nodes[iV];

 if (pV == retired) continue;// не можем улучшить

if (pV == notvisited) {// Вставка в очередь первый раз

if (pReuse != NULL) {

pV = pReuse;

pReuse = NULL;

} else pV = new FibHeapNode;

Nodes[iV] = pV;

ed[iV] = edp;

pV->cr = crV;

pV->g = dwCost;

pV->h = CostNorm(crV, crEnd);

PQ.Insert(pV);

 } else if (dwCost <= pV->g) {// Может улучшим !?

if (dwCost == pV->g) {

if (rand() <= RAND_MAX/2)// избежим смещения

ed[iV] = edp;

continue;

}

ed[iV] = edp;// Обновление соседа

pV->g = dwCost;

PQ.DecreaseKey(pV);

 }

 }

 }

if (crU == crEnd) { // Мы нашли путь

// Подсчет числа граней возврата пути

for (iNumEdges = 0; crU != crBeg; iNumEdges++)

WalkEdge(crU, crU, OppositeEdge(ed[IndexOf(crU)]));

// Реконструирование пути по граням при помощи

// перебора по возвратам & в обратном направлении...

 pedEdges = new EdgeDir[iNumEdges];

 EdgeDir *ped = pedEdges + iNumEdges;

 for (crU = crEnd; crU != crBeg; )

 WalkEdge(crU, crU, 

OppositeEdge(*(--ped) = ed[IndexOf(crU)]));

} else {// Путь не найден

return 0

delete[] ed;

pedEdges = NULL;

dwCost = 0;

 }

// Освобождение памяти (PQ, освобождает узлы поставленные

// в очередь самостоятельно)

if (pReuse != NULL) delete pReuse;

 delete[] Nodes;

 delete[] ed;

return dwCost;

}

6. Прогрессивная аппроксимация

Для очень больших графов, мы неизбежно исчерпаем физическую память когда будем обсчитывать нескольких миллионов вершин на нынешних стандартных персональных компьютерах. Использование жесткого диска для виртуальной памяти помогает, но резко замедляет вычисления. Учитывая это, может ли A* искать более быстро, и при этом уменьшая использование памяти? Далее, рассмотрим прогрессивный метод, когда вначале грубое, приблизительное решение вычислено, которое затем расширено до более точного решения.

Грубое решение может быть найдено, запустив обычный A* алгоритм на 'укрупненной модели' графа. Укрупненный граф создается из оригинала 'группируя вместе' квадратные области соседних вершин в одну вершину, для того чтобы получить уменьшенный граф, который все еще представляет оригинал. При коэффициенте укрупнения равном 4, имеем что 4x4 вершины собраны в одну новую, и мы имеем 16-кратное уменьшение и, числа граней и вершин как проиллюстрировано на рисунке 16. Количество использованной памяти A* алгоритмом, чтобы найти грубое решение на укрупненном графе соответственно уменьшается. Как мы должны определить функцию стоимости для укрупненного графа? Несколько подходов равнозначно. При первом подходе надо выбрать значения самого короткого пути между вершиной в первоначальном графе, которые совпадут с теми же в укрупненном графе (см. рисунок 16). При другом подходе, надо некоторым способом, 'вычислить среднее' всех возможных путей, которые могут быть созданы из граней, сгруппированых вместе. Оба этих подхода имеют ряд трудностей и требуют незначительного времени для вычислений. Вместо этого, был выбран подход с созданием нового набора атрибутов для укрупненного графа и 'многократного использования' 'первоначальной' функции стоимости. Если 'масштаб' уменьшен по всем пространственным координатам, зависящие от длины грани значения, которые использует функция стоимости не обязательно должны быть повторно вычислены; оптимальный путь будет тот же самый, хотя общая стоимость пути будет не такой же.

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



Рисунок 16 -Укрупненные грани, при факторе 4

Рисунок 17 - укрупненные сегмены пути

Затем, грубое решение (найденное на укрупненном графе) разделенно на 'сегменты', как несколько преувеличенно иллюстрировано на рисунке 17, где небольшой путь с девятью гранями был разделен на три сегмента по три грани каждый. Затем, оптимальный путь между конечными точками первого сегмента (отмеченными черными кругами на рисунке) найден, используя A* алгоритм на оригинальном 'точном' графе. Это повторяется для других сегментов, и все 'точные' решения сегментов в заключение вставляются вместе в полное решение. Однако нельзя сказать, что точки конца сегмента должны лежать на оптимальном пути. Таким образом, эта схема улучшена, во-первых, при помощи использования фактической исходной вершины для первого точного сегмента путей и вершины адресата для последнего. Далее, для каждого нового сегмента (следующие после первого) предыдущий 'точный' путь находится по указателям возврата нескольких граней. Это положение затем принимается как исходная вершина для поиска A* в новом сегменте вместо 'грубой' отметки начала сегмента; см. рисунок 17. Хорошая идея добавить проверку, того что вершина, используемая как источник и адресат в каждом точном решении сегмента не попадает внутрь например воды или других недоступных областей. Так как любой сегмент может быть сделан намного короче чем общая длина пути, очередь поисков A* станет намного меньше. Имеются некоторые непроизводительные затраты, связанные с нахождением пути, используя эту процедуру, так что стандартный метод будет обычно быстрее. Однако, при намного меньшей очереди поиска можно найти путь только в оперативной памяти и не использовать жесткий диск для виртуальной памяти. Таким образом, на больших графах, мы можем фактически ожидать уменьшения времени поиска. Это было проверено на практических тестах, см. дальше раздел 5.5

Этот процесс можно бы теоретически разбить на отдельные этапы, которые начинаются с очень грубого решения и продолжаются к более точным решениям на сетках/графах. Однако, при укрупнении может потеряться информация которая необходима для нахождения оптимальных путей, например узкие мосты, непроходимые реки и т.д.. Это означает это, если мы хотим найти 'возможное решение', грубый граф должен содержать все 'существенные' характеристики карты. Это можно обеспечить выбором наибольшего коэффициента укрупнения. Практические тесты показывают, что при коэффициенте 6 все еще можно избежать слишком очевидных побочных эффектов (особенно в городских регионах). Кроме того, не много можно использовать от графа, который является более точным чем первоначальные растровые данные, так что процесс с двумя шагами, кажется, единственный, который имеет смысл. Другая проблема - длина сегмента. Для максимальной скорости длина должна быть как можно большей до предельного значения, при которой A* алгоритм начинает использовать слишком много памяти. Фактическое значение предела зависит от очень многих вещей, и от фактической реализации также как и специфической среды, в которой поиск производится. Эмпирический анализ специфического приложения при хорошем 'запасе прочности' способен обеспечить подходящее значение длины сегмента (это так же может зависить от времени рассуждения предоставляемого юниту для выбора пути).

Насколько же хорошо метод, представленный здесь работает в реальных приложениях? Был произведен ряд тестов, некоторые из них представлены здесь.

На этих рисунках, насыщенности серого соответствует стоимость перемещения через местность. Более светлые области более дешевые, а более темные более дорогие. Вода черная. Дороги показаны белым. Широкие дороги имеют малую стоимость перемещения, в то время как узкие дороги имеют большую стоимость (но вообще все еще меньшую, чем типичная стоимость местности). Пути проведены темно-серым. Область поиска ограничена черным прямоугольником в случае, если она находиться в рисунке, например см. рисунок 18.

Рисунок 18 - Некоторая типичная местность, дороги, область поиска и путь.

Препятствия в форме озер и труднопроходимой местности корректно обходяться. На рисунке 19, темно-серый - лес ( с очень плохой проходимостью) а черная - вода.



Рисунок 19 - Три коротких пути через местность с лесом и озерами.

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

Рисунок 20 - Маршрут обходного пути найден, чтобы избежать вражеской территории.

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

Рисунок 21 - Может быть более важено достичь адресата, чем полностью уйти от врага.

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



Рисунок 22 - Дороги широко задействованы в этом примере

Область поиска A*

Для того чтобы четко показать, как алгоритм поиска A* 'распространяет' от источника, необходима анимация. Но так как в печатной форме довольно трудно показывать анимацию фотоснимком. Рисунок 23 иллюстрирует ситуацию на тот момент времени, когда оптимальный путь к адресату найден, и работа алгоритма завершена. Ячейки, которые находятся в очереди поиска (то есть на 'фронте' поиска) отмечены белыми точками. Все ячейки внутри этой 'области' уволены из очереди поиска (то есть оптимальные пути к ним были найдены). Ячейки вне этой области не были посещены (введенны в очередь поиска) в течение поиска. Обратите внимание, что число ячеек в очереди - только малая доля всех ячеек в области поиска (ограниченной черным прямоугольником). Далее, общее число обработанных ячеек (в течение поиска) около четверти всех ячеек. В случае, если мы имеем более длинный путь, большое количество дорог и меньшее количества леса, эта доля - обычно около половины. Мы видим, даже в этом примере, что есть тенденция для дорог увеличивать область поиска, расширяя длинные 'усики' к удаленным областям.



Рисунок 23 - Фронт поиска на тот момент, когда адресат достигнут.

Прогрессивная аппроксимация

Рисунок 24 - больший граф поиска, 8.5 млн. вершин



Рисунок 25 - Время против длины сегмента

Чтобы сделать рассмотрение более подробным, до настоящего времени все приведенные примеры использовали относительно малую область поиска. Они все занимают в большинстве случаев нескольких секунд расчета. Для того чтобы понять эффективность работы на больших графах давайте рассмотрим рисунок 24, который показывает путь, где расстояние между источником и адресатом - приблизительно 64 км (размер ячейки - 25 м). Для ясности, рисунок только указывает главные дороги и позволяет различить разные типы местности воду, город или другую. Фактические данные графа для поиска такие же, как в предыдущих примерах, только намного больше, поэтому они не представлены подробно. Полный граф для поиска, содержит приблизительно 8.5 миллионов вершин. Враги отсутствуют. При использовании стандартного алгоритма, расчет занял 48 сек, на Pentium 133 с 18МБ свободной памяти. Время для выборки растровых данных не учитано. Большинство времени было отнято управлением виртуальной памятью на жестком диске. Для сравнения, вычисление 'грубого' решения при коэффициенте 6 укрупненного графа заняло только 2.5s! Насколько хорош прогрессивный метод при той же проблеме? Это незначительно зависит от выбранной длины сегмента; при большом количестве сегментов, большое количество непроизводительных затрат; поэтому их должны быть немного (то есть длинные) насколько возможно. С другой стороны, если они слишком длинные, мы снова исчерпаем память, и на обмен с диском будет тратиться много времени. Рисунок 25 показывает график времени от длины сегмента для нескольких тестов. Все эти тесты использовали 6-кратное укрупненное приблизительное решение, которые были затем разделены на сегменты различных длин. Длина сегмента выражена как число граней в укрупненном графе решения (то есть 1/6-ой из числа граней в точном графе). Во всех упомянутых случаях (даже один 6-кратный укрупненный граф) результат фактически был визуально неразличим на рисунке 24 вследствие того, что размер ячейки был намного меньше, чем экранный пиксел.

Мы ищем только пути, которые внутри назначенной области поиска. Рисунки 26 и 27 иллюстрируют проблему возникающую при этом с озером в качестве препятствия и двух областей поиска с разными размерами.

Рисунок 26 - В малой области поиска - нет пути

Рисунок 27 - С увеличинной областью поиска

Мы не обязаны ограничиваться только перемещением по земле транспортных средств. Есть пример, с лодкой; все дороги и стоимость местности установлены в за исключением воды, которая показана темным цветом на рисунке 28. В отличие от предыдущих рисунков, цвета на этом рисунке не соответствуют стоимости перемещения. Обратите внимание, что, если мы знаем, что ищем, мы можем ясно видеть, что имеются только восемь возможных направлений для перемещения. Например, в левом верхнем углу начала пути, имеется показательный пример направленного смещения.

Рисунок 28 - Управление лодкой в архипелаге Стокгольма.

Заключение

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

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

Имеются несколько мыслей, что заслуживают внимания и можно исследовать с большей тщательностью:

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

При другом подходе надо следить за параметром времени наряду с параметром 'самый лучший путь' для каждого узла в течение поиска A*. Этот параметр мог бы затем использоваться вместе с пространственной позицией подобно нахождению врага и других модификаторов. Это имеет большое преимущество (по сравнению с предыдущим подходом) только когда берутся изменения в 'константе' пространства и времени одновременно. Это также хорошо, даже если имеются большие изменения во вражеских перемещениях и т.д.. С другой стороны, это вызывает много работы, за отслеживанием параметра 'текущего времени' во время поиска, но это предохранило бы от использования 'ленивого' вычисления видимости, поскольку видимость больше не статическая во время поиска.

При помощи увеличения числа ячеек, рассматриваемых как соседи данной ячейки, мы можем увеличивать число граней в графе. Возьмем экстремум и рассмотрим все другие ячейки, как соседей и получим так называемый полный граф. Поскольку A* алгоритм с хорошей эвристикой действительно дает оптимальное решение для графа, это должно дать нам отличное решение для проблемы 'растрезации'. Но, тогда затраченное время как - Nlog(N) найденное в больше не истинно (N - число вершин) поскольку число граней, М, больше не статическое, как было принято. Взамен мы имеем M=N² число соседей, для исследования в каждой итерации, тогда затраченное время будет рассчитано как O(NlogN + NM) = O(N³). Следовательно, стоимость для улучшения точности для всех размеров графов зависит в более высокой полиномиальной степени от времени и размера памяти. Однако, что является оптимальном числом соседей? То есть какой идеальный компромисс между ошибкой и эффективностью? Решение использовать восемь соседних ячеек было удобно, так как это то максимальное число, для которого функция стоимости грани легко определяется и вычисляется.

Альтернативные методы определения врагов и видности не исследовались в этой работы. Так как это довольно тяжело, и возможно это еще одна область, где более эффективный алгоритм мог бы быть применен с выгодой.

В разделе отмечено, что оптимальная A* эвристическая функция h, может масштабироваться как ch, при этом уменьшение c до нуля приводит к методу Дийкстры, или дает приблизительные результаты для c>1. При более высоких с, поиск больше 'направлен' к цели и понижается ожидаемая средняя продолжительность поиска, но также и поведение алгоритма становится более 'глупое' относительно обхода препятствий. Самый плохой случай поведения не улучшен. Возможно что может быть найдена более хорошая эвристика? Или возможно мы могли бы создать эвристику, которая пробует подражать решению человека, который 'решает' как действовать в зависимости от 'локального' состояния окружающей местности?

Альтернативы использования A* могут быть исследованы при нахождении приблизительных путей. Моделирование обжига довольно интересный вариант. Он имеет некоторую привлекательность, так как дает абсолютный контроль над временем решения; его можно остановить всякий раз, когда исчерпан лимит времени или когда считаем, что решение достаточно хорошое. Чем дольше он выполняется, тем более высокая точность может ожидаться. Однако, построение хорошей функции возмущения, далеко не тривиальная задача. Чтобы получить высокую степень точности решения, требуется значительно больше времени, чем для метода A*. Более подробное сравнение методов довольно интересно. Есть идея в том, чтобы использовать моделируемый обжиг для грубого решения и затем использовать A*, чтобы уточнить решение локально, подобно прогрессивному методу.

Библиография

1. Boyer, The Fibonacci Heap, Dr. Dobb's Journal, #261 January 1997.

2. Buckley, F. Harary, Distance in graphs, Addison-Wesley, 1990, pp. 270-272.

3. V. Cherkassky, A.V. Goldberg, and T. Radzik, Shortest Paths Algorithms: Theory and Practice, Technical Report, STAN-CS-93-1480, Computer Science Department, Stanford University, Stanford, CA, 1993.

4. C. Clarke, Analytical and Computer Cartography, Prentice Hall, 1990.

5. H. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms. The MIT Press/McGraw-Hill, 1990.

6. W. Dijkstra,A note on two problems in connection with graphs, Numerische Mathematik, 1959.

7. Elg, Sцkgraf fцr kortaste vдgen i planet, FOA, 1992.

8. Foley, A. van Dam, S. Feiner, J. Hughes, Computer Graphics, Principles and Practice, 2^nd ed., Addison-Wesley, 1990.

9. D. Holmes and E.R.A. Jungert, Symbolic and geometric connectivity graph methods for route planning in digitized maps, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 5, 1992, pp549-565.

10. Kimmel, A. Amir, and A.M. Bruckstein, Finding shortest paths on surfaces using level sets propagation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no. 6, 1995, pp635-640.

11. G. Luenberger, Linear and Nonlinear programming, 2^nd ed, Addison Wesley, 1984.

12. M. Montgomery et al., Navigation algorithm for a nested hierarchical system of robot path planning among polyhedral obstacles, Proceedings IEEE International conference on Robotics and Automation, pp. 1616-1622, 1987.

13. N J Nilsson, Principles of Artificial Intelligence, Springer Verlag. Berlin, 1982.

14. W. H. Press, S. A. Teukolsky, W. T. Vetterling, B. P. Flannery, Numerical Recipes in C, 2^nd ed., Cambridge University Press, New York, 1992, pp. 444-455.

15. M. Sonka, V. Hlavac, R. Boyle, Image Processing, Analysis and Machine Vision, Chapman & Hall, London, 1993.

16. E. Stefanakis, M. Kavouras, On the determination of the Optimum Path in Space from A.U. Frank, W. Kuhn (editors) Spatial Information Theory, A theoretical basis for GIS, COSIT95 Proceedings, LNCS 988, 1995.

Размещено на Allbest.ru

...