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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.67
parikmaher534
38 / 38 / 1
Регистрация: 16.11.2011
Сообщений: 112
#1

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

20.09.2012, 13:50. Просмотров 3608. Ответов 5
Метки нет (Все метки)

Добрый день.
Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну вещь.

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

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

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

C++ Волновой алгоритм
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
C++ Волновой алгоритм (шахматы, конь)
C++ Волновой алгоритм
C++ Волновой алгоритм
Волновой алгоритм C++
C++ Волновой алгоритм - поиск минимального пути
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
Псевдослучайный
1743 / 1086 / 71
Регистрация: 13.09.2011
Сообщений: 3,108
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
4661 / 2487 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.09.2012, 19:39     Волновой алгоритм поиска пути #6
Цитата Сообщение от NoMasters Посмотреть сообщение
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
Вот это правильный алгоритм. Только этот путь нужно заносить куда-то (пока не дойдем до начальной точки), а потом выводить.
Если же сделать волну от конечной точки в начальную, то можно путь сразу выводить на экран.
Yandex
Объявления
20.09.2012, 19:39     Волновой алгоритм поиска пути
Ответ Создать тему
Опции темы

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