1.2. Идея алгоритма Фаулкса

Итак, попытаемся найти путь в этом лабиринте, устанавливая возможные иерархии между различными частямиодежды.

Для простоты записи мы обозначим их буквами:

А — брюки,В — жилет,С — пиджак,D — галстук,Е — пальто,F — носки,G — обувь,H— перчатки.

Мы уверены, что наш друг при всей своей ловкости не сможет, например, надеть жилет позже пиджака; мы выразим это необходимое условие обозначением

В < С

(что можно читать как «В предшествуетC»). Зато ему безразлично, надеть ли прежде жилет или галстук, что запишется ввиде

В >< D.

Наконец, мы считаем почти немыслимым, чтобы он не обулся немедленно после того, как надел носки; отсюда напрашиваются общие обозначения

F |< G

(F непосредственно предшествуетG).

Подытожим подобные соотношения различных типов, допускаемые нашей задачей:

А <В,D, С;В <С; В >< D, F;

С < Е; D< С, Е, H;F |< G; G < С,H.

Эти соотношения могут выражаться рисунком или графом, о чем мы уже неоднократно говорили.

Граф, сампо себе, может быть представлен матрицей, если условиться обозначать единицей все реализуемые связи буквы, стоящей в строке, с буквой, указывающей столбец.

Матрица 1

	A	B	C	D	E	F	G	H
A	1	1	0	1	0	0	1	0
B	0	1	1	1	0	1	0	0
C	0	0	1	0	1	0	0	0
D	0	1	1	1	0	0	0	0
E	0	0	0	0	1	0	0	1
F	0	1	0	0	0	1	1	0
G	0	0	1	0	0	0	1	1
H	0	0	0	0	1	0	0	1

Рис. 16.1.

Теперь мы хотим определить, существует ли такой путь между какой-нибудь буквой, служащей входом, и какой-нибудь буквой, служащей выходом, который дал бы возможность нашему другу Фреголи одеться, не нарушая выписанных выше соотношений.

Чтобы справиться с этой задачей, выполним довольно специфическую операцию — умножение матрицы М (матрицы 1) на себя, заменяя, однако, обычную арифметическую сумму булевойсуммой элементов.

Мы не будем останавливаться на обсуждениях по поводу булевой суммы, таблицу которой мы приводим ниже и которая была предметом специального исследования в гл. 11:

+	A	B	A + B
	0 0 1 1	0 1 0 1	0 1 1 1

Таким образом, член произведения, расположенный в третьей клетке первой строки, является произведением строки A на столбецCи равен 1, если рассматривать булеву сумму элементов

Мы видим, что полученная матрица, которую мы обозначим через М[²], будет содержать только нули и единицы. Так же будет обстоять дело и сМ[⁴].

М[^2]=		A	B	C	D	E	F	G	H
	A	1	1	(1)	1		(1)	1	(1)
	B		1	1	1	(1)	1	(1)
	C			1		1			(1)
	D		1	1	1	(1)	(1)
	E					1			1
	F		1	(1)	(1)		1	1	(1)
	G			1		(1)		1	1
	H					1			1

Единицы, обозначенные (1), не входили в М и составляют частьМ[²].

М[^4]=		A	B	C	D	E	F	G	H
	A	1	1	1	1	1	1	1	1
	B		1	1	1	1	1	1	1
	C			1		1			1
	D		1	1	1	1	1	1	1
	E					1			1
	F		1	1	1	1	1	1	1
	G			1		1		1	1
	H					1			1

Из матрицы М[⁴] видно, чтоA является элементом, за которым может следовать (прямо или косвенно) любой другой, нокоторому никакой элемент не может предшествовать.

М′[^8]=		B	C	D	E	F	G	H
	B	1	1	1	1	1	1	1
	C		1		1			1
	D	1	1	1	1	1	1	1
	E				1			1
	F	1	1	1	1	1	1	1
	G		1		1		1	1
	H				1			1

Для вычисления М[⁸] нет надобности сохранять столбец и строкуA вМ[⁴]; мы получаемМ′[⁸], относительно которой легкозаметить, что она в точности равна соответствующей частиМ[⁴].

В этих условиях мы должны, согласно алгоритму Фаулкса¹,прекратить наши операции. Перестановкой строк и столбцов матрицуМ[⁴] можно представить в формеМ[⁴]; это означает, что задача порождает пять упорядоченных подграфов.

М[^4]=		A	F	B	D	G	C	E	H
	A	1	1	1	1	1	1	1	1
	F	0	1	1	1	1	1	1	1
	G	0	1	1	1	1	1	1	1
	E	0	1	1	1	1	1	1	1
	H	0	0	0	0	1	1	1	1
	D	0	0	0	0	0	1	1	1
	C	0	0	0	0	0	0	1	1
	B	0	0	0	0	0	0	1	1

Это множество обладает одним и только одним гамильтоновым путем², которым является путьADBFGCEH. Последнее означает, что наш друг Фреголи обладает одним и только одним способом одеться, как денди. Этот способ состоит в том,чтобы одеваться в таком порядке: галстук, жилет, носки, ботинки, пиджак, пальто, перчатки.

Некоторые аналогичные задачи могут привести к нескольким решениям; так, если бы в приведенном примере мы имелиD F, то существовало бы дополнительное решениеABDFGCEH.

Хотя мы описали алгоритм Фаулкса на столь забавном примере, ясно, что он может быть также использован при решении гораздо более серьезных задач.

Задачи о назначении в промышленности, например, могут носить такой же комбинаторный характер: речь может идти о выполнении некоторого числа операций на различных машинах; при этом на порядок этих операций могут быть наложены условия с помощью связей типа<, или |<.Когда имеется много машин и много операций, единственность решения встречается

Рис. 16.2.

Рис. 16.3.

редко. В этих условиях остается выбрать, согласно определенному критерию (в качестве которого могут выступать затраты или длительность процесса), лучший из возможных порядков, даваемых решениями задачи.