Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.51/41: Рейтинг темы: голосов - 41, средняя оценка - 4.51
oler117
0 / 0 / 0
Регистрация: 08.06.2009
Сообщений: 48
1

Поиск кратчайшего пути в лабиринте

10.06.2009, 21:29. Просмотров 7724. Ответов 5
Метки нет (Все метки)

Пишу программу для нахождения (и вывода) кратчашего пути в лабиринте, заданном в текстовом файле в виде бинарной матрицы. Пример:
Код
1 1 1 0 1 0 1 
0 1 1 0 1 0 0 
1 1 1 1 0 0 1 
0 1 0 1 1 0 0 
0 1 1 0 1 0 1
1 - проход, 0 - препятствие. По диагонали прохода нет! Начальная точка А: arr(iStart, jStart); конечная В: arr(iFinish, jFinish). Нужно:
1) Определить, существует ли путь от А до В.
2) Напечатать все возможные пути от А до В.
3) Определить кратчайший (и напечатать).
Пункты 2 и 3 не получаются. Приведите (или дайте ссылку) пожалуйста алгоритм нахождения всех возможных путей А-В и кратчайшего.
Ничего толкового не нашел: только стадартный случай, когда надо найти ВЫХОД из лабиринта, а не путь А-В.
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.06.2009, 21:29
Ответы с готовыми решениями:

Поиск кратчайшего пути в лабиринте
Добрый день, знаю два алгоритма. 1. А - стар 2. Волновой Нужен какой нибудь 3... Ссылки...

Поиск кратчайшего пути
Всем доброго времени суток! Скажите, пожалуйста. Есть ли какие-то принципиальные отличия волнового...

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

АСтар поиск кратчайшего пути
Здравствуйте знаю что подобных тем сотни, но я никак не могу разобраться в двух вещах. Я пытаюсь...

Поиск кратчайшего пути лошадью
(p, q)-лошадь - это обобщение обычного шахматного коня. (p, q)-лошадь своим ходом перемещается на p...

5
9h05t
4 / 4 / 0
Регистрация: 07.05.2009
Сообщений: 29
17.06.2009, 19:07 2
Простейший вариант- рекурсивный перебор всех возможных путей с защитой от зацикливания(т.е. самопересечения) , все пути и з в б запоминаеш, выбираеш самый короткий.
Если такого пояснения недостаточно могу привести пример рекурсии, или фрагмент кода по твоей задаче.
0
oler117
0 / 0 / 0
Регистрация: 08.06.2009
Сообщений: 48
17.06.2009, 20:05  [ТС] 3
Спасибо, я уже сделал.
Использовал волновой алгоритм.
0
Talija
0 / 0 / 0
Регистрация: 12.12.2009
Сообщений: 9
12.12.2009, 22:17 4
Цитата Сообщение от oler117 Посмотреть сообщение
Спасибо, я уже сделал.
Использовал волновой алгоритм.
Привет! А ты на чем программировал поиск в лабиринте???? Мне надо реализовать это с помощью java, а я не знаю как=(((
0
oler117
0 / 0 / 0
Регистрация: 08.06.2009
Сообщений: 48
13.12.2009, 13:13  [ТС] 5
Я на VB 6 делал. Нашел код на С++ и просто переписал его на VB
0
just_a_cat
5 / 5 / 1
Регистрация: 16.09.2009
Сообщений: 4
14.01.2010, 23:51 6
я думаю многие скажут спасибо за исходники С++
0
14.01.2010, 23:51
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2010, 23:51

Двунаправленный поиск кратчайшего пути в графах
Никто не встречал реализованный на c\c++ алгоритм? Добавлено через 17 часов 24 минуты помогите...

Поиск кратчайшего пути в матрице или установка факта, что такового не существует
Всем привет!!!я начал решать задачку и у меня не получается, а не получается у меня самое главное...

Алгоритмы кратчайшего пути
Нужен алгоритм нахождения кратчайшего пути между двумя точками (волновой не подходит). Заранее...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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