Kommivayjer masalasi

Everistik 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: