Muhammad al-xorazmiy nomidagi toshkent axborot texnalogiyalari universiteti qarshi filiali kompyuter injineringi fakulteti ki-13-21 guruh diskret tuzilmalar fanidan

Qadam 0: [Insiallashtirish] TOUR:=0; COST:=0; V:=U; Qadam 1

Download 407,44 Kb.

bet	5/20
Sana	25.12.2022
Hajmi	407,44 Kb.
	#895982

1 2 3 4 5 6 7 8 9 ... 20

Bog'liq
7 DAN 12 GACHA

Qadam 0: [Insiallashtirish] TOUR:=0; COST:=0; V:=U;

Qadam 1: [Hama shaharlarni o’tish] For k:=1 to N-1 do qadam 2;

Qadam 2: [Keyingi vektorga o’tish]
Faraz qilaylik, (V,W) – V shahardan W ga olib borayotgan eng kichik narxli vektor. Unda:
TOUR:=TOUR+(V,W); COST:=COST+C(V,W);
V:=W;

Qadam 3: [Marshrutni tugatish] TOUR:=TOUR+(V,1);
COST:=COST+C(V,1);
Marshrutni tasvirlash uchun biz matematikada graf yoki tur deb nomlanayotgan chizmadan foydalanamiz. Umuman tur – bu nuqtalar va bir nechta yoki barcha ikki nuqtalarni bog’layotgan chiziqlar to’plami, undan tashqari chiziqlar ustida qiymatlar ham berilishi mumkin.
Masalani soddalashtirish uchun beshta shahar uchun yechim topamiz. Rasm. 1a – narxlar matrisasi. Rasm. 1b – turli model ko’rsatilgan.

Rasm 1-a). Narxlar matrisasi

Rasm 1-b). To’rsimon model

Turlar nazariyasida shaharlar ruyhati bir shahardan boshlab va o’sha shaharga barcha qolgan shaharlarni bir martadan o’tib qaytib kelish jarayonini belgilaydi. Bunday o’tishni marshrut deb ta’riflaymiz. Marshrut narxi chiziqlar ustidagi qiymatlar yig’indisi bilan aniqlanadi.
Rasm 2 algoritm GTS bo’yicha K marshrutni shahar1 dan boshlab tuzishni aks ettiradi.

Rasm 2. Algoritm qadamlari

GTS algoritmi bo’yicha marshrut narxi 14 ga teng. Bu yerda algoritm eng kichik narxli marshrutni topmaganini ko’ramiz. Masalan, marshrut 1-5-3-4-2-1 narxi 5+2+1+4+1=13.
Odatda yaqinlashgan algoritmlar tez bo’lsa ham, hamma vaqt optimal yechimni berolmaydilar. GTS algoritm uchun biz nazoratchi nisol topib bildik. Lekin, yaqinlashgan algoritm ishlamasligini isbotlash hamma vaqt ham oson bo’lmaydi.

GTS algoritmi uchun dastur yozish ancha yengil. Lekin uni tezligini tahlil qilib ko’raylik. Ixtiyoriy kommivoyajer masalasi uchun (besh shahardan iborat) C narxlar matrisasini o’qish va tuzishga operatsiya kerak. Demak, pastki murakkablik chegara algoritm uchun teng va GTS algoritmini yahshi evristik algoritm deb qabul qilishimiz mumkin.

Manba;hozir.org

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNALOGIYALARI UNIVERSITETI QARSHI FILIALI KOMPYUTER INJINERINGI FAKULTETI KI-13-21 GURUH DISKRET TUZILMALAR FANIDAN
10-MUSTAQIL ISH

BAJARDI: DJUMANIYOZOV S

QABUL QIDI: TURDIYEV U.Q

Download 407,44 Kb.

Do'stlaringiz bilan baham:

1 2 3 4 5 6 7 8 9 ... 20