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

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

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

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

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

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

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

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

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

Волновой алгоритм - поиск минимального пути - C++
Доброго времени суток всем. Не могу въехать в алгоритм волновой для поиска минимального пути. Видел кучу примеров с готовым кодом, читал,...

Алгоритм поиска пути - C++
Ребята, помогите разобраться с кодом. Пробую реализовать преследование привидений пакмана. При этом использую алгоритм поиска пути и...

Алгоритм поиска пути и прорисовка его - C++
Есть класс Карта #ifndef MAP_H #define MAP_H #include <SFML\Graphics.hpp> class Map{ private: int m_level; public:

Алгоритм поиска пути в лабиринте, заданном связным графом - C++
использовать алгоритм поиска пути в лабиринте, заданном связным графом. граф уже задан в самой программе. Пример: int mas = {...

Волновой алгоритм - C++
Нужно найти кратчайший путь в лабиринте размерностью 10х10 , и выводить ответ. Помогите

Волновой алгоритм - C++
Здравствуйте, очень прошу помочь с реализацией волнового алгоритма только лишь с помощью матрицы весов неориентированного графа. Объясните...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
Псевдослучайный
1747 / 1090 / 71
Регистрация: 13.09.2011
Сообщений: 3,121
20.09.2012, 15:08     Волновой алгоритм поиска пути #4
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
defer
秘密
555 / 235 / 3
Регистрация: 29.11.2010
Сообщений: 783
20.09.2012, 15:12     Волновой алгоритм поиска пути #5
Цитата Сообщение от parikmaher534 Посмотреть сообщение
Алгоритм пока не останавливается когда находит конечную точку а идет до конца по всему полю.
Это не правильно, весь смысл в том, что алгоритм останавливается, и у вас конечная точка получается окруженной самыми большими числами, и путь ищется просто обратным ходом
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.09.2012, 19:39     Волновой алгоритм поиска пути
Еще ссылки по теме:

Волновой алгоритм - C++
Доброго времени суток, дорогие форумчане. Никак не додумаю волновой алгоритм, помогите, кто чем может: файл - матрица целых чисел, где...

Волновой алгоритм - C++
Подскажите пожалуйста, на сколько сложно изготовить из матрицы 0000 0000 0000 напр.4345 3234 2123 3234 Только при помощи обычных...

Волновой алгоритм - C++
Нужно реализовать волновой алгоритм поиска кратчайшего пути на поле 20*20, причем координаты начала и конца вводятся пользователем,...

Лабиринт - волновой алгоритм - C++
Помогите пожалуйста. Я написал код, который мне выведет на экран кратчайший путь... Но чего-то не хватает.... Может создать цикл с...

Tiled Map и волновой алгоритм - C++
Делаю игру пакман. Нашла, что для привидений хорошо подходит волновой алгоритм. Нашла примеры реализации -все они завязаны на двумерных...

Волновой алгоритм (шахматы, конь) - C++
Всем привет! Пытался написать волновой алгоритм для нахождения кратчайшего пути коня на шахматной доски из A->B. Но что-то у меня...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.09.2012, 19:39     Волновой алгоритм поиска пути #6
Цитата Сообщение от NoMasters Посмотреть сообщение
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
Вот это правильный алгоритм. Только этот путь нужно заносить куда-то (пока не дойдем до начальной точки), а потом выводить.
Если же сделать волну от конечной точки в начальную, то можно путь сразу выводить на экран.
Yandex
Объявления
20.09.2012, 19:39     Волновой алгоритм поиска пути
Ответ Создать тему
Опции темы

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