2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Тип задач на прохождение лабиринта.
Сообщение09.02.2012, 09:27 
В связи с отсутствием достаточных возможностей в средах поддерживающих Исполнителя типа робот
т.е. в Pascal ABC NET и в Лого, решил написать сам программу для интерактивного моделирования
плоских лабиринтов стандартных типов.
Правда даже после этого передо мной 2 пути:
1)решать задачу кратчайшего пути в стандартной постановке - в условиях знания всего графа лабиринта
2)реализовать команды и свойства исполнителя-робот и решать задачу прихода в заданную точку лабиринта любым алгоритмом для исполнителя
Пример графа лабиринта формы параллелограмма
Изображение

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group