Фіксуємо елемент х3 в позиції р4

4. Вибираємо елемент Х4.

1. Закріплюємо елемент Х4 в позиції Р1

Х4
	2
		Х3	Х2
	Х1

Підраховуємо нижню границю

F4(1) = f 4(1),н + f4(1), 1(3) + f4(1), 1(5) + f4(1), 3(4) +

f1(3), н + f2(5), н + f3(4), н + f1(3), 2(5) + f1(3), 3(4) + f2(5),3(4)

r 4(1),н = 1 d 4(1),н = 2 f 4(1),н = 2

r4(1) , 1(3) = 0 d4(1) , 1(3) = 4 f4(1) , 1(3) = 0

r4(1) , 2(5) = 0 d4(1) , 2(5) = 5 f4(1) , 2(5) = 0

r4(1) , 3(4) = 1 d4(1) , 3(4) = 4 f4(1) , 2(5) = 4

r 1(3), н = 3 d1(3), н = 2 f1(3), н = 6

r 2(5) , н = 2 d2(5) , н = 2 f2(5) , н = 4

r 3(4) , н = 2 d3(4) , н = 3 f3(4) , н = 6

r 1(3) , 2(5) = 1 d1(3) , 2(5) = 3 f1(3) , 2(5) = 3

r 2(5) , 3(4) = 3 d2(5) , 3(4) = 1 f2(5) , 3(4) = 3

r1(3) , 3(4) = 2 d1(3) , 3(4) = 2 f1(3) , 3(4) = 4

F4(1) = 2 +0+0+4+6+4+6+3+3+4 = 32

Враховуючи, що F3(4) = F4(1)

Фіксуємо елемент х4 в позиції р1 Фіксуємо елемент х5 в позиції р2

Х4
	Х5
		Х3	Х2
	Х1

Підраховуємо сумарну довжину з'єднань

Fсум = 1*3+2*2+0*4+3*2 + 3*1+0*5+2*3 + 1*4+2*2 + 1*2 = 3+4+0+6+3+0+6+4+4+2 = 32

Порядок виконання роботи

1. Використовуючи запропонований алгоритм, для заданого робочого поля і матриці зв'язності знайти оптимальне розташування елементів на робочому полі.

2. Скласти програму, яка реалізує запропонований алгоритм.

3. Порівняти часову і програмну складність алгоритмів повного перебору іпобудованого алгоритму

4. Скласти та захистити звіт з лабораторної роботи

.

Варіанти завдань

1									R					2									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X	X		x1	0	1	2	0	3					X	X	X		x1	0	1	3	0	2
	X		X	X		x2		0	3	0	2				X		X	X		x2		0	3	0	2
	X	X				x3			0	1	2				X	X				x3			0	2	1
	X		X	X		x4				0	1				X		X	X		x4				0	1
						x5					0									x5					0
3									R					4									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X	X		x1	0	1	3	0	3					X	X	X		x1	0	1	2	0	3
	X	X		X		x2		0	3	0	2				X	X		X		x2		0	2	0	3
	X	X				x3			0	1	2				X	X				x3			0	2	1
	X		X	X		x4				0	1				X		X	X		x4				0	1
						x5					0									x5					0
5									R					6									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X			x1	0	1	2	0	3					X	X			x1	0	1	3	0	2
	X		X	X		x2		0	3	0	2				X		X	X		x2		0	2	0	3
	X	X		X		x3			0	1	2				X	X		X		x3			0	2	1
	X		X	X		x4				0	1				X		X	X		x4				0	1
						x5					0									x5					0
7									R					8									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X			x1	0	1	2	0	3					X	X			x1	0	1	3	0	2
	X		X	X		x2		0	3	0	2				X		X	X		x2		0	2	0	3
	X	X		X		x3			0	1	2				X	X		X		x3			0	2	1
	X	X		X		x4				0	1				X	X		X		x4				0	1
						x5					0									x5					0
9									R					10									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X		X		x1	0	1	2	0	3					X		X		x1	0	1	3	0	2
	X		X	X		x2		0	3	0	2				X		X	X		x2		0	2	0	3
	X	X	X			x3			0	1	2				X	X	X			x3			0	2	1
	X		X	X		x4				0	1				X		X	X		x4				0	1
						x5					0									x5					0
11									R					12									R
	31						x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
	4	X	X	X		x1	0	2	3	0	4					X	X	X		x1	0	2	4	0	3
	X	3	X	X		x2		0	4	0	3				X		X	X		x2		0	3	0	4
	X	X	5	2		x3			0	2	3				X	X				x3			0	3	2
	X	1	X	X		x4				0	2				X		X	X		x4				0	2
				36		x5					0									x5					0
13									R					14									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X	X		x1	0	2	3	0	4					X	X	X		x1	0	2	4	0	3
	X	X		X		x2		0	4	0	3				X	X		X		x2		0	3	0	4
	X	X				x3			0	2	3				X	X				x3			0	3	2
	X		X	X		x4				0	2				X		X	X		x4				0	2
						x5					0									x5					0
15									R					16									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X			x1	0	2	3	0	4					X	X			x1	0	2	4	0	3
	X		X	X		x2		0	4	0	3				X		X	X		x2		0	3	0	4
	X	X		X		x3			0	2	3				X	X		X		x3			0	3	2
	X		X	X		x4				0	2				X		X	X		x4				0	2
						x5					0									x5					0
17									R					18									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X			x1	0	2	3	0	4					X	X			x1	0	2	4	0	3
	X		X	X		x2		0	4	0	3				X		X	X		x2		0	3	0	4
	X	X		X		x3			0	2	3				X	X		X		x3			0	3	2
	X	X		X		x4				0	2				X	X		X		x4				0	2
						x5					0									x5					0
19									R					20									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X		X		x1	0	2	3	0	4					X		X		x1	0	2	4	0	3
	X		X	X		x2		0	4	0	3				X		X	X		x2		0	3	0	4
	X	X	X			x3			0	2	3				X	X	X			x3			0	3	2
	X		X	X		x4				0	2				X		X	X		x4				0	2
						x5					0									x5					0

21									R					22									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
			X	X		x1	0	5	3	0	1						X	X		x1	0	5	3	0	1
		X		X		x2		0	3	0	2					X		X		x2		0	3	3	2
	X	X	X			x3			0	1	2				X	X	X			x3			0	1	2
	X	X	X	X		x4				0	5				X	X	X	X		x4				0	1
						x5					0									x5					0
23									R					24									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X	X		x1	0	5	3	0	1					X	X	X		x1	0	5	3	0	1
			X	X		x2		0	3	0	2						X	X		x2		0	3	3	2
	X	X		X		x3			0	1	2				X	X		X		x3			0	1	2
	X	X	X			x4				0	5				X	X	X			x4				0	1
						x5					0									x5					0
25									R					26									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
			X	X		x1	0	5	3	0	1						X	X		x1	0	5	3	0	1
	X	X		X		x2		0	3	0	2				X	X		X		x2		0	3	3	2
		X	X			x3			0	1	2					X	X			x3			0	1	2
	X	X	X	X		x4				0	5				X	X	X	X		x4				0	1
						x5					0									x5					0
27									R					28									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
		X	X	X		x1	0	5	3	0	1					X	X	X		x1	0	5	3	0	1
	X		X	X		x2		0	3	0	2				X		X	X		x2		0	3	3	2
		X		X		x3			0	1	2					X		X		x3			0	1	2
	X	X	X			x4				0	5				X	X	X			x4				0	1
						x5					0									x5					0
29									R					30									R
							x1	x2	x3	x4	x5										x1	x2	x3	x4	x5
			X	X		x1	0	5	3	0	1						X	X		x1	0	5	3	0	1
	X	X		X		x2		0	3	0	2				X	X		X		x2		0	3	3	2
	X	X	X			x3			0	1	2				X	X	X			x3			0	1	2
		X	X	X		x4				0	5					X	X	X		x4				0	1
						x5					0									x5					0

Зміст