Корректировка алгоритма кратчайшего пути - PullRequest
Новая
       2

Корректировка алгоритма кратчайшего пути

2 голосов
/ 12 декабря 2010

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

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

  • Проведите линию между исходным и конечным узлом, найдите ближайший узелдо середины этой линии и рекурсивно разделить «путь» на 2.Базовый случай был бы меньшим графом, если бы один Дейкстра сделал бы вычисление.Это не совсем корректировка текущего алгоритма, но если подумать, то ясно, что это не даст оптимального решения.
  • Попробуйте дать алгоритму некоторое чувство направления, придав более высокий приоритет ребрам, которыеуказать на конечный узел.Это также не будет оптимальным.

Так что теперь у меня нет идей, и я надеюсь, что кто-то здесь может дать мне небольшой намек на возможную корректировку.На самом деле не нужно улучшать алгоритм, я думаю, что первая причина, по которой они попросили нас сделать это, заключается в том, что мы не просто реализуем алгоритм из бумаги, не зная, что за этим стоит.

(ЕслиStackoverflow - не то место, где можно задать этот вопрос, мои извинения :))

Краткое описание алгоритма: алгоритм пытается выбрать, какие узлы выглядят перспективными.Под обещанием я подразумеваю, что у них есть хороший шанс лежать на кратчайшем пути.Насколько многообещающим является узел, представлен его «досягаемостью».Протяженность вершины пути - это минимум ее расстояний до начала и до конца.Достижение вершины в графе является максимумом вершин на всех кратчайших путях.Чтобы в конечном итоге определить, добавлен ли узел в очередь приоритетов в алгоритме Дейкстры, добавлена ​​функция test ().Тест возвращает true (если охват вершины в графе больше или равен значению, то вес пути от начала координат до v в момент времени v должен быть вставлен в очередь с приоритетами) или (охват вершины вграфик больше или равен евклидову расстоянию от v до конечной вершины).

Harm De Weirdt

1 Ответ

2 голосов
/ 12 декабря 2010

В таких случаях лучше всего думать как исследователь: исследования в целом и исследования в области компьютерных наук, в частности, касаются постепенного улучшения, один человек показывает, что он может вычислить что-то быстрее с помощью алгоритма Дейкстры, а затем они или кто-то еще , покажите, что они могут вычислить то же самое немного быстрее, используя A *. Это серия маленьких шагов.

Тем не менее, лучшее место для поиска путей улучшения алгоритма, представленного в статье, находится в разделе будущих направлений. Эта статья дает вам немного работы в этом направлении, но ваша золотая жила в этом случае находится в разделах 5 и 6. Есть несколько мест, где авторы допускают разные возможные подходы. Попробуйте исследовать некоторые из этих подходов, это должно привести вас либо к возможному улучшению алгоритма или, по крайней мере, один спорному. Желаем удачи!

...