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

Некоторые алгоритмы для прохождения лабиринтов с неизвестными препятствиями:

• Правило «одной руки». myrobot.ru cyberleninka.ru Суть алгоритма в том, чтобы, двигаясь по лабиринту, всё время касаться правой или левой рукой его стены. myrobot.ru cyberleninka.ru Недостаток метода в том, что нужно пройти долгий путь, заходя во все тупики, и нельзя найти выход, если есть отдельно стоящие стены. cyberleninka.ru
• Алгоритм Люка-Тремо. myrobot.ru cyberleninka.ru Из любой точки лабиринта нужно сделать отметку на его стене (крест) и двигаться в произвольном направлении до тупика или перекрёстка. myrobot.ru cyberleninka.ru В первом случае нужно вернуться назад, поставить второй крест и идти в направлении, не пройденном ни разу или пройденном один раз. myrobot.ru cyberleninka.ru Во втором — идти по произвольному направлению, отмечая каждый перекрёсток на входе и на выходе одним крестом. myrobot.ru cyberleninka.ru Если на перекрёстке один крест уже имеется, то следует идти новым путём, если нет — то пройденным путём, отметив его вторым крестом. myrobot.ru cyberleninka.ru
• Поиск в ширину. cyberleninka.ru Алгоритм выполняет исследование равномерно во всех направлениях. cyberleninka.ru Нужно отслеживать состояние расширяющегося кольца, которое называется границей. cyberleninka.ru Повторять шаги, пока граница не окажется пустой: выбирать и удалять точку из границы, помечать точку как посещённую, расширять границу, глядя на её соседей. cyberleninka.ru
• Алгоритм маршрутизации в лабиринте. en.wikipedia.org Метод позволяет найти путь между любыми двумя точками лабиринта. en.wikipedia.org Алгоритм может обнаруживать, когда между источником и пунктом назначения нет пути. en.wikipedia.org