Amaliy matematika va informatika” yo’nalishi 18. 08-guruh talabasi Topvoldiyev Muslimjon Muxtorjom o’g’lining

Evrestik algoritmlar. Tez yaxshi echimlarni beradigan turli evristik va yaqinlashuvchi algoritmlari ishlab chiqilgan. Bularga ko'p qismli algoritmlar deyiladi. Zamonaviy yechimlar katta muammolarni oz vaqt ichida echimini topishi mumkin, ular eng yaxshi echimdan atigi 2-3% uzoqlikda bo’lishi mumkin.

Evristikaning bir nechta toifalari tan olingan.

Konstruktiv evristika

Eng yaqin qo'shni algoritmi sotuvchiga keyingi harakat sifatida yaqin atrofdagi shaharni tanlashga imkon beradi.

Iterativ takomillashtirish

O'zaro almashish

Juft almashinish yoki 2 optli usul ikki qirralarni iterativ ravishda olib tashlash va ularni almashtirish orqali hosil qilingan parchalarni yangi va qisqaroq turga bog'laydigan ikki xil qirralarni almashtirishni o'z ichiga oladi. Xuddi shunday, 3-optik usul 3 qirrani olib tashlaydi va qisqa turni yaratish uchun ularni birlashtiradi. Bu k -opt usulining maxsus holatlari . Lin-Kernigan yorlig'i 2-opt uchun noto'g'ri eshitiladigan xato. Lin-Kernigan aslida k-opt usulining eng umumiy usuli hisoblanadi.

Evklid misollari uchun 2 optik evristik o'rtacha echimlarni beradi, ular Kristofidlar algoritmidan 5% yaxshi. Agar ochko'z algoritm yordamida qilingan dastlabki echimdan boshlasak , o'rtacha harakatlanish soni yana kamayadi va bo'ladi. {\ displaystyle O (n)}

Ammo tasodifiy boshlanishlar uchun o'rtacha harakat soni{\ displaystyle O (n \ log (n))}. Ammo bu ozgina kattalashish bo'lsa-da, kichik muammolar uchun boshlang'ich soni ochko'z evristik usul bilan solishtirganda tasodifiy boshlash uchun 10 baravar katta. Buning sababi shundaki, bunday 2 optik evristik echimning "yomon" qismlaridan, masalan, o'tish joylaridan foydalanadi. Ushbu turdagi evristikalar tez-tez marshrut echimlarini qayta tiklash uchun transport vositalarining marshrutlash muammolari evristikasida qo'llaniladi