Естественные науки

Кто знает где найти алгоритмы для поиска путей в лабиринтах?

Есть в теории графов алгоритм который позволяет обойти весь лабиринт проедя по каждому пути не более двух раз. Смысл: когда доходите до перекрестка отмечаете по какому пути пришли, далее отмечаете любой из ранее непройденных путей и идете по нему. А если таких нет идете по любому пути который был входящим в этот перекресток (т. е. он ранее пройден, но не при движении из этого перекрестка, а наоборот при движении в этот перекресток) . Дойдя до следующего перекрестка повторяете тоже самое. Если цель найти выход (и он есть, ну и достаточно времени) то вы к нему выйдете. Если нужно просто обойти весь лабиринт, то когда вы попали в перекресток из которого нет ни непройденных путей, ни путей пройденных один раз (входящих) то значит вы обошли весь лабиринт и вернулись в исходную точку (ту с которой начали отмечать пути) .

Если где будете читать, обратите внимание я немного накрутил с терминологией. В теории графов, то что я в описании называл "путями" называется ребрами графа, а "перекрестки" - вершинами графа.
Константин Лахно
Константин Лахно
1 963
Лучший ответ
Полностью присоединяюсь к ответу Умера Аджегиряева. Я ему уже дал +5. Действительно, алгоритм не нужен. Идите вдоль стены (не важно правой или левой) , постоянно касаясь её рукой, и непременно выберетесь. Проверено мною в старых компьютерных играх на ПК прежних поколений.
А*
Ардак ********
24 494
Ну собственно, простейший можно придумать самому по схеме:
Если *условие* тогда *действие 1*;
Иначе *действие 2*;
КонецЕсли;
Bonnie Nightmare
Bonnie Nightmare
3 787
ето не алгоритмуеться)
Тома
Тома
612
есть такое правило держаться вдоль стенки или правойи или левой стороны. то есть на все повороты сворачивать только на одну сторону. из этого следует что весь лабиринт вы может не обйдёте, но зато не заблудитесь :) и заодно чертить схему.

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