|
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.
|
-
|
1
|
2
|
7
|
5
| |
1
|
-
|
4
|
4
|
3
| |
2
|
4
|
-
|
1
|
2
| |
7
|
4
|
1
|
-
|
3
| |
5
|
3
|
2
|
3
|
-
|
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.
Kommivoyajer (fr. commis voyageur) — sayohatchi savdogar. Kommivoyajer masalasi transport logistikasida muhim vazifa bo'lib, transportni rejalashtirish bilan shug'ullanadigan sanoatdir. Kommivoyajer uy xo'jaligida zarur bo'lgan va unchalik zarur bo'lmagan tovarlarni sotish uchun n nuqtani aylanib o'tishi va oxir-oqibat boshlang'ich nuqtasiga qaytishi kerak. Bu eng foydali aylanma marshrutni aniqlash uchun talab qilinadi. Marshrut rentabelligining o'lchovi sifatida (aniqrog'i, kamchilik) umumiy sayohat vaqti, yo'lning umumiy qiymati yoki eng oddiy holatda, marshrut uzunligi bo'lishi mumkin.
Kommivoyajer masalasi eng mashhur kombinatoriy optimallashtirish masalalaridan biri bo'lib, u belgilangan shaharlardan kamida bir marta o'tib, keyin asl shaharga qaytib keladigan eng foydali marshrutni topishdan iborat.
Ko'rinib turibdiki, masalani aylanma yo'lning barcha variantlarini sanab o'tish va eng maqbulini tanlash orqali hal qilish mumkin. Masala shundaki, mumkin bo'lgan marshrutlar soni n o'sishi bilan juda tez o'sib boradi (u n ga teng! - nuqtalarni buyurtma qilish mumkin bo'lgan usullar soni).
Masalan, 100 ball uchun variantlar soni 158 xonali raqam bilan ifodalanadi - hech qanday kalkulyator bunga dosh berolmaydi! Bir soniyada million variantni saralashga qodir kuchli kompyuter 310 144 yil davomida masala bilan kurashadi. Kompyuterning ishlashini 1000 baravar oshirish, garchi 1000 baravar kam bo'lsa-da, lekin variantlarni sanab o'tish uchun dahshatli vaqtni beradi. Har bir marshrut varianti uchun boshlang'ich nuqta (n variant) va aylanma yo'nalish (2 variant) tanlashda farq qiluvchi 2 * n ekvivalent mavjudligi ham vaziyatni saqlab qolmaydi. Ushbu kuzatishni hisobga olgan holda ro'yxatga olish variantlar bo'yicha biroz qisqartiriladi.
|
