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

[Atilla]

Надо найти кратчайший путь в лабиринте. Сделал поиск в глубину, но работает слишком долго.
Есть ли другие способы поиска, чтобы побыстрее работало?

P. S. И не посоветуете форумы, где более уместны такие вопросы?

[[DarkNet]Alpha]

http://ithappens.ru/story/825

[Atilla]

Пользоваться заливкой по экрану - это слишком круто для меня:)
Мне бы что-то полегче что ли...

[ArcFi]

http://www.google.com/search?q=кратчайший+путь+в+лабиринте
М?..

[Atilla]

http://www.google.com/search?q=кратчайший+путь+в+лабиринте
М?..

Мммм... Очень интересный сайт. И как я только о нём до этого не знал...

[truegeek]

http://www.google.com/search?q=кратчайший+путь+в+лабиринте
М?..

Мммм... Очень интересный сайт. И как я только о нём до этого не знал...

а пора бы уже

[inkblack]

А для чего? Искать кратчайший путь?
В чем состоит задача?

[ChaosWarrior]

(Нажмите, чтобы показать/скрыть)

http://www.google.com/search?q=кратчайший+путь+в+лабиринте
М?..

Простите, но вы малость неадекватны. Впрочем, а чего удивляться, если и на буржуйском форуме читаю вопрос: "у меня в conky не влазят несколько строк, как увеличить высоту его окна или сделать так, чтобы она устанавливалась автоматически". Ответ: "Что вы имели ввиду?". И все, больше человек ничего спрашивать не будет. И это типично.

О, и как я не заметил:

А для чего? Искать кратчайший путь? В чем состоит задача?

И не смешно даже. Ага, зайти на форум автомобилистов с вопросом "почему у меня вторая передача через раз включается". Ответом должно быть: "Какая передача? Программа телепередач?"
Не засоряйте эфир, господа, и помните, что даже в Яндексе найдется далеко не все; более того из-за таких необычайно содержательных ответов на первые места в выдаче Google уже попадают ответы "ищите в Google".

Соломоново решение... но не для поставленной задачи.

http://ithappens.ru/story/825

Вам нужно сделать следующее:

Если лабиринт такой все немного проще: можно двигаться только вперед, назад, вверх и вниз. А там либо стенка, либо проход, либо выход. Либо вернулись к началу, что тоже надо обработать. Можно сделать так, чтобы попытка пройти в начало соответствовало "стенка" и все будет в порядке.  Надо помнить еще вариант "нет выхода". Рекурсия в помощь. По идее, должен образоваться ветвящийся список всех возможных путей прохода, там уже встанет проблема выбора кратчайшего, это уже тупо подсчетом и перебором. И да, мне кажется, любой плоский лабиринт можно привести в "квадратный" вид.

[Atilla]

Да, лабиринт именно такой.
Я уже сделал примерно такой ход решения. Но такая программа работает нормально только при небольших матрицах (~100х100). При увеличении матрицы хотя бы до 200х200 время нормально так возрастает до неприемлемого уровня (до секунд 2-2,5).
В чём и заключается вопрос: нет ли более быстрой программы для поиска пути? (В замечательном сайте google.com к сожалению представлен только медленный метод решения)

[ChaosWarrior]

Код на стол.

[[DarkNet]Alpha]

Попробовать что ли тоже лабиринт накодить...

[vadim-nsk]

 а что нельзя через графы решить? алгоритмы дейкстра, беллмана-форда, флойда-уоршелла . поиск кратчайшего пути между двумя вершинами разве не рулят?

[truegeek]

а что нельзя через графы решить? алгоритмы дейкстра, беллмана-форда, флойда-уоршелла . поиск кратчайшего пути между двумя вершинами разве не рулят?

конечно можно, но нужно же учить матчасть, а хочется уже побыстрее велосипед изобрести

может наталкнет на мысли
http://www.ega-math.narod.ru/Nquant/Maze.htm

[ChaosWarrior]

Увы, решения, отличного от уже озвученного, там нет.

[armad]

Волновой алгоритм - Построение крaтчaйшего мaршрутa (мне кажется очень удачным)
http://www.codenet.ru/progr/alg/way.php