“Dag’al kuch” usuli bilan tartiblashtirish. Kommivoyajer haqida masala Rеja

Eng qisqa yo’llar bo’yicha aniqlasak

• 1-> 2 -> 4 -> 3 -> 1
• L=5+7+15+7 =34
• 1-> 4 -> 2 -> 9 -> 1
• L=9 +6 +8 + 7=30
• Endi algoritmni ko’rib chiqamiz.
• Jadval ko’rinishda yozib olamsiz.
• Satrlar bo’yicha minimumni aniqlaymiz

3) Reduksiya(satrlar reduksiyasi) (soddalashtirish, o’zgartirish, hosil qilish)

Shahar	1	2	3	4	di
1	M	5	11	9	5
2	10	M	8	7	7
3	7	14	M	8	7
4	12	6	15	M	6

Matritsa elementlarining har biridan tegishli minimal qiymatlarini ayirib chiqamiz

	1	2	3	4
1	M	0	6	4	5
2	3	M	1	0	7
3	0	7	M	1	7
4	6	0	9	M	6

4) Ustunlar bo’yicha minimal elementlarni aniqlaymiz

SH	1	2	3	4
1	M	0	6	4
2	3	M	1	0
3	0	7	M	1
4	6	0	9	M
di	0	0	1	0

5) Matritsa ustunlari reduksiyasi

SH	1	2	3	4	Di
1	M	0	5	4	5
2	3	M	0	0	7
3	0	7	M	1	7
4	6	0	8	M	6
dj	0	0	1	0

6) 0 li kataklarni baholash Baholash bu kataklarni bahosi deganda tegishli satr va ustun minimumlari yig’indisini tushunamiz

SH	1	2	3	4
1	M	0(4)	5	4
2	3	M	0 (5)	0 (1)
3	(4) 0	7	M	1
4	6	0 (6)	8	M

Yan gi matritsani hosil qilamiz

SH	1	2	3	4
1	M	4	5	4
2	3	M	5	1
3	4	7	M	1
4	6	6	8	M

7) Matritsani reduksiyalash 0 qiymatli kataklar orasidan bahosi eng katta bo’lganini tanlab olamiz. Bu katakni M qiymat bilan almashtiramiz.

SH	1	2	3	4
1	M	0(4)	5	4
2	3	M	0 (5)	0 (1)
3	0 (4)	7	M	1
4	6	M 0 (6)	8	M

• 4->2 ga beriladi.
• 2 ta M paydo bo’lgan satr va ustunni chiqarib tashlaymiz.

2) 4-> 2 ga borgani uchun 2-> 4 ga borilmaydi va M qo’yiladi

Sh	1	3	4	di
1	M	5	4
2	3	0(5)	0(1) M
3	0 (4)	M	1
dj

3) Satrlar reduksiyasi

Sh	1	3	4	di
1	M	5	4	4
2	3	0	M	0
3	0	M	1	0
dj

4)

Sh	1	3	4	di
1	M	1	0	4
2	3	0	M	0
3	0	M	1	0
dj

5)

Sh	1	3	4	di
1	M	1	0	4
2	3	0	M	0
3	0	M	1	0
dj	0	0	0

6)

Sh	1	3	4	di
1	M	1	0	4
2	3	0	M	0
3	0	M	1	0
dj	0	0	0

7)

Sh	1	3	4	di
1	M	1	0 (1)	4
2	3	0 (3)	M	0
3	0(1)	M	1	0
dj	0	0	0

2->3

Sh	1	3	4	di
1	M	1	0 (1)	4
2	3	M	M	0
3	0(1)	M	1	0
dj	0	0	0

8)

Sh	1	4
1	M	1
3	0	1

• 4->2->3->1->4
• L=6+8+7+9=30

• E’tibor uchun rahmat