Sayohatchi sotuvchi muammosini tushunish

Sayohatchi sotuvchi muammosini tushunish

(TSP-travelling salesman problem)

Sayohatchi sotuvchi muammosi (TSP) - bu muayyan yo'nalishlar ro'yxati berilgan odam uchun eng qisqa, ammo eng samarali yo'lni topish muammosi. Bu kompyuter fanlari va operatsiyalarni tadqiq qilish sohalarida mashhur algoritmik muammodir.

Tanlash uchun juda ko'p turli xil yo'nalishlar bor, lekin eng yaxshisini topish - eng kam masofa yoki xarajatlarni talab qiladigan - matematiklar va kompyuter olimlari o'nlab yillar davomida hal qilishga harakat qilishgan.

TSP juda katta e'tiborni talab qildi, chunki uni tasvirlash juda oson, ammo hal qilish juda qiyin. Aslida, TSP NP-to'liq deb nomlanuvchi kombinatsion optimallashtirish muammolari sinfiga kiradi. Bu shuni anglatadiki, TSP NP-hard deb tasniflanadi, chunki u "tezkor" yechimga ega emas va muammoga ko'proq yo'nalish qo'shsangiz, eng yaxshi marshrutni hisoblashning murakkabligi ortadi. 

Muammoni eng qisqasini aniqlash uchun har bir aylanish yo'nalishini tahlil qilish orqali hal qilish mumkin. Biroq, yo'nalishlar soni ortib borayotganligi sababli, mos keladigan sayohatlar soni eng tezkor kompyuterlarning imkoniyatlaridan ham oshib ketadi. 10 ta yoʻnalish boʻyicha 300 000 dan ortiq aylanma oʻzgartirishlar va kombinatsiyalar boʻlishi mumkin. 15 ta yoʻnalish boʻlsa, mumkin boʻlgan yoʻnalishlar soni 87 milliarddan oshishi mumkin.

Mashhur sayohatchi sotuvchi muammolari yechimlari

Sayohatchi sotuvchi muammosining eng mashhur yechimlaridan ba'zilari: