#1 18.08.09 22:51
Задачи на графах, метод "замазывания тупиков в лабиринтах"
В НГУ на ФИТе среди экзаменационных вопросов по программированию есть вопрос по этому методу.
Гугл на запросы со словами "граф программирование метод замазывание тупик лабиринт" выдает рассказы, как граф Рудольф блуждал по лабиринтам и ни слова про программирование.
Я конечно предполагаю, что это удаление ребер, которые ведут к тупиковому варианту, но хотелось бы поточнее узнать, что там препод имел в виду.
Может, кто слышал о таком методе?
p.s. пишу в программирование, потому что программистам это близко и ради соответствия тематики могу попросить программу на чем-нибудь Си-подобном с реализацией этого метода :)
Offline
#2 19.08.09 12:15
Re: Задачи на графах, метод "замазывания тупиков в лабиринтах"
http://en.wikipedia.org/wiki/Maze_solving_algorithm
Dead-end filling
Dead-end filling is an algorithm for solving mazes that looks at the entire maze at once. It can be used for solving mazes on paper or with a computer program, but it is not useful to a person inside an unknown maze. The method is to 1) find all of the dead-ends in the maze, and then 2) "fill in" the path from each dead-end until the first junction met. A video of dead-end filling in action can be seen here: [1].
Dead-end filling cannot accidentally "cut off" the start from the finish since each step of the process preserves the topology of the maze. Furthermore, the process won't stop "too soon" since the end result cannot contain any dead-ends. Thus if dead-end filling is done on a perfect maze (maze with no loops), then only the solution will remain. If it is done on a partially braid maze (maze with some loops), then every possible solution will remain but nothing more. [2]
Offline
#3 19.08.09 15:28
Re: Задачи на графах, метод "замазывания тупиков в лабиринтах"
Thank you very much) That's quite what I need)
Next time I'll think of using English in Google before turning to other people)
Offline
#6 09.09.09 10:24
Re: Задачи на графах, метод "замазывания тупиков в лабиринтах"
)))
Метод замазывания тупиков в лабиринтах - это алгоритм для поиска пути в лабиринте в случае, когда есть возможность увидеть лабиринт целиком. Его можно использовать для поиска пути на бумаге или в компьютерной программе, но не для поиска пути человеком, находящимся в лабиринте.
Метод заключается в следующем:
1) Найти все тупики в лабиринте.
2) "Замазать" путь от каждого тупика до первого перекрестка от него. Видео можно посмотреть здесь: [1] (в источнике наверно и правда есть ссылка, прим. Kosh_Mar)
Метод замазывания тупиков в лабиринтах не может случайно отрезать выход от начала пути, т.к. каждый шаг сохраняет топологию лабиринта (топология - раздел геометрии, для коготорого не важны размеры, а важны лишь связи и непрерывность, т.е. непрерывную линию метод не замажет, прим. Kosh_Mar). Более того, процесс не остановится раньше, чем нужно, т.к. конечный результат не может содержать тупиков. Таким образом, если алгоритм замазывания тупиков завершен в идеальном лабиринте (лабиринте без циклов), то останется только решение. Если алгоритм применять к лабиринту с циклами, то останутся все возможные решения и ничего лишнего.
faeton написал(а):
Dead-end filling- типа смертный конец Филинни?)
да-да, именно об этом идет речь))
Исправлено Kosh_Mar (09.09.09 10:25)
Offline
