Mavzu: Kommivoyajer masalasi algoritmlarini o'rganish, chuqurlik va eni bo'yicha aylanib o'tuvchi graflar, kommivoyajer masalasini echish

Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

• Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:
• U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.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);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.