Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нахождение кратчайшего пути в волновом алгоритме

Автор: Royan 26.12.2004, 14:49

Описание "Волнового алгоритма" можно найти здесь: http://www.codenet.ru/progr/alg/way.php или здесь http://algolist.manual.ru/games/wavealg.php У меня есть реализация этого алгоритма на С++ (могу кому надо выслать для наглядности) Способ определения кратчайшего (или одного из путей), в описанных выше алгоритмах сводился примерно к следующему: Цитата В окрестности позиции R(Х,Y) (конечная точка) ищем элемент с наименьшим значением (т.е.для этого просмaтривaем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координаты этого элемента заносим в переменные X1 и Y1. Совершаем перемещение объекта по полю из позиции [X,Y] в позицию [X1,Y1] и повторяем операцию. Но так, на мой взгляд, на начальном этапе (в принципе и позже тоже) можно уехать в любую сторону, если значения справа, слева, вверху или внизу одинаковы. В связи, с чем вопрос, надо ли использовать дополнительные алгоритмы (Дейкстры или Флойда) чтобы на основе имеющихся данных построить матрицу смежности и определить кратчайший путь, или я чего не понимаю?

Автор: podval 26.12.2004, 17:16

Оптимизационная задача может иметь: - единственное решение; - множество решений; - ни одного решения. Делай выводы

Автор: maxim1000 26.12.2004, 21:23

Цитата В окрестности позиции R(Х,Y) (конечная точка) ищем элемент с наименьшим значением (т.е.для этого просмaтривaем R(Х+1,Y), R(Х-1,Y), R(Х,Y+1), R(Х,Y-1). Координаты этого элемента заносим в переменные X1 и Y1. Совершаем перемещение объекта по полю из позиции [X,Y] в позицию [X1,Y1] и повторяем операцию. на самом деле весь волновой алгоритм к моменту выполнения этого действия уже закончился, здесь описан уже сам процесс прохода по кратчайшему пути Цитата В связи, с чем вопрос, надо ли использовать дополнительные алгоритмы ни в коем случае, алгоритм уже сделан, в каждой клеточке написано кратчайшее растояние до цели Цитата Но так, на мой взгляд, на начальном этапе (в принципе и позже тоже) можно уехать в любую сторону, если значения справа, слева, вверху или внизу одинаковы если значения R снизу и сверху одинаковы, значит, можно двигаться и вверх, и вниз, неважно куда...

Автор: chaos 27.12.2004, 10:34

у меня есть алгоритм обхода всех возможных путей на С & pascal'e кому надо могу дать может чем поможет

Автор: Royan 27.12.2004, 15:55

Ну вот посмотрите как это выглядит у меня. http://polfin.narod.ru/pict/Field.jpg Красненькое начальная точка синенькая конечная, или наоборот если угодно. Тут просто так выбирая первое наименьшее/наибольшее не добершься.

Автор: Sunbeam 22.1.2006, 22:47

Цитата(Royan @ 26.12.2004, 14:49) Описание "Волнового алгоритма" можно найти здесь: http://www.codenet.ru/progr/alg/way.php У меня тут возник такой вопрос. А какое время работы данного алгоритма?

Автор: knut 11.2.2006, 19:18

Вышли мне если тебе не трудно реализацыю алгоритма на agent_angel_007@mail.ru

Автор: chaos 13.2.2006, 12:08

всем кто собирается это реализовывать на С++, предлагаю глянуть на библиотеку boost::graph http://boost.org http://boost.org/libs/graph/doc/table_of_contents.html вот исходники на Си(однажды пришлось решить человеку задачу обход графа) http://forum.vingrad.ru/index.php?showtopic=36790&view=findpost&p=287082

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)