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

 

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

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

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

11.4.3. Абстрактное представление лабиринта
Конкретизируя данное в предыдуем разделе определение изоморфно-сти абсторактных представлений, получаем следующее определение для лабиринтов.
Определение 11.4.1. Два лабиринта называются изоморфными, если меж -ду мно ествами их комнат и дверей мо но установить взаимно-однозначное соответствие, для которого вполняется следуее условие: если дверь соединяет две комнаты одного лабиринта, то соответствующие комнаты другого лабиринта соединяются соответственной дверью. Конец определения 11.4.1.
Это определение позволяет говорить о лабиринтах безотносительно их изобра ений, как о системах комнат с переходами. Такой лабиринт мо ет изобрааться соверенно по-разному в зависимости от того, например, какие цели преследу тся при реении задачи блу дания.
Для иллюстрации на рис. 11.8 предлагаются два изоморфных лабиринта, зрительно совсем не похо их друг на друга.
одобие показанных лабиринтов становится нагляднм, если отразить на их изображениях номера комнат (см. рис. 11.8б). Чтобы подчеркнуть условность изобра ения комнат, стенок и дверей на рис. 11.8б пунктиром показаны разделительные линии между комнатами.
11.4. ЛАБИРИНТ
667
а) Лабиринта без разметки
б) Лабиринта с разметкой
Рис. 11.8. Два изоморфных лабиринта
Задача распознавания подобия лабиринтов интересна, но она не рассматривается в данной книге. Здесь важнее заметить, что для всех подобных лабиринтов нахождение пути между комнатами достигается с помощью одного и того е алгоритма, тогда как построение их графического представления может существенно различаться.
Что нужно для такой унификации решения задачи блуждания?
Абстрактное представление лабиринта — это программистское отражение математического понятия, а конкретное представление — это изображение абстрактного лабиринта. Поскольку пользователь программы поиска пути имеет дело с конкретным представлением, а алгоритм решения форму-
668
11. ,
лируется для абстрактного представления, необходимо иметь возмо ность трансформировать конкретное представление в абстрактное, а также отображать абстрактное решение в изображениях лабиринта.
Таким образом, конкретное представление для задачи о лабиринтах означает, во-первх, выбор конкретной структур данных, реализуей абстрактну структуру комнат, и во-вторых, выбор визуализации абстрактного представления как одного из подобных лабиринтов. Первая часть может оказаться тривиальной, поскольку структура данных, созданная при разработке абстрактного представления, часто без изменений переходит в конкретное, особенно если конкретное не находится под естким давлением ресурсных ограничений либо требований совместимости с какой-то другой системой.
Применительно к задаче о лабиринте можно выделить следующие положения, характеризирующие абстрактное представление лабиринта:
1. набор комнат лабиринта — это двумерный массив Rooms, соседство элементов которого отражает соседство комнат в конкретном представлении лабиринта;
2. комнаты идентифициру тся парой индексов массива Rooms;
3. из комнаты можно перейти только в одну из четырех соседних, индексы которх в массиве отлича тся на единицу, а число дверей комнат — не более четрех (следствие предыдуих поло ений);
4. все комнаты лабиринта стандартного одинакового размера, максимально возмо ного для правильного (полного и без пересечений) покрытия любых комнат конкретного представления (такое покрытие рассматривается как разбиение больших комнат на стандартные с соответствую-
ими дверями);
5. в качестве стенок рассматриваются запреты на переходы к соседним комнатам, выставляемые принудительно как атрибуты комнат. Поскольку для двух соседних комнат достаточно указать запрет лиь у одной из них, стандартизуется, что атрибуты запрета перехода вставля тся в направлениях роста идентифицируих индексов: запрет на переход вправо (Rt) и запрет на переход вниз (Dn);
6. для унификации вычисления возмо ности перейти влево (противоположное Rt направление Lf) и вверх (противоположное Dn направление Up), массив Rooms дополняется рядом и колонкой фиктивных комнат
11.4. ЛАБИРИНТ
669
с нулевым соответствующим индексом. Этим комнатам принудительно задаются, соответственно, атрибуты запрета на переход Dn для ряда и запрета на переход Rt для колонки, соответственно. х нельзя указ -вать в качестве начальной или конечной комнат для блу дания;
7. начальная и конечная комнаты задаются как пары индексов, соответственно, bX, bY и eX, eY;
8. искомый путь в лабиринте представляется массивом Way, который содержит пары индексов, идентифицирующих комнаты, и переменной Lway — длиной пути;
9. для отра ения хода вычислительного процесса поиска пути в лабиринте каждая комната снабжается числовым атрибутом Inf, который кодирует состояние комната. То, как определять состояния, непосредственно связано с алгоритмом, работающим с абстрактным представлением. Например, ненулевые значения этого атрибута могут указывать на номер комнаты в последовательности искомого пути, что нацеливает использование атрибута Inf на изобра ение лабиринта с пометками у комнат, выделяими искомый путь.
Предыдущая << 1 .. 227 228 229 230 231 232 < 233 > 234 235 236 237 238 239 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100