Это задача теории графов. Лабиринт представляется усеченным графом-решеткой. (центр каждой клетки – вершина графа.. Наличие стенки – отсутствие ребра). Возможные варианты постановки – пространственная решетка (имитация кристаллической решетки с потерянными связями)
Возможны также решетки гексагональные и типа гексагональной призмы
задача о кратчайшем маршруте из точки An в Ak включает:
1)анализ достижимости, методом разбиения графа на компоненты связности.
2)поиск маршрута (кратчайшего маршрута) .Возможные методы: разновидности перебора с возвратом ,метод поиска в глубину,волновой алгоритм.
Указанные методы основаны на анализе всего графа ,т.е. либо матрицы инцидентности либо матрицы
смежности. В то же время интересна возможность определения маршрута программой исполнителя (робота).
На уроках информатики и ЕГЭ иногда предлагаются задачи поиска маршрута конкретного графа с записью в виде программы для исполнителя (например на Лого или Pascal ABC NET). Например для лабиринта
Для таких типов задач известны методы обхода лабиринта.
1) правило "правой руки: Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа. Если прохода нет - впереди стена - робот поворачивает налево. Если прохода снова нет, он еще раз поворачтвает налево, таким обр разворачиваясь на 180 град, и идет в обратном направлении
Применимо только для односвязных лабиринтов т.е. tсли изв, что у лабиринта нет отдельно стоящих стенок, т е нет замкнутых маршрутов, по кот можно возвратиться в исх точку,
2) алгоритм Люка-Тремо.: выйдя из любой т лабиринта, н сделать отметку на его стене (крест) и двиг в произв направлении до тупика или перекрестка; в 1 сл вернуться назад, поставить 2й крест, укажет, что путь пройден дважды - туда и назад, и идти в направл, не пройд ни разу, или пройд один раз; во 2м - идти по произв направл, отмечая каждый перекр на входе и на выходе 1 крестом; если на перекр один крест уже имеется, то след идти новым путем, если нет - то пройд путем, отметив его 2м крестом
Алгоритм Люка-Тремо, по-видимому также не может анализировать односвязность графа и принадлежность начальной и конечной точки к одной компоненте и не может быть использован для поиска кратчайшего маршрута.
Вопрос. Возможна ли реализация любой разновидности алгоритма кратчайшего пути в среде исполнителя? Т.е в задаче с неполной информацией, командами типа
Вверх 1 шаг Вниз 1 шаг, Влево 1 шаг, Вправо 1 шаг.
И свойствами Препятствие спереди Препятствие сзади Препятствие слева, Препятствие справа
