0 / 0 / 1
Регистрация: 19.10.2014
Сообщений: 40
|
||||||||||||||||
1 | ||||||||||||||||
Как найти кратчайший путь в лабиринте?20.04.2015, 18:48. Показов 6436. Ответов 4
Метки нет (Все метки)
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить.
Есть 2 вектора:
После прохода волнового алгоритма лабиринт выглядит так: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 8 9 10 11 12 13 14 15 16 17 0 0 6 7 8 9 10 11 12 13 14 15 16 0 0 5 6 7 8 9 10 11 12 13 14 15 0 0 4 5 6 7 8 9 10 11 12 13 14 0 2 3 4 5 6 7 8 9 10 11 12 0 15 1 0 4 5 6 7 8 9 10 11 0 13 14 2 0 5 5 6 7 8 9 10 11 0 14 14 0 0 6 6 6 7 8 9 10 11 0 15 0 0 0 7 7 7 7 8 9 10 11 0 15 0 0 0 8 8 8 8 8 9 10 11 0 14 0 0 0 9 9 9 9 9 9 10 11 12 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - стена Подскажите, как найти кратчайший путь?
0
|
20.04.2015, 18:48 | |
Ответы с готовыми решениями:
4
Найти кратчайший путь в лабиринте, который представлен в виде составного куба заданного размера Как найти кратчайший путь? Как найти НЕ Кратчайший путь в графе ? Найти кратчайший путь |
Модератор
|
|
20.04.2015, 18:59 | 2 |
Путь ищем назад, из 17 точки. Находим минимальную вокруг. Если их несколько - как здесь две 16 - то надо ветвится и проверять по обоим вариантам. Когда в одной из веток, на том же шаге, находится число меньшее чем в других - другие ветки удаляются.
0
|
0 / 0 / 1
Регистрация: 19.10.2014
Сообщений: 40
|
|
20.04.2015, 20:33 [ТС] | 3 |
конечная точка:
int finishX=12; int finishY=6; Так и делал, но путь не всегда самый короткий получается и решение не оптимально(
0
|
101 / 101 / 39
Регистрация: 17.04.2011
Сообщений: 554
|
|
20.04.2015, 21:20 | 4 |
Есть же алгоритмы поиска пути
Добавлено через 43 секунды https://ru.wikipedia.org/wiki/... F%F3%F2%E8 Добавлено через 53 секунды вот в лабиринтеhttp://habrahabr.ru/post/198266/ Добавлено через 57 секунд https://ru.wikipedia.org/wiki/... %EC_%CB%E8
0
|
21.04.2015, 15:20 | 5 |
0
|
21.04.2015, 15:20 | |
21.04.2015, 15:20 | |
Помогаю со студенческими работами здесь
5
Найти кратчайший путь из вершины u в вершину v Найти кратчайший путь, без массивов Найти самый кратчайший путь в массиве Найти кратчайший путь шахматного короля Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |