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

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

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

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

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

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

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

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

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

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

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

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

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

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

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
defer
秘密
555 / 235 / 3
Регистрация: 29.11.2010
Сообщений: 783
20.09.2012, 14:49 #2
У вас что-то не правильно в алгоритме, рядом с точкой -5 должны быть самые большие цифры
0
parikmaher534
38 / 38 / 1
Регистрация: 16.11.2011
Сообщений: 112
20.09.2012, 14:58  [ТС] #3
Цитата Сообщение от defer Посмотреть сообщение
У вас что-то не правильно в алгоритме, рядом с точкой -5 должны быть самые большие цифры
Алгоритм пока не останавливается когда находит конечную точку а идет до конца по всему полю. Возле -5 вроде максимальные числа 5. Выход из цикла при совпадении я сделаю. А вот подскажите что дальше?
Как получить координаты шагов пути?
0
NoMasters
Псевдослучайный
1754 / 1097 / 72
Регистрация: 13.09.2011
Сообщений: 3,134
20.09.2012, 15:08 #4
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
0
defer
秘密
555 / 235 / 3
Регистрация: 29.11.2010
Сообщений: 783
20.09.2012, 15:12 #5
Цитата Сообщение от parikmaher534 Посмотреть сообщение
Алгоритм пока не останавливается когда находит конечную точку а идет до конца по всему полю.
Это не правильно, весь смысл в том, что алгоритм останавливается, и у вас конечная точка получается окруженной самыми большими числами, и путь ищется просто обратным ходом
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.09.2012, 19:39 #6
Цитата Сообщение от NoMasters Посмотреть сообщение
Идёшь от конечной ячейки по наименьшим значениям соседних клеток, пока не дойдешь до старта.
Вот это правильный алгоритм. Только этот путь нужно заносить куда-то (пока не дойдем до начальной точки), а потом выводить.
Если же сделать волну от конечной точки в начальную, то можно путь сразу выводить на экран.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.09.2012, 19:39
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
20.09.2012, 19:39
Ответ Создать тему
Опции темы

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