Описание "Волнового алгоритма" можно найти здесь:
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] и повторяем операцию.

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

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

Делай выводы

Цитата

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

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

Цитата

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

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

Цитата

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

если значения R снизу и сверху одинаковы, значит, можно двигаться и вверх, и вниз, неважно куда...

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

Это сообщение отредактировал(а) chaos - 13.2.2006, 14:54

Ну вот посмотрите как это выглядит у меня. Скриншот Красненькое начальная точка синенькая конечная, или наоборот если угодно. Тут просто так выбирая первое наименьшее/наибольшее не добершься.

У меня тут возник такой вопрос. А какое время работы данного алгоритма?

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

всем кто собирается это реализовывать на С++, предлагаю глянуть на библиотеку boost::graph
boost
документация по графам


вот исходники на Си(однажды пришлось решить человеку задачу обход графа)
http://forum.vingrad.ru/index.php?showtopi...st&p=287082

Это сообщение отредактировал(а) chaos - 13.2.2006, 14:55