Toshpulatov Jasurbekning "Algoritmlarni loyihalash"

Evristik Algoritmlar: Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:
1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.
2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.

Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi. Misol tariqasida quyidagi algoritmni ko’rib chiqamiz:

GTS algoritmi: (kommivoyajer). N ta shaharlar va C narxlar matrisasi berilgan kommivoyajer masalasi uchun U shahardan boshlab COST narxli TOUR yaqinlashgan yechimni topish kerak.
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);

-	1	2	5	7
1	-	4	4	3
2	4	-	1	2
5	4	2	-	3
7	3	2	3	-

Rasm-1) Narxlar matrisasi

1

5 2

4 3
Rasm 2). 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 3. 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.