Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 29
Текст из файла (страница 29)
Теперь легко построить рекурсивную схему. Четыре составляюшпе фигуры вновь обозначаются А, В, С и О, а соединительные линии рисуются явно. Заметим, что четыре рекурсивные кривые действительно одинаковы с точностью до поворота на 90'. Основной образ кривых Серпинского следующий: (3.2() а объединенные рекурсивные фигуры строятся по таким схемам: А: А г В .=.~В . т А В Вв С(гА гВ С;С В» — -В 'С Вп Э 'А () С'--Ю (3.22) (Двойные стрелки обозначают линии двойной длины.) ргеегппг В!егр1п«Ь! (рг,оигри1); ( иэображение кривых Сераинского порядка от 1 до л ) сопМ п == 4; ЬО = 512; гаг ЬЬ,х,у,хО,уО: 1а1екгг; р~: 61е е1 1а1ексг; ргоседпге А(!': шгекег); Ъее1пК ! > О 1Ъеп Ъеп1п А(! — 1); х:== х+Ь; у: у — Ь; р(о1; В(1--$); Х:= х + 2«Ь; р1о1; Ю(! — 1); х;== х'+Ь,' у:=- у+Ь; р!о1; А(1 — 1) епд епа; ргеседпге В(1: оиссгг)1 Ъее!и К ! > О 1Ъеп Ъеп1п В(! — !); х:= х — Ь; у:== у — Ь; р1о1; С(! — 1); у:= у — 2«Ь; р1 1; А(! — 1); х:= — х ~-Ь; у:=- у — Ь; р1о1; В(! — 1) епд епд; ргаседпге С(1: шгссег); Ъеп)п И' г > О гЪеп Ъеп)п С(1 — 1); х: х — Ь; у:= у+Ь; р1о1; В(1 — 1); х: х — 2«Ь; р!ог; В(! — 1); х: х — Ь; у: у — Ь; р1о1; С(! — 1) епд епд; ргоссдпге Ю(1; 1я1екгг): Ъсс1п 1г ( > О гЪеп Ъеп!п Ю(! — 1); х; х+Ь; У:=- У+Ь; Р!о11 А(! — 3); у:= у — , '2«Ь; р1о1; С(1 — )); х:= х — Ь; у: у+Ь; р)о11 З(! — ) епд епд; Ъед)п а1аг1р!о1: 1; О;!г:.=.
ЬО д)г 4; хО:.== 2«Ь; уО: Э«Ь; гепеаФ 1::=- 1-,'-1; хО:=-. хΠ— Ь; Ь:= Ь д(г 2; уО:= уО+Ь; х:.=- хО; у:==- уО; негр!ог; А(1); х:.=- х+Ь; у:= у-Ь; р!ог; 162 8. Рекурсивные авгоргплы В(г); х:= х — Ь; у:= у — Ь,' р1ог; С(г); х .'= х — Ь; у:= у+Ь; р(ог; О(г) х:= х+Ь; у:= у+Ь; р7ог; шпйг =я; елогр7от епй . Программа 3.2. Крггвые Серпипокого, Используя те же примитивы и в случае кривых Гильберта, ную схему легко преобразовать снвный алгоритм: для операций построения, что приведенную выше рекурсивв (прямо и косвенно) рекур- ргвсеввге А(г'; глгейег) „' )геа)п Ы г' > 0 1)геп Ьея(п А(г — 1); х:= Щ-1); х:= Щ-1); х:= А(г — 1) х+Ь; у: 1-Ь; р1о1; х+2вй) р1ог' (3.23) х+Ь,' у гыв у+Ь) р(ор' епа епй Эта процедура соответствует первой строке рекурсивной схе. мы (3.22).
Процедуры, соответствующие фигурам В, С и О, строятся аналогично. Основная программа строится по схеме (3.21), Оиа должна установить начальные значения для координат рисунка н задать длину единичной линии /г в зависимости от формата бумаги, как показано в программе 3.2. Результат работы этой программы прн и = 4 показан на рпс. 3.7. Заметим, что Бо не рисуется. Как можно убедиться, в этих примерах рекурсия используется весьма элегантно. Правильность программ легко следует пз их структуры и схем построения, Кроме того, использование явного параметра уровня г в соответствии со схемой (3.5) гарантирует окончание программ, так как глубина рекурсии не может быть больше и.
По сравнению с этой рекурсивной формулировкой эквивалентные программы, которые избегают явного использования рекурсии, чрезвычайно сложны и трудны для понимания. Мы предлагаем читателю самому в этом убедиться, попытавшись разобраться в программах, приведенных в [3.31. 163 8,4. Ллворигмы с вовврогом Рис. З.т. Крнвые Серповского 5н .... ое Заь АПГОРМТМЫ С ВОЗВРАТОМ Особенно интересный раздел программирования — это задачи из облас|н «искусственного интеллекта» Здесь нужно строить алгос; тмы, которые находят решение определенной задачи и" по фиксированным правилам вычисления, а мето; ом проб и ошибок.
Обычно процесс проб и ошибок разделяется на отдельные подзадачи. Часто эти подзадачи наиболее естественно опнсываютсн с помошью рекурсии. Процесс проб и ошибок можно рассматривать в обгцем аиде как попсковый процесс, который постепенно строит и просматривает (а также обрезает) дерево подзадач. Во многих случаях такие деревья поиска растут очень быстро, обычно экспопепцпально, в зависимости от заданного параметра. Соответственно увеличивается стоимость поиска.
Часто дерево поиска можно обрезать, используя только эвристические соображения, н тем самым сводить количество вычислений к рану и вы и предел ам. 3. Рекурсивные ел«ориг»ы Здесь мы не собираемся обсуждать общие эврпстнч«: ве правила. Предмет этой главы — общий принцип разбиения таких задач на подзадачи и использование в них рекурсии. Вначале мы продемонстрируем основные принципы на хо. рошо известном примере — задаче о ходе коня. Дана доска и Хи, содержащая и' полей. Копь, козорый ходит согласно шахматным правилам, помещается на поле с начальными координатами хе, уы Нужно покрыть всю доску ходами коня, т. е. вычислить обход доски, если он существует, пз п' — ! ходов, такой.
что каждое поле посещается ровно один раз. Очевидно, что задачу покрытия и' полей можно свести к более простой: или выполнить очередной ход, илп устава. вить, что никакой ход невозможен. Поэтому мы буем строить алгорнтм, который пытается сделать очередной ход. Первая попытка выглядит так: ргосебнге попытка следующего хода; Ьер(п ин~щиаиия выборки ходов; гереа1 выбор слвдуюи(гго возможного хода из списка осврвдных ходов; И он приемлем 1Ьеп Ьеи(п запись хода; И доска нв заполнена 1Ьеп (3.24) Ьед(п попытка следующего хода; И неудача 1Ьеп стирание предыдущего хода епб епд нп(И (ход был удачным! ~l (нгт других возможных ходов) епб Если мы хотим более точно описать этот алгоритм, то должны выбрать некоторое представление для данных. Очевидно, что доску можно представить в виде матрицы, скажем, Ь.
Введем также тип индексирующих значений; 1уре(пдвх= 1..п; тат гт ". аггау(тс(ех, тс(вх! о1 (гнвуег (3. 23) Таи как мы хотим сохранять историю последовательного «захвата» доски, то мы будем представлять каждое поле доски целым числом, а не булевским значением, которое отражало бы просто факт занятия поля. Очевидно, можно остановиться на таких соглашениях: 61х, у1=-О: поле (х, у) не посещалось, (3.26) гс!х, у)=с поле (х, у) посещалось на с-и ходу (1~(~~аз).
Теперь нужно выбрать подходящие параметры. Оиидолжлы определять начальные условия для следующего хода, а азь Алгоритмы с возвратом ргосел!пге и! (ь': (пгееег; х,>'. 1пл(ех; чаг у: Ьоо1еап); чаг и,о: ьпгстсг; 111: Ьоо!еап; Ъеа!и иниииаггия выбора ходов; гереа! пусгпь и, ь — координаты следующего хода, определяемого шахлгатными правилами; !1(1(и п) уь (1(егмп) 1ь (А[и,о]=О) !)ьеп 1ьеа!и й[и,о];.= 1; !1 г < гдг(п) !!ьеп !ьеа!п ггу(!+1,и,о,.д1 ); !à — у1 !!ьеп 1ь[цо):= О епд е!зе д1;= ггие епь! пп61 д! Ч (нет других ходов); д;= д1 епд (3.27) Еще один этап уточнения, и мы напишем программу уже п~ лностью на нашем языке программирования. Надо заметить, что до сих пор программа разрабатывалась совершенно независимо от правил хода коня.
Мы вполне умышленно откладывалп рассмотрение частных особенностей аадачи. Но теперь пора обратить на них внимание. Если задана начальная пара координат (х, у), то имеется восемь возможных координат (и, о) следующего хода. На рис. 8.8 они пронумерованы от 1 до 8. таь ке сообщать о его удаче или неудаче. 11ервая задача выполняется заданием координат поля х, у, с которого делается ход, а также номером хода ! (для его фиксации).
Для решения второй задачи нужен булевскнй параметр-результат: у = 1гие означает удачу, д =- [а1зе — неудачу. Какие операторы можно теперь уточнить на основе этих решений? Разумеется, «доска не заполнена» можно выразить как «1«. и'», Кроме ього, если ввести две локальные переменные и и о для обозначения координат возможного хода, определяемых по правилам хода коня, то предикат «приемлем» можно выразить как логическую конъюнкцию двух условий. чтобы новое поле находилось на доске, т.
е, 1 ( и - и и ! ~ о ~ п, и чтобы оно ранее пе посещалось, т. е. )ь [и, 1ь] = =-О. Фиксация допустимого хода выполняется с помощью присваивания 1ь[и, о]: = ь, а отмена хода (стирание) — как 6 [и. и]:= О. Если при рекурсивном вызове этого алгоритма в качестве параметра-результата передается локальная переменная д1, то вместо «ход был удачным» можно подставить л)1. Таким образом, мы приходим к программе (3.27); )66 3. Рекурсивньм алгоритмы Получать и, и пз х, у просто — будем прибавлять к пим разности координат, помещенные либо в массиве пар разностей, либо в двух массивах отдельных разностей.
Пусть эти массивы обозначены через а и Ь и соответствующим образом инициированы. Для нумерации следующего возможного хода можно вспользовать индекс й. Подробности показаны в программе 3.3. 1зекурсивная пропедура вызь!вается Рвс. 3.8. Восемь возможных холов коня. в первый раз с параметрами хо, уо — коордниатамн пос!я, с которого начинается обход. Этому полю присваивается значение 1, осгальные поля маркируются как свободные: л(хв Уо1:= 1; Ггу(2, ха, Ум г7) Нс следует упускать еще одну деталь. Переменная й(и, о) су цествует лишь в том случае, когда и и о находятся внутри границ массива ! ... и.
Следовательно. выражение в (3.27), подставленное вместо «он приемлема в (3.24), осмысленно, только если его первые две составлязощпе истинны. В программе 3.3 это условие подходяп!им образом переформулнровано, кроме того, двойное отношение ! и =-. н заменено выражением и 1п 11, 2, ..., л], которое прп достаточно малых п обычно бывает более эффективным (см. разд. !.!0.3). В табл. 3.! приведены решения, полученные при исходных позициях (1,1), (3,3) для и = 5 н (1,1) для и =-б.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
