Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Непейвода Н.Н. -> "Основания программирования " -> 231

Основания программирования - Непейвода Н.Н.

Непейвода Н.Н., Скопин И.Н. Основания программирования — Институт компьютерных исследований , 2002. — 919 c.
Скачать (прямая ссылка): osnovanprogramm2002.pdf
Предыдущая << 1 .. 225 226 227 228 229 230 < 231 > 232 233 234 235 236 237 .. 316 >> Следующая

борной задачей, требуей просмотра вариантов с возвратами. Во-вторых, в ней легко усмотреть связь с задачей закраски области (§ 11.2). Попытка применить уже наработанный подход к решению оказывается поучительной. В-третьих, на примере данной задачи мо но проследить один ванй технологический подход к реени программистских задач, связаннй с разбиением задачи на подзадачи.
11.4.1. Блуждание по лабиринту и закраска области
Задача закраски области мо ет быть достаточно просто переформулирована для случая блу дания по лабиринту, когда требуется найти все точки области, достижимые из заданной точки. В такой постановке новая задача допускает решение, ничем не отличающееся от решения задачи о закраске.
самом деле, возмо ность перехода из одной точки лабиринта в другу пол-ность соответствует поняти соседства точек, и как следствие, закраску соседней точки мо но трактовать как переход в нее, а осуествление закраски всей области — как отметку всех последовательно достижимых точек. Однако если слегка изменить постановку задачи блуждания, потребовав определить не суествование пути, а сам путь из одной точки в другу , то об-нару ится, что алгоритм закраски области потребует корректировки. Кстати сказать, новая постановка более естественна для задачи блу дания.
очему для нахо дения пути из одной точки в другу подход, представленный в предыдущем разделе, не годится? Дело в том, что он не фиксирует последовательности перемеений по точкам, более того, для закраски принципиально, что одна и та е точка посеается не один раз, а столько, сколько ну но для закраски всех соседствуих с ней точек. ри реении новой е задачи ну но научиться отвергать (искл чать из рассмотрения) точки, переходы из которых ведут в тупики (не только зацикливание). В прежней задаче отвергались лиь граничне точки, что сохраняется и для задачи блу дания, и те точки, соседи которх леат на границе области или у е закрае-ны. ными словами, определить, ну на ли конкретная точка для продол е-ния процесса (для рекурсивного взова процедуры), мо но бло локально. Теперь же, составляя последовательность точек (последовательности, если требуется найти разне пути), представляей искомый путь (пути), отвергать точки ну но после исследования, ведет ли из нее путь в точку назначения. Весьма поучительно попробовать попытаться воспользоваться преним алгоритмом для реения данной задачи непосредственно и увидеть его дефекты.
Есть еще одна особенность новой задачи, важная уже на уровне уточ-
11.4. ЛАБИРИНТ
вв3
нения постановки: при блу дании по лабиринту для кадой точки всегда можно выделить множество очевидно достижимых из нее точек. В него, к примеру, попадают все соседние неграничные точки, весь луч из данной точки до пересечения его с границей (интуитивное представление видимости).
оэтому мо но ввести понятие мно ества точек, очевидно достиимх из данной. чевидно достиимые точки определять мо но по-разному, но при выполнении одного условия: для поиска пути в лабиринте в качестве начальной (конечной) точки выбор какой-либо из них в множестве очевидно дости-
имх точек безразличен.
нми словами, для блу дания в лабиринте все мно ества взаимно очевидно достиимх точек группиру тся в классы эквивалентности, и вместо точечного пространства, аналогичного области закраски, в задачах о лабиринте нужно оперировать с набором классов эквивалентности. Для определенности будем называть такие классы комнатами, искусственно устанавливая границ комнат как окончания очевидно суествуего перехода ме -ду точками. Эти границы либо совпадают с фактическими границами лабиринтного пространства, которые в дальнейшем называются стенами, либо добавлены для разграничения комнат, связанных возможным переходом, — двери. В результате в качестве начала и конца искомого пути указываются не точки, а комнат , а сам путь рассматривается как последовательность комнат.
Таким образом, задача о лабиринте становится дискретной. В ней можно выделить в ней два независимых аспекта:
• графическое отображение лабиринта и
• нахождение пути в нем.
Следует заметить, что и при решении задачи раскраски фактически был осуествлен переход к дискретной постановке: непрерывность границ области рассматривалась как наличие среди соседей каждой граничной точки других граничнх точек. В сво очередь, именно это позволило разработать универсальный алгоритм, не зависяий от (аналитического) вида границ области закраски (правда, у этого алгоритма есть недостаток: он очень чувствителен к непрервности отобра ения границы области на экране, т. е. неустойчив к пропуску граничных пикселей). В задаче раскраски не было необходимости выделять аспект графического отобра ения, она формулируется для заданной, т. е. у е изобра енной области. Таким образом, дискретное представление области закраски остается реализационнм.
664
11. ,
ля блу дания по лабиринту ситуация иная. Задача поиска пути мо ет ставиться для изображенного лабиринта, но, тем не менее, и в этом случае подразумевается, что ее решение должно формулироваться как последовательность комнат, дверей, а не на уровне точечного представления. Кроме того, естественно предполагать, что реение, полученное для одного лабиринта, ока ется тем е самым для лбого другого, подобного ему лабиринта (вопросы, связанные с подобием, обсуждаются в следующем параграфе).
Предыдущая << 1 .. 225 226 227 228 229 230 < 231 > 232 233 234 235 236 237 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100