Форум программистов [Powered by Invision Power Board]

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

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

Автор: 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

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

Делай выводы smile

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

Цитата

на самом деле весь волновой алгоритм к моменту выполнения этого действия уже закончился, здесь описан уже сам процесс прохода по кратчайшему пути

Цитата

В связи, с чем вопрос, надо ли использовать дополнительные алгоритмы

ни в коем случае, алгоритм уже сделан, в каждой клеточке написано кратчайшее растояние до цели

Цитата

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

если значения 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

Вышли мне если тебе не трудно реализацыю алгоритма на [email protected]

Автор: 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