Форум программистов, компьютерный форум CyberForum.ru

Волновой алгоритм поиска пути - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.67
parikmaher534
38 / 38 / 1
Регистрация: 16.11.2011
Сообщений: 112
20.09.2012, 13:50     Волновой алгоритм поиска пути #1
Добрый день.
Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну вещь.

Пройдя волновым методам по соседним клеткам нахожу конечную точку. Матрица тоже заполнена:
Волновой алгоритм поиска пути

Тут -3 - препятствие, -5 конечная точка.

Подскажите как получить массив с шагами( координатами ) наименьшего пути?
Как организовать сам цикл? Нужно складывать веса сразу при прохождении волнами что-ли?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.09.2012, 13:50     Волновой алгоритм поиска пути
Посмотрите здесь:

C++ Волновой алгоритм
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Волновой алгоритм
C++ Волновой алгоритм
Волновой алгоритм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
defer
秘密
 Аватар для defer
555 / 235 / 3
Регистрация: 29.11.2010
Сообщений: 783
20.09.2012, 14:49     Волновой алгоритм поиска пути #2
У вас что-то не правильно в алгоритме, рядом с точкой -5 должны быть самые большие цифры
parikmaher534
38 / 38 / 1
Регистрация: 16.11.2011
Сообщений: 112
20.09.2012, 14:58  [ТС]     Волновой алгоритм поиска пути #3
Цитата Сообщение от defer Посмотреть сообщение
У вас что-то не правильно в алгоритме, рядом с точкой -5 должны быть самые большие цифры
Алгоритм пока не останавливается когда находит конечную точку а идет до конца по всему полю. Возле -5 вроде максимальные числа 5. Выход из цикла при совпадении я сделаю. А вот подскажите что дальше?
Как получить координаты шагов пути?
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,094
20.09.2012, 15:08     Волновой алгоритм поиска пути #4
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
defer
秘密
 Аватар для defer
555 / 235 / 3
Регистрация: 29.11.2010
Сообщений: 783
20.09.2012, 15:12     Волновой алгоритм поиска пути #5
Цитата Сообщение от parikmaher534 Посмотреть сообщение
Алгоритм пока не останавливается когда находит конечную точку а идет до конца по всему полю.
Это не правильно, весь смысл в том, что алгоритм останавливается, и у вас конечная точка получается окруженной самыми большими числами, и путь ищется просто обратным ходом
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.09.2012, 19:39     Волновой алгоритм поиска пути #6
Цитата Сообщение от NoMasters Посмотреть сообщение
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
Вот это правильный алгоритм. Только этот путь нужно заносить куда-то (пока не дойдем до начальной точки), а потом выводить.
Если же сделать волну от конечной точки в начальную, то можно путь сразу выводить на экран.
Yandex
Объявления
20.09.2012, 19:39     Волновой алгоритм поиска пути
Ответ Создать тему
Опции темы

Текущее время: 03:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru