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

 

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

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

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

Программа 11.3.5
procedure SelectF2 ( var Ie : PL; co, k : Integer);
var Cr, Nx : PL; begin
new (Ie); Cr := Ie; with IeAdo
begin inf := k; down := nil; right:= nil; end;
if co < N then SelectF2 ( CrA.left, co + 1, 1 ); while k < N do begin k := k + 1;
new (Nx);
CrA.down := Nx;
NxA.inf := k;
NxA.right:= CrA.right;
NxA.down := nil;
Cr := Nx; end;
end;
11.3. ПЕРЕБОРНЫЕ АЛГОРИТМЫ И РЕКУРСИЯ
659
Вызов процедуры SelectF2(Sta,1,1) для фиксированного N приводит к построению графа, который представлен списком, изображенном на рис. 11.6. Искомые кортежи строятся при прохождении всех маршрутов, начинающих-
Sta
inf downright
Рис. 11.6. Граф решений, представленный списком
ся в верине, на котору указвает Sta. остроение кортеа сводится к выписыванию последовательности пометок вершин графа (поля inf) при их посещении согласно следующему правилу: из всех вершин вертикального направления перемещения пометка берется только у последней из них. Построение всех корте ей мо ет рассматриваться как самостоятельная задача отслеивания ну нх маррутов без повторений. Возмо но ее реение рекурсивным методом. При разработке соответствующей программы (это предлагается вполнить самостоятельно) целесообразно не ограничиваться графами, которые получа тся при выполнении процедур SelectF2. Реая задачу для обего случая, мы не только расиряем сферу ее применения (в частности, долно получиться так, что она будет работать и тогда, когда склейка окончаний не предусматривается, можно предусмотреть фильтра-ци реений и т. д.), но и получаем универсальный подход для оперирования
660
11. ,
с графами.
Структура получившегося графа решений вполне регулярна, и можно говорить о построении ее иными методами, нежели те, что были применены вше. Разумеется, это можно (и нужно!) было выяснить на этапе анализа задачи, которй устанавливает принимаемй метод реения. о здесь хотелось бы подчеркнуть другое. Если сравнить различные решения задачи с точки зрения того, как вовлекаются данные в вычисления, то становится ясно, что структура графа отражает именно эти потоки данных, т. е. фиксирует в себе все допустимые с точки зрения задействованных алгоритмов порядки4 доступа к даннм.
Каждый из путей из начальной вершины графа соответствует одному из искомых решений. Ацикличность построенного графа позволяет при построении решений не заботиться о контроле длин проходимых путей. Если отказаться от использования этого свойства, то мо но ее раз произвести склейку графа по вертикальному направлению (см. рис. 11.7а). Поиск решений для нового графа мо ет осуествляться той е программой, которая применима для графов обоих прежних видов (без учета и с учетом совпадений окончаний), если только она контролирует длины проходимых путей. Это принципиально, т. к. новый граф перестает быть ациклическим.
В списочном представлении нового графа оказалось, что все ссылки направо (поле right) имеют одно и то же значение. Зачем же тогда хранить их в каждом элементе? Очевидный ответ на этот вопрос приводит к тому, что требуемую списочную структуру целесообразно преобразовать в простой последовательный список (см. рис. 11.7б). Прежняя программа для его обработки не годится, но из нее легко (да е механически!) мо но построить нову программу, соответствуу измененной структуре даннх.
Содеримое элементов этого списка для реаемой задачи соответствует следованию чисел отрезка натурального ряда, записанного в поле Inf. Поэтому сам такой список становится избыточным: вместо его просмотра более эффективно реализовать непосредственное оперирования с этим отрезком.
это возврат к тому, что бло реализовано в первом или втором реении, которе вовсе не использу т граф. Впрочем, теперь они оказались упрятанными в программе обработки (Handle).
Круг замкнулся. риведенными построениями мы показали, что для ре-
4 В данном случае это слово практически является термином: поток данных задает частичный порядок на них, фиксирующий разрешение доступа к данным: чтодбы данное a стало доступным, нужно обработать все предшествующие ему.
11.4. ЛАБИРИНТ
вві
Sta
Sta'

1 > /
г
2 > /

N X
2
N
...
а)
б)
Рис. 11.7. Два вида графа решений: (а) — список со склеенными вертикалями и (б) — список-последовательность.
1
шаемой задачи переход от рекурсивной программы к рекурсивным данным не дает преимуществ. Но не следует по этой причине считать наши построения излишними: в других случаях подобный переход может быть целесообразным во многих отношениях, и во всяком случае его нужно запомнить как общий прием программирования.
§11.4. ЛАБИРИНТ
В настоящем параграфе приводится иллюстрация метода перебора/генерации вариантов с возвратами, когда требуется найти не все, а одно из возмо нх решений. В качестве области применения метода обсуждается разработка алгоритмов блуждания по лабиринту, т. е. нахождения путей в лабиринте из заданной точки. В учебном плане задача блуждания по лабиринту удобна в нескольких отноениях. Во-первых, она является весьма характерной пере-
662
11. ,
Предыдущая << 1 .. 224 225 226 227 228 229 < 230 > 231 232 233 234 235 236 .. 316 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100