Главная Промышленная автоматика.

теперь используется для хранения части пути. Теперь поде left ячейки (1) указывает назад, а не вперед по пути; однако мы восстановим этот указатель, когда поиск в глубину перейдет с ячейки (2) обратно на ячейку (1). Аналогично, в ячейке (2) значение поля back равно R, а правое поде указывает в обратном направлении на ячейку (1), а не вперед на ячейку (3), как это показано на рис. 12.3, а. □

При осуществлении поиска в глубину выполняются три основных шага.

1. Продвижение вперед. Есди мы определили, что текущая ячейка имеет один иди несколько ненулевых указателей, нужно перейти на первый из них, т.е. следовать указателю в поде left иди, есди такового не имеется, - указателю в поде right. Теперь надо преобразовать ячейку, на ксл-орую указывает текущая ячейка, в "новую" текущую, а "старую" текущую ячейку - в предыдущую. Чтобы облегчить поиск обратного пути, нужно сделать так, чтобы указатель, ксл-орому мы только что следовали, теперь указывал на прежнюю предыдущую ячейку. Эти изменения показаны на рис. 12.4,а в предположении, что отслеживался левый указатель. На этом рисунке "старые" указатели показаны сплошными линиями, а "новые" - пунктирными.

2. Переключение. Есди мы определили, что ячейки, исходящие из текущей ячейки, уже все просмсл-рены (иди, например, текущая ячейка может содержать только атомы, иди может быть уже помйченной), то обращаемся к полю back предыдущей ячейки. Есди его значение равно L, а поде right этой ячейки содержит ненулевой указатель на какую-то ячейку С, тогда делаем С текущей ячейкой, в то время как статус предыдущей ячейки остается неизменным. Но значение поля back предыдушей ячейки устанавливается равным R, а левый указатель в этой ячейке устанавливаем так, чтобы он указывал на прежнюю текущую ячейку. Чтобы отследить и сохранить путь от предыдущей ячейки обратно к ячейке source, надо сделать так, чтобы указатель на ячейку С в поде right предыдущей ячейки теперь указывал туда, куда указывал ранее ее левый указатель. Все эти изменения показаны на рис. 12.4, б.

3. Отход. Есди мы определили, что ячейки, исходящие из текущей ячейки, уже просмотрены, но значение поля back предыдущей ячейки равно R иди L, а поде right содержит атом иди нудь-указатедь, значит, мы уже просмсл-реди все ячейки, исходящие из предыдушей ячейки. Тогда осуществляется отход, при ксл-ором предыдущая ячейка становится текущей, а следующая ячейка вдоль пути от предыдущей ячейки к ячейке source - новой предыдущей ячейкой. Эти изменения показаны на рис. 12.4, в (здесь значение поля back предыдущей ячейки равно R).

Нетрудно заметить, что каждый шаг, показанный на рис. 12,4, можно рассматривать как одновременную циклическую перестановку трех указателей. Например, на рис. 12.4, а мы одновременно заменили (previous, current, current.left) на (current, current.left, previous) сосл-ветственно. В данном случае важно подчеркнуть одновременность этих действий: местоположение ячейки current.leftизженшся только при присваивании нового значения current. Чтобы выполнить эти модификации указателей, используется процедура rotate (циклический сдвиг), показанная в листинге 12.3.

Листинг 12.3. Процедура модификации указателей

procedure rotate ( var pi, рй, рЗ : tcelltype ) var

temp: tceHtype;

begin ";

temp:= pi; я

p2 p3

= p2; Я

= P3; = temp

end; { rotate }



а. Продвижение вперед


previous

б. Переключение


в. Отход

Рис. 12.4. Три основных шага поиска в глубину

Теперь вернемся к написанию нерекурсивной процедуры маркировки nrdfs. Эта процедура представляет собой один из тех запутанных процессов, которые проще всего понять, если при их написании использовать метки и операторы безусловного перехода goto. Для процедуры nrdfs возмокны два "состояния": продвижение вперед, представленное меткой state 1, и отход, представленный меткой state2. Поначалу, а таюке в тех случаях, когда мы перешли на новую ячейку (либо в результате шага продвижения вперед, либо в результате шага переключения), мы переходим в первое состояние. В этом состоянии мы пытаемся выполнить еще один шаг продвижения вперед и "отходим" или "переключаемся" лишь в том случае, если оказываемся заблокированными. Можно оказаться заблокированными по двум причинам: (1) ячейка, к которой только что обратились, уже помечена; (2) в данной ячейке отсутствуют ненулевые указатели. Оказавшись заблокированными, переходим во второе состояние - состояние отхода.

Переход во второе состояние возможен в тех случаях, когда мы отходим или когда не можем оставаться в состоянии продвижения вперед, так как оказались заблокированными. В состоянии отхода проверяем, отошли ли обратно на ячейку sourcel. Как уже было сказано выше, мы распознаем эту ситуацию по выполнению условия previous = current; в этом случае переходим в состояние 3 (метка stateS), т.е. практически закончили маркировку ячеек. В противном случае принимается решение либо отступить и остаться в состоянии отхода, либо переключиться и перейти в состояние продвижения вперед.



Код процедуры nrdfs цоказан в листицге 12.4. В этой программе исцользуются функции blockleft (блокировка слева), blockright (блокировка справа) и block (блокировка), которые проверяют, содержит ли левое или правое поле ячейки (или оба эти поля) атом или пуль-указатель. Функция block проверяет также, пе маркиро-вапа ли ячейка.

Листинг 12.4. Нерекурсивный алгоритм маркировки ячеек

function blockleft ( cell: celltype ) : boolean;

{ проверяет, является ли левое поле атомом или нуль-указателем } begin

with cell do

if [pattern = PP) or (pattern = PA) then if left <> nil then return!false); return(true) end; { blockleft }

function blockright ( cell: celltype ): boolean;

{ щэоверяет, является ли правое поле атомом или нуль-указателем } begin

with cell do

if (pattern = PP) or (pattern = AP) then if right <> nil then return(false); return(true) end; { blockright }

function Ыоcc ( cell: celltype ): boolean;

{ проверяет, не помечена ли ячейка и не содержит ли ненулевые указатели }

begin

if (cell .mark = true) or blockleft(cell) and blockright (cell)

then

return(true)

else

return(false)

end; { block }

procedure nrdfs; { помечает ячейки, доступные из ячейки source } var

current, previous: Tcelltype; begin { инициализация }

current:= sourcelt. right;

{ ячейка, на которую указывает sourcel } previous:= sourcel; { теперь previous указывает на sourcel } sourcelt.back:= R;

sourcelt. right:= sourcel; { Sourcel указывает сама на себя } sourcelt .mark:= true; statel: { продвижение вперед }

if ЫосА( currentT) then begin { подготовка к отходу } сиггел tt.jnar>f:= true; goto state2

else begin { пометить и продвинуться вперед } currentt. marA:= true; if biocJ;lef t ( сиггел tt) then begin





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 [112] 113 114 115 116 117 118 119 120 121 122 123

0.0036