31

Практическая работа №3.

Тема: Изучение алгоритмов покрытия.

Цель: освоение методов и алгоритмов полного перебора и сокращение перебора при нахождении покрытий.

				Постановка задачи.
Пусть	B = {b1, . . . , bn}-			опорное множество.				Имеется		множество
подмножеств	A = {A ,..., A }			множества		В		m	A = B) . Каждому
							(A B, U
подмножеству Ai		1	m			ai ,	i	i = 1	i
		сопоставлено			число		называемое ценой.			Множество
P = {A1,..., Al}(l ≤ m)		называется решением				задачи о		покрытии		или	просто
покрытием,	если	выполняется			условие		l	= B ,	при	этом	цена
							U Aj
							j =1

l

S = ∑ a j → min . Термин покрытие означает, что совокупность множеств j =1

A1,..., Al содержит все элементы множества В, т.е. “покрывает” множество В.

Определение 3.1.1. Безизбыточным называется покрытие, если при удалении из него хотя бы одного элемента оно перестает быть покрытием.

Иначе -		покрытие избыточно.
	Определение 3.1.2. Покрытие Р называется минимальным, если его цена
S =	l	a j - наименьшая среди всех покрытий данной задачи.
	∑
	j =1

Определение 3.1.3. Покрытие Р называется кратчайшим, если l –

наименьшее среди всех покрытий данной задачи.

Теорема 3.1.1. Минимальные и кратчайшие покрытия – безизбыточны. Имеются следующие варианты формулировки задачи о покрытии.

1.Требуется найти все покрытия. Для решения задачи необходимо выполнить полный перебор всех подмножеств множества А.

2.Требуется найти только безизбыточные покрытия. Не существует простого и эффективного алгоритма, не требующего построения всех избыточных покрытий; хорошо, если уменьшается их количество. Используется граничный перебор либо разложение по столбцу в таблице покрытий (ТП).

3.Требуется найти одно безизбыточное покрытие. Решение задачи основано на сокращении ТП.

Задачи о покрытии могут быть решены точно (при небольшой размерности) либо приближенно.

Для нахождения точного решения используются следующие алгоритмы.

1.Алгоритм полного перебора. Основан на методе упорядочения перебора подмножеств множества А.

2.Алгоритм граничного перебора по вогнутому множеству. Основан на одноименном методе сокращения перебора.

3.Алгоритм разложения по столбцу ТП. Основан на методе сокращения перебора, который состоит в рассмотрении только тех строк ТП, в которых имеется “ 1 ” в выбранном для разложения столбце.

4.Алгоритм сокращения ТП. Основан на методе построения циклического остатка ТП, покрытие для которого далее строится методами граничного перебора либо разложение по столбцу.

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

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

l

UAij = B .

j=1

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

Таблица покрытий.

Удобным и наглядным представлением исходных данных и их преобразований в задаче о покрытии является таблица покрытий. Таблица покрытий – это матрица Т отношения принадлежности элементов множеств Ai A опорному множеству В. Столбцы матрицы Т сопоставлены элементам

если

b

B

b

A

множества В, строки – элементам множества

А: T

1,

=

если

j

j

i .

0,

b

j

B b

j

A

Нули в матрице Т не проставляются.

i

Пример 3.2.1. Некоторый

писатель

выпустил

множество

сборников

A = { A1,..., A7 },

содержащее в совокупности

все

множествоB = {b1,...,b9 }

его

сочинений

(

таблица 3.2.1.). Каждый сборник

Ai

содержит

некоторое

подмножество сочинений

из

В ( Ai B )

и

имеет

некоторую

цену

ai .

Необходимо

найти такое

множество

P = { A1,..., Al },( Ai B,l ≤ 7)

сборников,

чтобы

в их

совокупности

содержались

все сочинения

данного

автора

l

A

= B

и

чтобы при

этом цена

S =

l

a

такого полного

собрания

U

∑

i =1

i

j =1

ij

сочинений была наименьшей, либо количество l сборников было минимальным.

Таблица 3.2.1.
		b1	b2	b3	b4	b5	b6	b7	b8	b9	a
	A1	1		1		1	1				1
	A2	1	1		1				1		2,5
	A3		1			1		1			2
	A4			1					1	1	1,5
	A5				1	1			1	1	3
	A6			1		1	1	1		1	7
	A7		1		1		1				1

	Возможным решением примера 3.2.1. будут следующие множества:
P1 = {A1, A3, A5}, A1 A3 A5 = B ; S1 = 1+ 2 + 3 = 6; l1 = 3;
P = {A , A			}, A A = B ; S		2	= 2,5+ 7 = 9,5; l = 2;
2	2	6	2	6		2

P3 = {A1, A3, A4, A7}, A1 A3 A4 A7 = B ; S3 = 1+ 2 +1,5+1 = 5,5; l3 = 4 .

На языке отношения принадлежности задача о покрытии формулируется как задача построения таких подмножеств Pi строк таблицы покрытия (ТП), чтобы в совокупности строк, входящих в Pi , во всех столбцах были “ 1”

(единицы в некотором столбце могут повторяться). Такое подмножество строк называется покрытием.

Алгоритм полного перебора.

Будем считать, что подмножества Ai пронумерованы A1,..., Am и таким

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

строки, из двух строк и т.д. …, из всех строк, т.е. всего 2m подмножеств:

D = { ,{A1},...,{Am},{A1, A2},...,{A1, Am},...,{A1,..., Am}}.

Словесное описание алгоритма:

0.Текущее подмножество D = {A1},i = 0 ;

1.i=i+1. Запоминаем множество D , как очередное построенное подмножество Di ;

2.Находим наибольший номер j элемента Aj D ;

2.1. Если j не равно n ( n – количество подмножеств Ai				), то переходим к
	п.3;
2.2.	Если j = n, то удаляем	An из D	и если D = ,	то	заканчиваем
	построение; если D ≠ -	находим	наибольший номер		j элемента
	Aj D и удаляем Aj из D .
3.	j=j+1. Вводим в D элемент Aj . Переходим к п.1.

Алгоритм граничного перебора по вогнутому множеству.

Алгоритм генерации подмножеств должен гарантировать, что при его последовательном применении можно построить, начиная с некоторого начального подмножества все возможные подмножества; при этом не должно быть повторений и должен существовать критерий окончания перебора. В п.1.3. упорядочение произведено сначала по числу i элементов, а затем для фиксированного i - по лексикографическому правилу относительно номеров подмножеств.

Более удобный для дальнейшего упрощения процесса решения алгоритм полного перебора заключается в следующем: сначала строятся все подмножества Di содержащие A1, затем - содержащие A2, но не содержащие

A1; если построено подмножество Di , то за ним строится подмножество Di + j ,

целиком содержащее Di ( Di Di + j ). Во многих приложениях достаточно

находить только безизбыточные покрытия ( теорема 3.1.1. ), что естественным образом сокращает перебор. Однако не удается найти простой и эффективный алгоритм, не требующий построения всех избыточных покрытий. Идея изменения алгоритма перебора ( генерации ) подмножеств заключается в следующем: если в текущее подмножество - покрытие, то в это подмножество не нужно вводить новые элементы.

Теорема 3.4.1.	Если P	покрытие,	то и	P' P тоже	покрытие,	т.е.
множество всех возможных покрытий вогнуто.
Безизбыточные	покрытия	- это	граница	вогнутого	множества	всех

покрытий, поэтому модифицированный алгоритм носит название “Алгоритм граничного перебора по вогнутому множеству”.

Словесное описание алгоритма:

0.Текущее подмножество D = {A1},i = 0. Выполняем п.4;

1.Находим наибольшей номер j элемента в подмножестве D ; 1.1. Если j не равен n и D - не покрытие, то выполняем п.3; 1.2. Если j не равен n и D - покрытие, то выполняем п.2;

1.3. Если j = n, то удаляем An из D , и если D = , то выполняем п.5, иначе

–снова находим наибольший номер j элемента в D и выполняем п.2;

2.Удаляем элемент Aj из D ;

3.j=j+1. Вводим элемент Aj в D ;

4.Выясняем, является ли D покрытием;

4.1.Если очередное построение в D - покрытие, то удаляем из ранее построенных покрытий те, которые поглощают D (избыточные

покрытия), соответственно сокращая i и запоминаем, D как покрытие Pi(i = i +1; Pi = D). Переходим к п.1;

4.2. Если построение в D не является покрытием, то выполняем п.1;

5.Заканчиваем построение всех безизбыточных покрытий.

Контрольные задачи.

1. Построить минимальное покрытие методом граничного перебора.

	1		1		2		3		4		5		6	а
	А		1		0		1		0		0		1	2
		Б	1		0		0		1		1		0	1
	В		1		0		0		1		1		0	3
		Г	0		1		1		0		0		1	4
	3		1		2		3		4		5		6	а
	А		1		1		0		0		0		1	2
		Б	1		0		0		1		0		0	3
	В		1		0		0		0		1		1	2
		Г	0		1		1		0		0		1	1
	5		1		2		3		4		5		6	а
	А		1		1		1		0		0		0	3
		Б	0		0		1		1		1		0	2
	В		1		0		1		1		0		0	5
		Г	1		0		0		1		0		1	2
		7		1		2		3		4		5	6	а
		А		1		1		1		0		0	0	3
		Б		0		1		1		0		1	0	2
		В		1		0		0		1		1	0	4
		Г		1		1		0		0		0	1	2

2	1	2	3	4	5	6	а
А	1	0	0	1	1	0	1
Б	1	1	1	0	0	0	3
В	0	1	0	1	0	1	3
Г	0	1	1	0	0	1	5
4	1	2	3	4	5	6	а
А	1	0	1	0	0	1	1
Б	0	1	0	1	0	1	1
В	1	1	0	0	1	0	2
Г	0	1	0	1	1	0	5
6	1	2	3	4	5	6	а
А	1	0	1	0	0	1	2
Б	0	0	0	1	1	0	2
В	0	1	0	0	1	1	2
Г	1	1	0	0	0	1	4
8	1	2	3	4	5	6	а
А	0	1	1	0	0	1	2
Б	1	0	0	1	0	1	1
В	1	0	1	0	1	0	3
Г	0	1	0	1	0	1	3

Практическая работа №4.

Тема: Изучение алгоритмов покрытия (продолжение).

Цель: освоение методов и алгоритмов полного перебора и сокращение перебора при нахождении покрытий.

Сокращение таблицы покрытий.

Теорема 4.1. (о ядре). Если в столбце таблицы покрытий содержится единственная 1, то строка, содержащая эту единицу 1, входит во все покрытия и называется ядерной.

Множество ядерных строк заранее выделяется и запоминается для выделения во все покрытия. Ядерные строки из таблицы покрытий удаляются и вычеркиваются все покрытые ими столбцы, т.е. вычеркиваются все столбцы, в которых есть 1 в ядерных строках.

Теорема 4.2. (об антиядре). Если после удаления ядерных строк и покрытых ими столбцов в какой-либо строке не останется 1, то эта строка не

входит ни в одно безизбыточное покрытие. Такие	строки	называются
антиядерными и вычеркиваются из таблицы покрытий без запоминания.
Определение 4.1. Вектор E = (e1,...,em) поглощает	вектор	F = (f1,..., fm),

E ≥ F , если для любых компонент ei , fi этих векторов можно одновременно записать ei ≥ fi ;

E = 1 1 0 1;F = 0 1 0 1 ;E ≥F .

e1e2e3e4		f1 f2 f3 f4
Теорема	4.3.	(о поглощающих столбцах). В таблице покрытий
могут быть	вычеркнуты все поглощающие столбцы (рассматриваемые как
векторы) без ущерба для построения всех безизбыточных покрытий.
Теорема	4.4.	(о поглощаемых строках при поиске одного

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

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

Используя теоремы 4.1. – 4.5. упрощаем таблицу покрытий. При этом возможны два исхода:

1.Таблица покрытий упрощается, после упрощения становится пустой – вычеркнуты все столбцы. В этом случае множество ядерных строк – требуемое покрытие;

2.Остаток таблицы покрытий более не упрощается приемами из теорем

4.1.– 4.5. Получаем циклический остаток таблицы покрытий. Покрытие

циклического остатка таблицы можно строить методами: 1. Граничным перебором;

2. Разложением по столбцу. Когда к ядерным строкам добавляются строки покрытий циклического остатка, получается покрытие исходной таблицы покрытий.

Алгоритм построения циклического остатка таблицы покрытий и множества ядерных строк для случая построения одного кратчайшего покрытия.

Словесное описание алгоритма: Словесное описание алгоритма:

0.Считаем исходную таблицу покрытий текущей, а множество ядерных строк – пустым;

1.Находим ядерные строки, запоминаем множество ядерных строк. Текущую таблицу покрытий сокращаем: вычеркиваем ядерные строки и все столбцы, покрытые ими;

2.Вычеркиваем антиядерные строки;

3.Вычеркиваем поглощающие столбцы;

4.Вычеркиваем поглощаемые строки;

5.Если в результате выполнения п.1 – 4 текущая таблица покрытий изменилась, снова выполняем п.1, иначе преобразования заканчиваем.

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

При сокращении таблицы покрытий до циклической, при построении минимального покрытия изменяется только п.4 алгоритма, который формулируется следующим образом:

4’. Вычеркиваются поглощаемые строки, веса которых не меньше весов соответствующих поглощающих строк.

При сокращении таблицы покрытий до циклической, при условии построения всех безизбыточных покрытий п.4 не выполняется: в этом случае нельзя вычеркивать никакие поглощаемые строки.

Метод минимального столбца - максимальной строки.

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

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

1.Исходная таблица считается текущей преобразуемой таблицей покрытий, если множество строк покрытий - пусто;

2.В текущей таблице выделяется столбец с наименьшим числом единиц. Среди строк, содержащих единицы в этом столбце, выделяется она с наибольшим числом единиц. Эта строка включается в покрытие, текущая таблица сокращается вычеркиванием всех столбцов, в

которых выбранная строка имеет единицу. Если в таблице есть не вычеркнутые столбцы, то выполняется пункт 2, иначе - покрытие построено. При подсчете числа единиц в строке учитываются единицы в не вычеркнутых столбцах.

Контрольные задачи.

1.Сократить следующие таблицы покрытий с гарантией построения одного кратчайшего покрытия.

1	1	2	3	4	5	6	7	8	9	1
А			1				1	1		1
Б	1	1					1		1
В	1			1		1				1
Г			1	1	1
Д						1			1	1
Е							1	1
Ж		1	1		1
З						1		1

2	1	2	3	4	5	6	7	8	9	1
А		1					1	1
Б	1			1
В						1			1
Г		1	1						1	1
Д				1				1
Е	1					1				1
Ж			1		1				1
З	1				1	1	1

3	1	2	3	4	5	6	7	8	9	1
А	1	1						1
Б		1	1		1		1
В				1			1
Г				1				1
Д		1				1			1	1
Е			1				1			1
Ж	1				1	1			1
З			1			1

5	1	2	3	4	5	6	7	8	9	10
А				1	1		1	1
Б			1	1		1
В		1							1
Г					1			1		1
Д			1					1
Е						1			1
Ж	1		1			1	1		1
З	1	1								1

4 1 2 3 4 5 6 7 8 9 1

	А				1		1 1 1
	Б 1		1				1			1
	В				1 1 1
	Г		1											1
	Д 1				1
	Е		1 1							1
	Ж1									1 1
	З						1							1
6		1	2	3	4	5		6	7		8	9		1
А			1								1
Б				1				1
В		1	1			1
Г					1						1	1
Д		1			1						1			1
Е					1			1
Ж			1			1			1					1
З				1					1			1

2.Решить задачи о покрытии методом минимального столбца - максимальной строки.

	1			1			2			3			4		5		6		7		8	9	А
	А									1			1						1				1
		Б		1											1								1
		В					1			1			1						1			1	2
		Г					1						1		1				1		1		4
	Д			1						1							1					1	3
		Е													1						1	1	1
	Ж						1										1				1	1	2
3			1			2			3			4		5		6		7		8		9	А
А						1			1					1						1			3
Б			1						1			1								1			2
В			1									1				1		1				1	4
Г						1										1						1	1
Д									1			1										1	2
Е			1															1		1			2
Ж						1								1		1		1					1
		5			1			2			3		4		5		6		7		8	9	А
		А									1				1		1						1
		Б			1								1									1	2
		В			1			1							1		1					1	2
		Г			1			1											1				1
		Д									1		1						1		1		4
		Е									1		1				1				1	1	2
		Ж						1							1						1		3

2	1		2		3		4		5		6		7		8		9		А
А							1		1				1						1
Б	1										1						1		2
В	1						1		1						1		1		3
Г					1										1		1		1
Д			1		1						1		1						3
Е	1		1				1				1		1						2
Ж			1						1						1				2
4		1		2		3		4		5		6		7		8		9		А
А								1								1				2
Б				1		1						1						1		1
В										1				1				1		3
Г		1						1						1				1		2
Д		1		1		1				1										1
Е		1		1		1		1				1				1				3
Ж												1		1		1				2
6	1		2		3		4		5		6		7		8		9		А
А			1						1				1		1				2
Б			1								1		1				1		2
В	1				1		1				1						1		3
Г	1						1								1				1
Д	1										1		1						3
Е			1		1												1		2
Ж					1		1		1						1				1

Практическая работа №5.

Тема: Конечный автомат.

Цель: Изучить работу автоматов Мили и Мура, а также их взаимное преобразование.

		Автоматы Мили и Мура.
Конечный автомат -		это набор из пяти элементов À = {S, X,Y,δ, λ}, где
S = {s1,..., sm}-	алфавит	внутренних состояний (конечное множество),
X = {x1,..., xn}- конечное множество входных состояний или входной алфавит,
Y = {y1,...,yk }-	конечное	множество выходных состояний или выходной
алфавит, δ - функция переходов: S × X → S , λ - функция выходов: S × X →Y .
	Краткое описание работы автомата.

Пусть в момент времени t автомат имел внутреннее состояние si и входное xi . Функция перехода δ определяет состояние sk автомата в момент времени t +1 в ответ на полное состояние si xi . Функция выхода λ определяет выход yi в соответствие полному состоянию si xi ( в этом случае автомат называется автоматом Мили ) или внутреннему состоянию si ( в этом случае автомат называется автоматом Мура ).

Для автомата Мили:	S(t +1) = δ(S(t), x(t)) ,	λ: S × X → Y .
	y(t) = λ(S(t), x(t))	t = 0,12, ,....
Для автомата Мура:	S(t +1) = δ(S(t), x(t))		, λ: S → Y .
	y(t) = λ(S(t)) = λ(δ(S(t −1), x(t −1)))

Для описания работы автомата чаще всего используют таблицы и графы переходов. В таблице 5.1 приведен пример представления автомата Мили, а в таблице 5.2. - пример представления автомата Мура.

Таблица 5.1.

	x1			…		xn
s1	δ(s1,x1)/λ(s1,x1)			…		δ(s1,xn)/λ(s1,xn)
…	…			…		…
						δ(sk ,xn)/λ(sk,xn)
sk	δ(sk ,x1)/λ(sk,x1)			…
						Таблица 5.2.
		x1			…		xn
	λ(s1) / s1	δ(s1, x1)			…		δ(s1, xn )
	…	…			…		…
	λ(sk ) / s1	δ(sk , x1)			…		δ(sk , xn )