3.4. Алгоритмы с возвратом
Весьма интригующее направление в программировании – поиск общих методов решения сложных зачач. Цель здесь в том, чтобы научиться искать решения конк%
ретных задач, не следуя какому%то фиксированному правилу вычислений, а мето%
дом проб и ошибок. Общая схема заключается в том, чтобы свести процесс проб и ошибок к нескольким частным задачам. Эти задачи часто допускают очень естест%
венное рекурсивное описание и сводятся к исследованию конечного числа подза%
дач. Процесс в целом можно представлять себе как поиск%исследование, в ко%
тором постепенно строится и просматривается (с обрезанием каких%то ветвей)
некое дерево подзадач. Во многих задачах такое дерево поиска растет очень быст%
ро, часто экспоненциально, как функция некоторого параметра. Трудоемкость поиска растет соответственно. Часто только использование эвристик позволяет обрезать дерево поиска до такой степени, чтобы сделать вычисление сколь%ни%
будь реалистичным.
Обсуждение общих эвристических правил не входит в наши цели. Мы сосредо%
точимся в этой главе на общем принципе разбиения задач на подзадачи с приме%
нением рекурсии. Начнем с демонстрации соответствующей техники в простом примере, а именно в хорошо известной задаче о путешествии шахматного коня.
Пусть дана доска n
×
n с n
2
полями. Конь, который передвигается по шахмат%
ным правилам, ставится на доске в поле
, y0>
. Задача – обойти всю доску, если это возможно, то есть вычислить такой маршрут из n
2
–1
ходов, чтобы в каждое поле доски конь попал ровно один раз.
Очевидный способ упростить задачу обхода n
2
полей – рассмотреть подзадачу,
которая состоит в том, чтобы либо выполнить какой%либо очередной ход, либо обнаружить, что дальнейшие ходы невозможны. Эту идею можно выразить так:
PROCEDURE TryNextMove; (* *)
BEGIN
IF
THEN
;
WHILE
(
v ) &
( v # )
DO
END
END
END TryNextMove;
Предикат
v # удобно выразить в виде про%
цедуры%функции с логическим значением, в которой – раз уж мы собираемся за%
писывать порождаемую последовательность ходов – подходящее место как для записи очередного хода, так и для ее отмены в случае неудачи, так как именно в этой процедуре выясняется успех завершения обхода.
PROCEDURE CanBeDone (
): BOOLEAN;
BEGIN
;
Алгоритмы с возвратом
Рекурсивные алгоритмы
144
TryNextMove;
IF
THEN
END;
RETURN
END CanBeDone
Здесь уже видна схема рекурсии.
Чтобы уточнить этот алгоритм, необходимо принять некоторые решения о пред%
ставлении данных. Во%первых, мы хотели бы записать полную историю ходов.
Поэтому каждый ход будем характеризовать тремя числами: его номером i
и дву%
мя координатами
. Эту связь можно было бы выразить, введя специальный тип записей с тремя полями, но данная задача слишком проста, чтобы оправдать соответствующие накладные расходы; будет достаточно отслеживать соответствую%
щие тройки переменных.
Это сразу позволяет выбрать подходящие параметры для процедуры
TryNextMove
Они должны позволять определить начальные условия для очередного хода, а так%
же сообщать о его успешности. Для достижения первой цели достаточно указы%
вать параметры предыдущего хода, то есть координаты поля x
, y
и его номер i
. Для достижения второй цели нужен булевский параметр%результат со значением
-
v v
. Получается следующая сигнатура:
PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN)
Далее, очередной допустимый ход должен иметь номер i+1
. Для его координат введем пару переменных u, v
. Это позволяет выразить предикат
-
v #
, используемый в цикле линейного поиска, в виде вызова процедуры%функции со следующей сигнатурой:
PROCEDURE CanBeDone (u, v, i1: INTEGER): BOOLEAN
Условие
может быть выражено как i < n
2
. А для условия
v
введем логическую переменную eos
. Тогда логика алгоритма проясняется следующим образом:
PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN);
VAR eos: BOOLEAN; u, v: INTEGER;
BEGIN
IF i < n
2
THEN
;
WHILE eos & CanBeDone(u, v, i+1) DO
END;
done := eos
ELSE
done := TRUE
END
END TryNextMove;
145
PROCEDURE CanBeDone (u, v, i1: INTEGER): BOOLEAN;
VAR done: BOOLEAN;
BEGIN
;
TryNextMove(u, v, i1, done);
IF
done THEN
END;
RETURN done
END CanBeDone
Заметим, что процедура
TryNextMove сформулирована так, чтобы корректно об%
рабатывать и вырожденный случай, когда после хода x, y, i выясняется, что доска заполнена. Это сделано по той же, в сущности, причине, по которой арифметиче%
ские операции определяются так, чтобы корректно обрабатывать нулевые значения операндов: удобство и надежность. Если (как нередко делают из соображений оп%
тимизации) вынести такую проверку из процедуры, то каждый вызов процедуры придется сопровождать такой охраной – или доказывать, что охрана в конкретной точке программы не нужна. К подобным оптимизациям следует прибегать, только если их необходимость доказана – после построения корректного алгоритма.
Следующее очевидное решение – представить доску матрицей, скажем h
:
VAR h: ARRAY n, n OF INTEGER
Решение сопоставить каждому полю доски целое, а не булевское значение,
которое бы просто отмечало, занято поле или нет, объясняется желанием сохра%
нить полную историю ходов простейшим способом:
h[x, y] = 0:
поле
еще не пройдено h[x, y] = i:
поле
пройдено на i
%м ходу
(0
<
i
≤
n
2
)
Очевидно, запись допустимого хода теперь выражается присваиванием h
xy
:= i
,
а отмена – h
xy
:= 0
, чем завершается построение процедуры
CanBeDone
Осталось организовать перебор допустимых ходов u, v из заданной позиции x, y в цикле поиска процедуры
TryNextMove
. На бесконечной во все стороны доске для каждой позиции x, y есть несколько ходов%кандидатов u, v
, которые пока конкретизировать нет нужды (см., однако, рис. 3.7). Предикат для выбора допустимых ходов среди ходов%кандидатов выражается как логическая конъюнк%
ция условий, описывающих, что новое поле лежит в пределах доски, то есть
0
≤
u < n и
0
≤
v < n
, и что конь по нему еще не проходил, то есть h
uv
= 0
. Деталь,
которую нельзя упустить: переменная h
uv существует, только если оба значения u
и v
лежат в диапазоне
0 ... n–1
. Поэтому важно, чтобы член h
uv
= 0
стоял после%
дним. В итоге выбор следующего допустимого хода тогда представляется уже зна%
комой схемой линейного поиска (только выраженной через цикл repeat вместо while
,
что в данном случае возможно и удобно). При этом для сообщения об исчер%
пании множества ходов%кандидатов можно использовать переменную eos
. Офор%
мим эту операцию в виде процедуры
Next
, явно указав в качестве параметров зна%
чимые переменные:
Алгоритмы с возвратом
Рекурсивные алгоритмы
146
PROCEDURE Next (VAR eos: BOOLEAN; VAR u, v: INTEGER);
BEGIN
(*eos*)
REPEAT
- u, v
UNTIL (
v ) OR
((0 <= u) & (u < n) & (0 <= v) & (v < n) & (h[u, v] = 0));
eos :=
v
END Next;
Инициализация перебора ходов%кандидатов выполняется внутри аналогич%
ной процедуры
First
, порождающей первый допустимый ход; см. детали в оконча%
тельной программе, приводимой ниже.
Остался только один шаг уточнения, и мы получим программу, полностью выраженную в нашей основной нотации. Заметим, что до сих пор программа раз%
рабатывалась совершенно независимо от правил, описывающих допустимые хо%
ды коня. Мы сознательно откладывали рассмотрение таких деталей задачи. Но теперь пора их учесть.
Для начальной пары координат x
,
y на бесконечной свободной доске есть восемь позиций%кандидатов u
,
v
,
куда может прыгнуть конь. На рис. 3.7 они пронумеро%
ваны от 1 до 8.
Простой способ получить u
,
v из x
,
y состоит в при%
бавлении разностей координат, хранящихся либо в мас%
сиве пар разностей, либо в двух массивах одиночных разностей. Пусть эти массивы обозначены как dx и dy и
правильно инициализированы:
dx = (2, 1, –1, –2, –2, –1, 1, 2)
dy = (1, 2, 2, 1, –1, –2, –2, –1)
Тогда можно использовать индекс k
для нумерации очередного хода%кандидата. Детали показаны в программе, приводимой ниже.
Мы предполагаем наличие глобальной матрицы h
размера n
×
n
, представляю%
щей результат, константы n
(и nsqr = n
2
), а также массивов dx и dy
, представля%
ющих возможные ходы коня без ограничений (см. рис. 3.7). Рекурсивная проце%
дура стартует с параметрами x0, y0
– координатами того поля, с которого должно начаться путешествие коня. В это поле должен быть записан номер 1; все прочие поля следует пометить как свободные.
VAR h: ARRAY n, n OF INTEGER;
(* ADruS34_KnightsTour *)
dx, dy: ARRAY 8 OF INTEGER;
PROCEDURE CanBeDone (u, v, i: INTEGER): BOOLEAN;
VAR done: BOOLEAN;
BEGIN
h[u, v] := i;
TryNextMove(u, v, i, done);
IF done THEN h[u, v] := 0 END;
Рис. 3.7. Восемь возможных ходов коня
147
RETURN done
END CanBeDone;
PROCEDURE TryNextMove (x, y, i: INTEGER; VAR done: BOOLEAN);
VAR eos: BOOLEAN; u, v: INTEGER; k: INTEGER;
PROCEDURE Next (VAR eos: BOOLEAN; VAR u, v: INTEGER);
BEGIN
REPEAT
INC(k);
IF k < 8 THEN u := x + dx[k]; v := y + dy[k] END;
UNTIL (k = 8) OR ((0 <= u) & (u < n) & (0 <= v) & (v < n) & (h[u, v] = 0));
eos := (k = 8)
END Next;
PROCEDURE First (VAR eos: BOOLEAN; VAR u, v: INTEGER);
BEGIN
eos := FALSE; k := –1; Next(eos, u, v)
END First;
BEGIN
IF i < nsqr THEN
First(eos, u, v);
WHILE eos & CanBeDone(u, v, i+1) DO
Next(eos, u, v)
END;
done := eos
ELSE
done := TRUE
END;
END TryNextMove;
PROCEDURE Clear;
VAR i, j: INTEGER;
BEGIN
FOR i := 0 TO n–1 DO
FOR j := 0 TO n–1 DO h[i,j] := 0 END
END
END Clear;
PROCEDURE KnightsTour (x0, y0: INTEGER; VAR done: BOOLEAN);
BEGIN
Clear; h[x0,y0] := 1; TryNextMove(x0, y0, 1, done);
END KnightsTour;
Таблица 3.1 показывает решения, полученные для начальных позиций
<2,2>,
<1,3>
для n = 5
и
<0,0>
для n = 6
Какие общие уроки можно извлечь из этого примера? Видна ли в нем какая%
либо схема, типичная для алгоритмов, решающих подобные задачи? Чему он нас учит? Характерной чертой здесь является то, что каждый шаг, выполняемый в попытке приблизиться к полному решению,
запоминается таким образом, чтобы
Алгоритмы с возвратом
Рекурсивные алгоритмы
148
от него можно было позднее отказаться, если выяснится, что он не может привес%
ти к полному решению и заводит в тупик. Такое действие называется возвратом
(backtracking). Общая схема, приводимая ниже, абстрагирована из процедуры
TryNextMove в предположении, что число потенциальных кандидатов на каждом шаге конечно:
PROCEDURE Try; (* v *)
BEGIN
IF
v THEN
v # ;
WHILE (
v # v ) & CanBeDone( v #) DO
v #
END
END
END Try;
PROCEDURE CanBeDone ( v # ): BOOLEAN;
(* v , # v # *)
BEGIN
v #;
Try;
IF
v THEN
v #
END;
RETURN
v
END CanBeDone
Разумеется, в реальных программах эта схема может варьироваться. В частно%
сти, в зависимости от специфики задачи может варьироваться способ передачи информации в процедуру
Try при каждом очередном ее вызове. Ведь в обсуж%
даемой схеме предполагается, что эта процедура имеет доступ к глобальным пе%
ременным, в которых записывается выстраиваемое решение и, следовательно,
содержится, в принципе, полная информация о текущем шаге построения. Напри%
Таблица 3.1.
Таблица 3.1.
Таблица 3.1.
Таблица 3.1.
Таблица 3.1. Три возможных обхода конем
23 4
9 14 25 10 15 24 1
8 5
22 3
18 13 16 11 20 7
2 21 6
17 12 19 1
16 7
26 11 14 34 25 12 15 6
27 17 2
33 8
13 10 32 35 24 21 28 5
23 18 3
30 9
20 36 31 22 19 4
29 23 10 15 4
25 16 5
24 9
14 11 22 1
18 3
6 17 20 13 8
21 12 7
2 19
149
мер, в рассмотренной задаче о путешествии коня в процедуре
TryNextMove нужно знать последнюю позицию коня на доске. Ее можно было бы найти поиском в мас%
сиве h
. Однако эта информация явно наличествует в момент вызова процедуры,
и гораздо проще ее туда передать через параметры. В дальнейших примерах мы увидим вариации на эту тему.
Отметим, что условие поиска в цикле оформлено в виде процедуры%функции
CanBeDone для максимального прояснения логики алгоритма без потери обозри%
мости программы. Разумеется, можно оптимизировать программу в других отно%
шениях, проведя эквивалентные преобразования. Например, можно избавиться от двух процедур
First и
Next
, слив два легко верифицируемых цикла в один. Этот единственный цикл будет, вообще говоря, более сложным, однако в том случае,
когда требуется сгенерировать все решения, может получиться довольно прозрач%
ный результат (см. последнюю программу в следующем разделе).
Остаток этой главы посвящен разбору еще трех примеров, в которых уместна рекурсия. В них демонстрируются разные реализации описанной общей схемы.
3.5. Задача о восьми ферзях
Задача о восьми ферзях – хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Ее исследовал Гаусс в 1850 г., но он не нашел полного решения. Это и неудивительно, ведь для таких задач характерно отсут%
ствие аналитических решений. Вместо этого приходится полагаться на огромный труд, терпение и точность. Поэтому подобные алгоритмы стали применяться почти исключительно благодаря появлению автоматического компьютера, который обла%
дает этими качествами в гораздо большей степени, чем люди и даже чем гении.
В этой задаче (см. также [3.4]) требуется расположить на шахматной доске во%
семь ферзей так, чтобы ни один из них не угрожал другому. Будем следовать об%
щей схеме, представленной в конце раздела 3.4. По правилам шахмат ферзь угро%
жает всем фигурам, находящимся на одной с ним вертикали, горизонтали или диагонали доски, поэтому мы заключаем, что на каждой вертикали может нахо%
диться один и только один ферзь. Поэтому можно пронумеровать ферзей по зани%
маемым ими вертикалям, так что i
%й ферзь стоит на i
%й вертикали. Очередным шагом построения в общей рекурсивной схеме будем считать размещение очеред%
ного ферзя в порядке их номеров. В отличие от задачи о путешествии коня, здесь нужно будет знать положение всех уже размещенных ферзей. Поэтому в качестве параметра в процедуру
Try достаточно передавать номер размещаемого на этом шаге ферзя i
, который, таким образом, является номером столбца. Тогда опреде%
лить положение ферзя – значит выбрать одно из восьми значений номера ряда j
PROCEDURE Try (i: INTEGER);
BEGIN
IF i < 8 THEN
j ;
Задача о восьми ферзях
Рекурсивные алгоритмы
150
WHILE (
v ) & CanBeDone(i, j) DO
j
END
END
END Try;
PROCEDURE CanBeDone (i, j: INTEGER): BOOLEAN;
(* v , i-# ! j- *)
BEGIN
! ;
Try(i+1);
IF
v THEN
!
END;
RETURN
v
END CanBeDone
Чтобы двигаться дальше, нужно решить, как представлять данные. Напраши%
вается представление доски с помощью квадратной матрицы, но небольшое раз%
мышление показывает, что тогда действия по проверке безопасности позиций по%
лучатся довольно громоздкими. Это
крайне нежелательно, так как это самая часто выполняемая операция. Поэтому мы должны представить данные так, чтобы эта проверка была как можно проще. Лучший путь к этой цели – как можно более непосредственно представить именно ту информацию, которая конкретно нужна и чаще всего используется. В нашем случае это не положение ферзей, а информа%
ция о том, был ли уже поставлен ферзь на каждый из рядов и на каждую из диаго%
налей. (Мы уже знаем, что в каждом столбце k
для
0
≤ k < i стоит в точности один ферзь.) Это приводит к такому выбору переменных:
VAR x: ARRAY 8 OF INTEGER;
a: ARRAY 8 OF BOOLEAN;
b, c: ARRAY 15 OF BOOLEAN
где x
i означает положение ферзя в i
%м столбце;
a j
означает, что «в j
%м ряду ферзя еще нет»;
b k
означает, что «на k
%й
/- диагонали нет ферзя»;
c k
означает, что «на k
%й
\- диагонали нет ферзя».
Заметим, что все поля на
/
%диагонали имеют одинаковую сумму своих коорди%
нат i
и j
, а на
\
%диагонали – одинаковую разность координат i-j
. Соответствующая нумерация диагоналей использована в приведенной ниже программе
Queens
С такими определениями операция
! раскрывается следующим образом:
x[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSE
операция
! уточняется в a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUE
151
Поле
безопасно, если оно находится в строке и на диагоналях, которые еще свободны. Поэтому ему соответствует логическое выражение a[j] & b[i+j] & c[i-j+7]
Это позволяет построить процедуры перечисления безопасных значений j для i%го ферзя по аналогии с предыдущим примером.
Этим, в сущности, завершается разработка алгоритма, представленного цели%
ком ниже в виде программы
Queens
. Она вычисляет решение x = (0, 4, 7, 5, 2, 6,
1, 3),
показанное на рис. 3.8.
Рис. 3.8. Одно из решений задачи о восьми ферзях
PROCEDURE Try (i: INTEGER; VAR done: BOOLEAN);
(* ADruS35_Queens *)
VAR eos: BOOLEAN; j: INTEGER;
PROCEDURE Next;
BEGIN
REPEAT INC(j);
UNTIL (j = 8) OR (a[j] & b[i+j] & c[i-j+7]);
eos := (j = 8)
END Next;
PROCEDURE First;
BEGIN
eos := FALSE; j := –1; Next
END First;
BEGIN
IF i < 8 THEN
First;
WHILE eos & CanBeDone(i, j) DO
Next
Задача о восьми ферзях
Рекурсивные алгоритмы
152
END;
done := eos
ELSE
done := TRUE
END
END Try;
PROCEDURE CanBeDone (i, j: INTEGER): BOOLEAN;
(* v , i-# ! j- *)
VAR done: BOOLEAN;
BEGIN
x[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSE;
Try(i+1, done);
IF done THEN
x[i] := –1; a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUE
END;
RETURN done
END CanBeDone;
PROCEDURE Queens*;
VAR done: BOOLEAN; i, j: INTEGER; (* # W*)
BEGIN
FOR i := 0 TO 7 DO a[i] := TRUE; x[i] := –1 END;
FOR i := 0 TO 14 DO b[i] := TRUE; c[i] := TRUE END;
Try(0, done);
IF done THEN
FOR i := 0 TO 7 DO Texts.WriteInt(W, x[ i ], 4) END;
Texts.WriteLn(W)
END
END Queens.
Прежде чем закрыть шахматную тему, покажем на примере задачи о восьми ферзях важную модификацию такого поиска методом проб и ошибок. Цель моди%
фикации – в том, чтобы найти не одно, а все решения задачи.
Выполнить такую модификацию легко. Нужно вспомнить, что кандидаты дол%
жны порождаться систематическим образом, так чтобы ни один кандидат не по%
рождался больше одного раза. Это соответствует систематическому поиску по де%
реву кандидатов, при котором каждый узел проходится в точности один раз. При такой организации после нахождения и печати решения можно просто перейти к следующему кандидату, доставляемому систематическим процессом порожде%
ния. Формально модификация осуществляется переносом процедуры%функции
CanBeDone из охраны цикла в его тело и подстановкой тела процедуры вместо ее вызова. При этом нужно учесть, что возвращать логические значения больше не нужно. Получается такая общая рекурсивная схема:
PROCEDURE Try;
BEGIN
IF
v THEN
v # ;
153
WHILE (
v # v ) DO
v #;
Try;
# v #
v #
END
ELSE
v
END
END Try
Интересно, что поиск всех возможных решений реализуется более простой программой, чем поиск единственного решения.
В задаче о восьми ферзях возможно еще более заметное упрощение. В самом деле, несколько громоздкий механизм перечисления допустимых шагов, состоя%
щий из двух процедур
First и
Next
, был нужен для взаимной изоляции цикла линейного поиска очередного безопасного поля (цикл по j
внутри
Next
) и цикла линейного поиска первого j
, дающего полное решение. Теперь, благодаря упро%
щению охраны последнего цикла, нужда в этом отпала и его можно заменить про%
стейшим циклом по j
, просто отбирая безопасные j
с помощью условного операто%
ра
IF
, непосредственно вложенного в цикл, без использования дополнительных процедур.
Так модифицированный алгоритм определения всех 92 решений задачи о восьми ферзях показан ниже. На самом деле есть только 12 существенно различ%
ных решений, но наша программа не распознает симметричные решения. Первые
12 порождаемых здесь решений выписаны в табл. 3.2. Колонка n
справа показы%
вает число выполнений проверки безопасности позиций.
Среднее значение часто%
ты по всем 92 решениям равно 161.
PROCEDURE write;
(* ADruS35_Queens *)
VAR k: INTEGER;
BEGIN
FOR k := 0 TO 7 DO Texts.WriteInt(W, x[k], 4) END;
Texts.WriteLn(W)
END write;
PROCEDURE Try (i: INTEGER);
VAR j: INTEGER;
BEGIN
IF i < 8 THEN
FOR j := 0 TO 7 DO
IF a[j] & b[i+j] & c[i-j+7] THEN
x[i] := j; a[j] := FALSE; b[i+j] := FALSE; c[i-j+7] := FALSE;
Try(i + 1);
x[i] := –1; a[j] := TRUE; b[i+j] := TRUE; c[i-j+7] := TRUE
END
END
ELSE
Задача о восьми ферзях
Рекурсивные алгоритмы
154
write;
m := m+1 (* v *)
END
END Try;
PROCEDURE AllQueens*;
VAR i, j: INTEGER;
BEGIN
FOR i := 0 TO 7 DO a[i] := TRUE; x[i] := –1 END;
FOR i := 0 TO 14 DO b[i] := TRUE; c[i] := TRUE END;
m := 0;
Try(0);
Log.String(' # v : '); Log.Int(m); Log.Ln
END AllQueens.
Таблица 3.2.
Таблица 3.2.
Таблица 3.2.
Таблица 3.2.
Таблица 3.2. Двенадцать решений задачи о восьми ферзях x0
x1
x2
x3
x4
x5
x6
x7
n
0 4
7 5
2 6
1 3
876 0
5 7
2 6
3 1
4 264 0
6 3
5 7
1 4
2 200 0
6 4
7 1
3 5
2 136 1
3 5
7 2
0 6
4 504 1
4 6
0 2
7 5
3 400 1
4 6
3 0
7 5
2 072 1
5 0
6 3
7 2
4 280 1
5 7
2 0
3 6
4 240 1
6 2
5 7
4 0
3 264 1
6 4
7 0
3 5
2 160 1
7 5
0 2
4 6
3 336
3.6. Задача о стабильных бракахПредположим, что даны два непересекающихся множества
A
и
B
равного размера n
. Требуется найти набор n
пар
– таких, что a
из
A
и b
из
B
удовлетворяют некоторым ограничениям. Может быть много разных критериев для таких пар;
один из них называется правилом стабильных браков.
Примем, что
A
– это множество мужчин, а
B
– множество женщин. Каждый мужчина и каждая женщина указали предпочтительных для себя партнеров. Если n
пар выбраны так, что существуют мужчина и женщина, которые не являются мужем и женой, но которые предпочли бы друг друга своим фактическим супру%
гам, то такое распределение по парам называется нестабильным. Если таких пар нет, то распределение стабильно. Подобная ситуация характерна для многих по%
хожих задач, в которых нужно сделать распределение с учетом предпочтений, на%
155
пример выбор университета студентами, выбор новобранцев различными родами войск и т. п. Пример с браками особенно интуитивен; однако следует заметить,
что список предпочтений остается неизменным и после того, как сделано распре%
деление по парам. Такое предположение упрощает задачу, но представляет собой опасное искажение реальности (это называют абстракцией).
Возможное направление поиска решения – пытаться распределить по парам членов двух множеств одного за другим, пока не будут исчерпаны оба множества.
Имея целью найти все стабильные распределения, мы можем сразу сделать набро%
сок решения, взяв за образец схему программы
AllQueens
. Пусть
Try(m)
означает алгоритм поиска жены для мужчины m
, и пусть этот поиск происходит в соот%
ветствии с порядком списка предпочтений, заявленных этим мужчиной. Первая версия, основанная на этих предположениях, такова:
PROCEDURE Try (m: man);
VAR r: rank;
BEGIN
IF m < n THEN
FOR r := 0 TO n–1 DO
r- m;
IF
THEN
;
Try(
m);
END
END
ELSE
v
END
END Try
Исходные данные представлены двумя матрицами, указывающими предпоч%
тения мужчин и женщин:
VAR wmr: ARRAY n, n OF woman;
mwr: ARRAY n, n OF man
Соответственно, wmr m
обозначает список предпочтений мужчины m
, то есть wmr m,r
– это женщина, находящаяся в этом списке на r
%м месте. Аналогично, mwr w
–
список предпочтений женщины w
, а mwr w,r
– мужчина на r
%м месте в этом списке.
Пример набора данных показан в табл. 3.3.
Результат представим массивом женщин x
, так что x
m обозначает супругу мужчины m
. Чтобы сохранить симметрию между мужчинами и женщинами, вво%
дится дополнительный массив y
, так что y
w обозначает супруга женщины w
:
VAR x, y: ARRAY n OF INTEGER
На самом деле массив y
избыточен, так как в нем представлена информация,
уже содержащаяся в x
. Действительно, соотношения x[y[w]] = w, y[x[m]] = m
Задача о стабильных браках
Рекурсивные алгоритмы
156
выполняются для всех m
и w
, которые состоят в браке. Поэтому значение y
w мож%
но было бы определить простым поиском в x
. Однако ясно, что использование массива y
повысит эффективность алгоритма. Информация, содержащаяся в мас%
сивах x
и y
, нужна для определения стабильности предполагаемого множества браков. Поскольку это множество строится шаг за шагом посредством соединения индивидов в пары и проверки стабильности после каждого преполагаемого брака,
массивы x
и y
нужны даже еще до того, как будут определены все их компоненты.
Чтобы отслеживать, какие компоненты уже определены, можно ввести булевские массивы singlem, singlew: ARRAY n OF BOOLEAN
со следующими значениями: истинность singlem m
означает, что значение x
m еще не определено, а singlew w
– что не определено y
w
. Однако, присмотревшись к обсуждаемому алгоритму, мы легко обнаружим, что семейное положение мужчины k
определяется значением m
с помощью отношения
singlem[k] = k < m
Это наводит на мысль, что можно отказаться от массива singlem
; соответствен%
но, имя singlew упростим до single
. Эти соглашения приводят к уточнению, пока%
занному в следующей процедуре
Try
. Предикат
можно уточнить в конъюнкцию операндов single и
, где предикат
еще предстоит определить:
PROCEDURE Try (m: man);
VAR r: rank; w: woman;
BEGIN
IF m < n THEN
FOR r := 0 TO n–1 DO
w := wmr[m,r];
IF single[w] &
THEN
x[m] := w; y[w] := m; single[w] := FALSE;
Try(m+1);
Таблица 3.3.
Таблица 3.3.
Таблица 3.3.
Таблица 3.3.
Таблица 3.3. Пример входных данных для wmr и mwr r = 0 1
2 3
4 5
6 7
r = 0 1
2 3
4 5
6 7
m = 0 6
1 5
4 0
2 7
3
w = 0 3
5 1
4 7
0 2
6 1
3 2
1 5
7 0
6 4
1 7
4 2
0 5
6 3
1 2
2 1
3 0
7 4
6 5
2 5
7 0
1 2
3 6
4 3
2 7
3 1
4 5
6 0
3 2
1 3
6 5
7 4
0 4
7 2
3 4
5 0
6 1
4 5
2 0
3 4
6 1
7 5
7 6
4 1
3 2
0 5
5 1
0 2
7 6
3 5
4 6
1 3
5 2
0 6
4 7
6 2
4 6
1 3
0 7
5 7
5 0
3 1
6 4
2 7
7 6
1 7
3 4
5 2
0
157
single[w] := TRUE
END
END
ELSE
v
END
END Try
У этого решения все еще заметно сильное сходство с процедурой
AllQueens
Ключевая задача теперь – уточнить алгоритм определения стабильности. К не%
счастью, свойство стабильности невозможно выразить так же просто, как при про%
верке безопасности позиции ферзя.
Первая особенность, о которой нужно пом%
нить, состоит в том, что, по определению, стабильность следует из сравнений рангов (то есть позиций в списках предпочтений). Однако нигде в нашей коллек%
ции данных, определенных до сих пор, нет непосредственно доступных рангов мужчин или женщин. Разумеется, ранг женщины w
во мнении мужчины m
вычис%
лить можно, но только с помощью дорогостоящего поиска значения w
в wmr m
. По%
скольку вычисление стабильности – очень частая операция, полезно обеспечить более прямой доступ к этой информации. С этой целью введем две матрицы:
rmw: ARRAY man, woman OF rank;
rwm: ARRAY woman, man OF rank
При этом rmw m,w обозначает ранг женщины w
в списке предпочтений мужчи%
ны m
, а rwm w,m
– ранг мужчины m
в аналогичном списке женщины w
. Значения этих вспомогательных массивов не меняются и могут быть определены в самом начале по значениям массивов wmr и mwr
Теперь можно вычислить предикат
, точно следуя его исходно%
му определению. Напомним, что мы проверяем возможность соединить браком m
и w
, где w = wmr m,r
, то есть w
является кандидатурой ранга r
для мужчины m
. Про%
являя оптимизм, мы сначала предположим, что стабильность имеет место, а потом попытаемся обнаружить возможные помехи. Где они могут быть скрыты? Есть две симметричные возможности:
1) может найтись женщина pw с рангом, более высоким, чем у w
, по мнению m
,
и которая сама предпочитает m
своему мужу;
2) может найтись мужчина pm с рангом, более высоким, чем у m
, по мнению w
,
и который сам предпочитает w
своей жене.
Чтобы обнаружить помеху первого рода, сравним ранги rwm pw,m и rwm pw,y[pw]
для всех женщин, которых m
предпочитает w
, то есть для всех pw = wmr m,i таких,
что i < r
. На самом деле все эти женщины pw уже замужем, так как, будь любая из них еще не замужем, m
выбрал бы ее еще раньше. Описанный процесс можно сформулировать в виде линейного поиска; имя переменной
S является сокраще%
нием для
Stability
(стабильность).
i := –1; S := TRUE;
REPEAT
INC(i);
Задача о стабильных браках
Рекурсивные алгоритмы
158
IF i < r THEN
pw := wmr[m,i];
IF single[pw] THEN S := rwm[pw,m] > rwm[pw, y[pw]] END
END
UNTIL (i = r) OR S
Чтобы обнаружить помеху второго рода, нужно проверить всех кандидатов pm
,
которых w
предпочитает своей текущей паре m
, то есть всех мужчин pm = mwr w,i с i < rwm w,m
. По аналогии с первым случаем нужно сравнить ранги rmwp m,w и
rmw pm,x[pm]
. Однако нужно не забыть пропустить сравнения с теми x
pm
, где pm еще не женат. Это обеспечивается проверкой pm < m
, так как мы знаем, что все мужчины до m
уже женаты.
Полная программа показана ниже. Таблица 3.4 показывает девять стабильных решений, найденных для входных данных wmr и mwr
, представленных в табл. 3.3.
PROCEDURE write;
(* ADruS36_Marriages *)
(* # W*)
VAR m: man; rm, rw: INTEGER;
BEGIN
rm := 0; rw := 0;
FOR m := 0 TO n–1 DO
Texts.WriteInt(W, x[m], 4);
rm := rmw[m, x[m]] + rm; rw := rwm[x[m], m] + rw
END;
Texts.WriteInt(W, rm, 8); Texts.WriteInt(W, rw, 4); Texts.WriteLn(W)
END write;
PROCEDURE stable (m, w, r: INTEGER): BOOLEAN; (* *)
VAR pm, pw, rank, i, lim: INTEGER;
S: BOOLEAN;
BEGIN
i := –1; S := TRUE;
REPEAT
INC(i);
IF i < r THEN
pw := wmr[m,i];
IF single[pw] THEN S := rwm[pw,m] > rwm[pw, y[pw]] END
END
UNTIL (i = r) OR S;
i := –1; lim := rwm[w,m];
REPEAT
INC(i);
IF i < lim THEN
pm := mwr[w,i];
IF pm < m THEN S := rmw[pm,w] > rmw[pm, x[pm]] END
END
UNTIL (i = lim) OR S;
RETURN S
END stable;
159
PROCEDURE Try (m: INTEGER);
VAR w, r: INTEGER;
BEGIN
IF m < n THEN
FOR r := 0 TO n–1 DO
w := wmr[m,r];
IF single[w] & stable(m,w,r) THEN
x[m] := w; y[w] := m; single[w] := FALSE;
Try(m+1);
single[w] := TRUE
END
END
ELSE
write
END
END Try;
PROCEDURE FindStableMarriages (VAR S: Texts.Scanner);
VAR m, w, r: INTEGER;
BEGIN
FOR m := 0 TO n–1 DO
FOR r := 0 TO n–1 DO
Texts.Scan(S); wmr[m,r] := S.i; rmw[m, wmr[m,r]] := r
END
END;
FOR w := 0 TO n–1 DO
single[w] := TRUE;
FOR r := 0 TO n–1 DO
Texts.Scan(S); mwr[w,r] := S.i; rwm[w, mwr[w,r]] := r
END
END;
Try(0)
END FindStableMarriages
Этот алгоритм прямолинейно реализует обход с возвратом. Его эффектив%
ность зависит главным образом от изощренности схемы усечения дерева реше%
ний. Несколько более быстрый, но более сложный и менее прозрачный алгоритм дали Маквити и Уилсон [3.1] и [3.2], и они также распространили его на случай множеств (мужчин и женщин) разного размера.
Алгоритмы, подобные последним двум примерам, которые порождают все воз%
можные решения задачи (при определенных ограничениях), часто используют для выбора одного или нескольких решений, которые в каком%то смысле опти%
мальны. Например, в данном примере можно было бы искать решение, которое в среднем лучше удовлетворяет мужчин или женщин или вообще всех.
Заметим, что в табл. 3.4 указаны суммы рангов всех женщин в списках пред%
почтений их мужей, а также суммы рангов всех мужчин в списках предпочтений их жен. Это величины
Задача о стабильных браках
Рекурсивные алгоритмы
160
rm = S
S
S
S
Sm: 0
≤ m < n: rmw m,x[m]
rw = S
S
S
S
Sm: 0
≤ m < n: rwm x[m],m
Таблица 3.4.
Таблица 3.4.
Таблица 3.4.
Таблица 3.4.
Таблица 3.4. Решение задачи о стабильных браках x0
x1
x2
x3
x4
x5
x6
x7
rm rw c
0 6
3 2
7 0
4 1
5 8
24 21 1
1 3
2 7
0 4
6 5
14 19 449 2
1 3
2 0
6 4
7 5
23 12 59 3
5 3
2 7
0 4
6 1
18 14 62 4
5 3
2 0
6 4
7 1
27 7
47 5
5 2
3 7
0 4
6 1
21 12 143 6
5 2
3 0
6 4
7 1
30 5
47 7
2 5
3 7
0 4
6 1
26 10 758 8
2 5
3 0
6 4
7 1
35 3
34
c
= сколько раз вычислялся предикат
(процедуры stable
).
Решение 0 оптимально для мужчин; решение 8 – для женщин.
Решение с наименьшим значением rm назовем стабильным решением, опти%
мальным для мужчин; решение с наименьшим rw
– оптимальным для женщин.
Характер принятой стратегии поиска таков, что сначала генерируются решения,
хорошие с точки зрения мужчин, а решения, хорошие с точки зрения женщин, –
в конце. В этом смысле алгоритм выгоден мужчинам. Это легко исправить путем систематической перестановки ролей мужчин и женщин, то есть просто меняя местами mwr и wmr
, а также rmw и rwm
Мы не будем дальше развивать эту программу, а задачу включения в програм%
му поиска оптимального решения оставим для следующего и последнего примера применения алгоритма обхода с возвратом.
3.7. Задача оптимального выбора
Наш последний пример алгоритма поиска с возвратом является логическим раз%
витием предыдущих двух в рамках общей схемы. Сначала мы применили прин%
цип возврата, чтобы находить одно решение задачи. Примером послужили задачи о путешествии шахматного коня и о восьми ферзях. Затем мы разобрались с поис%
ком всех решений; примерами послужили задачи о восьми ферзях и о стабильных браках. Теперь мы хотим искать оптимальное решение.
Для этого нужно генерировать все возможные решения, но выбрать лишь то,
которое оптимально в каком%то конкретном смысле. Предполагая, что оптималь%
ность определена с помощью функции f(s)
, принимающей положительные значе%
ния, получаем нужный алгоритм из общей схемы
Try заменой операции
v инструкцией
IF f(solution) > f(optimum) THEN optimum := solution END
161
Переменная optimum запоминает лучшее решение из до сих пор найденных.
Естественно, ее нужно правильно инициализировать; кроме того, обычно значе%
ние f(optimum)
хранят еще в одной переменной, чтобы избежать повторных вы%
числений.
Вот частный пример общей проблемы нахождения оптимального решения в некоторой задаче. Рассмотрим важную и часто встречающуюся проблему выбо%
ра оптимального набора (подмножества) из заданного множества объектов при наличии некоторых ограничений. Наборы, являющиеся допустимыми реше%
ниями, собираются постепенно посредством исследования отдельных объектов исходного множества. Процедура
Try описывает процесс исследования одного объекта, и она вызывается рекурсивно (чтобы исследовать очередной объект) до тех пор, пока не будут исследованы все объекты.
Замечаем, что рассмотрение каждого объекта (такие объекты назывались кандидатами в предыдущих примерах) имеет два возможных исхода, а именно:
либо исследуемый объект включается в собираемый набор, либо исключается из него. Поэтому использовать циклы repeat или for здесь неудобно, и вместо них можно просто явно описать два случая. Предполагая, что объекты пронумерова%
ны
0, 1, ... , n–1
, это можно выразить следующим образом:
PROCEDURE Try (i: INTEGER);
BEGIN
IF i < n THEN
IF
THEN
i- ;
Try(i+1);
i-
END;
IF
THEN
Try(i+1)
END
ELSE
END
END Try
Уже из этой схемы очевидно, что есть
2
n возможных подмножеств; ясно, что нужны подходящие критерии отбора, чтобы радикально уменьшить число иссле%
дуемых кандидатов. Чтобы прояснить этот процесс, возьмем конкретный пример задачи выбора: пусть каждый из n
объектов a
0
, ... ,
a n–1
характеризуется своим ве%
сом и ценностью. Пусть оптимальным считается тот набор, у которого суммарная ценность компонент является наибольшей, а ограничением пусть будет некото%
рый предел на их суммарный вес. Эта задача хорошо известна всем путешест%
венникам, которые пакуют чемоданы, делая выбор из n
предметов таким образом,
чтобы их суммарная ценность была наибольшей, а суммарный вес не превышал некоторого предела.
Теперь можно принять решения о представлении описанных сведений в гло%
бальных переменных. На основе приведенных соображений сделать выбор легко:
Задача оптимального выбора
Рекурсивные алгоритмы
162
TYPE Object = RECORD weight, value: INTEGER END;
VAR a: ARRAY n OF Object;
limw, totv, maxv: INTEGER;
s, opts: SET
Переменные limw и totv обозначают предел для веса и суммарную ценность всех n
объектов. Эти два значения постоянны на протяжении всего процесса вы%
бора. Переменная s
представляет текущее состояние собираемого набора объек%
тов, в котором каждый объект представлен своим именем (индексом). Перемен%
ная opts
– оптимальный набор среди исследованных к данному моменту, а maxv
–
его ценность.
Каковы критерии допустимости включения объекта в собираемый набор?
Если речь о том, имеет ли смысл включать объект в набор, то критерий здесь – не будет ли при таком включении превышен лимит по весу. Если будет, то можно не добавлять новые объекты к текущему набору. Однако если речь об исключении, то допустимость дальнейшего исследования наборов, не содержащих этого элемен%
та, определяется тем, может ли ценность таких наборов превысить значение для оптимума, найденного к данному моменту. И если не может, то продолжение по%
иска, хотя и может дать еще какое%нибудь решение, не приведет к улучшению уже найденного оптимума. Поэтому дальнейший поиск на этом пути бесполезен. Из этих двух условий можно определить величины, которые нужно вычислять на каждом шаге процесса выбора:
1. Полный вес tw набора s
, собранного на данный момент.
2. Еще достижимая с набором s ценность av
Эти два значения удобно представить параметрами процедуры
Try
. Теперь ус%
ловие
можно сформулирловать так:
tw + a[i].weight < limw а последующую проверку оптимальности записать так:
IF av > maxv THEN (* , #*)
opts := s; maxv := av
END
Последнее присваивание основано на том соображении, что когда все n
объек%
тов рассмотрены, достижимое значение совпадает с достигнутым. Условие
-
выражается так:
av – a[i].value > maxv
Для значения av – a[i].value
, которое используется неоднократно, вводится имя av1
, чтобы избежать его повторного вычисления.
Теперь вся процедура составляется из уже рассмотренных частей с добавлени%
ем подходящих операторов инициализации для глобальных переменных. Обра%
тим внимание на легкость включения и исключения из множества s
с помощью операций для типа
SET
. Результаты работы программы показаны в табл. 3.5.
163
TYPE Object = RECORD value, weight: INTEGER END; (* ADruS37_OptSelection *)
VAR a: ARRAY n OF Object;
limw, totv, maxv: INTEGER;
s, opts: SET;
PROCEDURE Try (i, tw, av: INTEGER);
VAR tw1, av1: INTEGER;
BEGIN
IF i < n THEN
(* *)
tw1 := tw + a[i].weight;
IF tw1 <= limw THEN
s := s + {i};
Try(i+1, tw1, av);
s := s – {i}
END;
(* *)
av1 := av – a[i].value;
IF av1 > maxv THEN
Try(i+1, tw, av1)
END
ELSIF av > maxv THEN
maxv := av; opts := s
END
END Try;
Задача оптимального выбора
Таблица 3.5.
Таблица 3.5.
Таблица 3.5.
Таблица 3.5.
Таблица 3.5. Пример результатов работы программы Selection при выборе из 10 объектов (вверху). Звездочки отмечают объекты из отпимальных наборов opts для ограничений на суммарный вес от 10 до 120
:
10 11 12 13 14 15 16 17 18 19
: 18 20 17 19 25 21 27 23 25 24
limw
↓
maxv
10
*
18 20
*
27 30
*
*
52 40
*
*
*
70 50
*
*
*
*
84 60
*
*
*
*
*
99 70
*
*
*
*
*
115 80
*
*
*
*
*
*
130 90
*
*
*
*
*
*
139 100
*
*
*
*
*
*
*
157 110
*
*
*
*
*
*
*
*
172 120
*
*
*
*
*
*
*
*
183
Рекурсивные алгоритмы
164
PROCEDURE Selection (WeightInc, WeightLimit: INTEGER);
BEGIN
limw := 0;
REPEAT
limw := limw + WeightInc; maxv := 0;
s := {}; opts := {}; Try(0, 0, totv);
UNTIL limw >= WeightLimit
END Selection.
Такая
схема поиска с возвратом, в которой используются ограничения для предотвращения избыточных блужданий по дереву поиска, называется
методомветвей и границ (branch and bound algorithm).
Упражнения3.1. (Ханойские башни.) Даны три стержня и n
дисков разных размеров. Диски могут быть нанизаны на стержни, образуя башни. Пусть n
дисков первона%
чально находятся на стержне
A
в порядке убывания размера, как показано на рис. 3.9 для n = 3
. Задание в том, чтобы переместить n
дисков со стержня
A
на стержень
C
, причем так, чтобы они оказались нанизаны в том же порядке.
Этого нужно добиться при следующих ограничениях:
1. На каждом шаге со стержня на стержень перемещается только один диск.
2. Диск нельзя нанизывать поверх диска меньшего размера.
3. Стержень
B
можно использовать в качестве вспомогательного хранилища.
Требуется найти алгоритм выполнения этого задания. Заметим, что башню удобно рассматривать как состоящую из одного диска на вершине и башни,
составленной из остальных дисков. Опишите алгоритм в виде рекурсивной программы.
3.2. Напишите процедуру порождения всех n!
перестановок n
элементов a
0
, ..., a n–1
in situ, то есть без использования другого массива. После порожде%
ния очередной перестановки должна вызываться передаваемая в качестве па%
раметра процедура
Q
, которая может, например, печатать порожденную пере%
становку.
Рис. 3.9. Ханойские башни
165
Подсказка. Считайте, что задача порождения всех перестановок элементов a
0
, ..., a m–1
состоит из m
подзадач порождения всех перестановок элементов a
0
, ..., a m–2
, после которых стоит a
m–1
, где в i
%й подзадаче предварительно были переставлены два элемента a
i и a
m–1 3.3. Найдите рекурсивную схему для рис. 3.10, который представляет собой су%
перпозицию четырех кривых
W
1
,
W
2
,
W
3
,
W
4
. Эта структура подобна кривым
Серпиньского (рис. 3.6). Из рекурсивной схемы получите рекурсивную про%
грамму для рисования этих кривых.
Рис. 3.10. Кривые
W
1
–
W
4 3.4. Из 92 решений, вычисляемых программой
AllQueens в задаче о восьми фер%
зях, только 12 являются существенно различными. Остальные получаются отражениями относительно осей или центральной точки. Придумайте про%
грамму, которая определяет 12 основных решений. Например, обратите вни%
мание, что поиск в столбце 1 можно ограничить позициями 1–4.
3.5. Измените программу для задачи о стабильных браках так, чтобы она находи%
ла оптимальное решение (для мужчин или женщин). Получится пример применения метода ветвей и границ, уже реализованного в задаче об опти%
мальном выборе (программа
Selection
).
3.6. Железнодорожная компания обслуживает n
станций
S
0
, ... ,
S
n–1
. В ее планах –
улучшить обслуживание пассажиров с помощью компьютеризованных информационных терминалов. Предполагается, что пассажир указывает свои станции отправления
SA
и назначения
SD
и (немедленно) получает расписа%
Упражнения
Рекурсивные алгоритмы
166
ние маршрута с пересадками и с минимальным полным временем поездки.
Напишите программу для вычисления такой информации. Предположите,
что график движения поездов (банк данных для этой задачи) задан в подхо%
дящей структуре данных, содержащей времена отправления (= прибытия)
всех поездов. Естественно, не все станции соединены друг с другом прямыми маршрутами (см. также упр. 1.6).
3.7. Функция Аккермана
A
определяется для всех неотрицательных целых аргу%
ментов m
и n
следующим образом:
A(0, n) = n + 1
A(m, 0) = A(m–1, 1) (m > 0)
A(m, n) = A(m–1, A(m, n–1)) (m, n > 0)
Напишите программу для вычисления
A(m,n)
, не используя рекурсию. В ка%
честве образца используйте нерекурсивную версию быстрой сортировки
(программа
NonRecursiveQuickSort
). Сформулируйте общие правила для преобразования рекурсивных программ в итеративные.
Литература
[3.1] McVitie D. G. and Wilson L. B. The Stable Marriage Problem. Comm. ACM, 14,
No. 7 (1971), 486–492.
[3.2] McVitie D. G. and Wilson L. B. Stable Marriage Assignment for Unequal Sets.
Bit, 10, (1970), 295–309.
[3.3] Space Filling Curves, or How to Waste Time on a Plotter. Software – Practice and Experience, 1, No. 4 (1971), 403–440.
[3.4] Wirth N. Program Development by Stepwise Refinement. Comm. ACM, 14,
No. 4 (1971), 221–227.
Скачать 2.67 Mb.