|
Muhammad al-xozazmiy nomidagi toshkent axborot texnologiyalari universiteti dasturiy injiniring fakulteti algoritmlarni loyihalash
|
| bet | 1/5 | | Sana | 05.04.2023 | | Hajmi | 88.87 Kb. | | #49057 |
Bog'liq 5-amaliy ish 1-labaratoriya, 4-labaratoriya, Dt sifatini ta\'minlash
OʻZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
DASTURIY INJINIRING FAKULTETI
ALGORITMLARNI LOYIHALASH fanidan
5-LABORATORIYA ISHI
Bajardi: Mallayev Og’abek
Tekshirdi: Turg‘unov Abror
TOSHKENT – 2022
Kommivayajer algoritmi(sotuvchi vazifasi)
Transport logistikasining eng mashhur va muhim vazifalaridan biri (va kombinatorni optimallashtirish) – sotuvchi vazifasi yoki "sayohat qiluvchi savdogarning vazifasi" (eng. «Travelling Salesman Problem», TSP). Shuningdek, "Xitoy postmanining vazifasi" nomi ham mavjud. «Chinese Postman Problem», CPP). Vazifaning mohiyati qidirishga tushadi oraliq nuqtalardan bir marta o'tadigan va boshlang'ich nuqtaga qaytadigan maqbul (eng qisqa, eng tezkor yoki eng arzon) yo'l. Misol uchun, eng foydali marshrutni topish imkonini beradi mahsulotingiz bilan muayyan shaharlarni bir marta ziyorat qiling va qaytib keling. Marshrutning rentabellik o'lchovi minimal sayohat vaqti, minimal yo'l xarajatlari yoki minimal yo'l uzunligi bo'lishi mumkin.
Bizning vaqtimizda, etkazib berish narxi ko'pincha mahsulotning o'zi bilan taqqoslanadigan bo'lsa va etkazib berish tezligi asosiy ustuvorliklardan biri bo'lsa, optimal marshrutni topish vazifasi katta ahamiyatga ega.
Tarkib:
sotuvchining vazifasi tarixi;
ta'rif, shartlar va echimlar usullari;
filiallar va chegaralar usuli bilan echim algoritmi;
muammoni hal qilishga misol;
amaliy va nazariy ahamiyati;
onlayn sotuvchi muammosini halqilish.
SOTUVCHINING PAYDO BO'LISHI VA TADQIQOT TARIXI
Muammoni kim va qachon o'rganishni boshlagan sotuvchi vazifalari noma'lum, ammo 1832 da allaqachon sotuvchilar uchun maslahatlar mavjud bo'lgan kitob nashr etildi. Ushbu kitobda tovarlarni bir qator shaharlarga etkazib berish kerak bo'lgan savdogar yoki kuryer uchun eng qisqa yo'lni topish vazifasi tavsiflangan va marshrutlarga misollar keltirilgan. Biroq, muammoni hal qilish uchun matematik apparat berilmagan.
Ushbu muammoning dastlabki versiyasini birinchi bo'lib tuzganlardan biri XIX asrning taniqli irland matematiki, fizigi va mexanigi edi. – Uilyam Rowan Hamilton. Olim icosahedrning (yigirma) simmetriyasini o'rganib chiqdi va 1857da taklif qildi "Icosian" o'yini (ingliz tili. "Icosian Game" ("Icosian Game"), uning maqsadi dodecaedrning barcha uchlarini (o'n ikki burchakli) bir marta va faqat uning qovurg'alari bo'ylab, so'ngra boshlang'ich nuqtaga qaytish edi. Boshqa so'zlar bilan aytganda, deb atalmish topish kerak edi Hamilton aylanishi 20 tugunli ustunda, bu holda muammoning echimi bo'lib, 20 qirralarini o'z ichiga oladi (qadimgi yunoncha" icosa "da" yigirma", shuning uchun o'yin nomi). Matematik tomonidan ixtiro qilingan jumboq Evropada dodecahedr va uning tepalari o'rnida chuqurchalar tasvirlangan taxta shaklida sotilgan.
1930 yilda avstriyalik-amerikalik matematik Karl Menger sotuvchi vazifasini "ma'lum bo'lgan joylar orasidagi eng qisqa yo'lni topish vazifasi"deb ta'rifladi.
Zamonaviy ism "sotuvchi vazifasi o'tish: saytda harakatlanish, qidiruv "Sayohat Salesman muammosi") amerikalik matematik Xassler Uitni tomonidan taklif qilingan.
Sotuvchi vazifasini rivojlantirishda muhim bosqich 1950-1960 yillarda, amerikalik va evropalik olimlar uni tadqiq qilishda ishtirok etishdi. Va bu erda birinchi navbatda matematiklar Jorj Danzig, Delbert Rey Falkerson va Selmer Jonsonni ta'kidlash kerak. Ular 1954 yilda institutda RAND Corporation muammoni diskret optimallashtirish vazifasi sifatida shakllantirish. Olimlar 49 shaharlari bilan sotuvchining shaxsiy muammosini hal qilish uchun kesish usulini (homori algoritmi) qo'lladilar va topilgan marshrutning maqbulligini asosladilar.
Bundan tashqari, 1962 yilda Xitoy matematiki may-ku Kuan ushbu muammoning sharhini "Xitoy postmanining vazifasi"(ingliz tili. «Chinese Postman Problem»). Uning versiyasida pochtachi har bir ko'chada faqat bir marta yoki minimal miqdordagi takrorlashlar bilan o'tadigan shaharning eng qisqa yo'nalishi bo'ylab xatlarni tarqatishi kerak edi.
1960-1970 yillarda sotuvchi vazifasini o'rganish davom ettirildi va 2 yo'nalishda: nazariy va amaliy (uning iqtisodiyot, biologiya, kimyo, informatika sohalarida qo'llash imkoniyatlari o'rganildi).
1972 yilda kompyuter fanlari bo'yicha amerikalik olim Richard Manning karp NP ni isbotladi-Gamilton yo'llarini topish vazifasining to'liqligi, undan keyin NP-sotuvchi vazifasining qiyinligi.
Martin Gretchel, Manfred Padberg, Jovanni Rinaldi va boshqa bir qator olimlar yangi ishlanmalarni (tekislik bilan bo'linish usuli, filiallar va chegaralar usuli) qo'llaganlarida, 2392 shahar bilan sotuvchi vazifasini hal qilishdi.
Sotuvchi muammosini hal qilish bo'yicha yana bir rekord 2006 yil aprel oyida, 85900 shahar bilan variant uchun echim topilganida o'rnatildi. Ammo bu cheklovdan uzoqdir, ba'zi usullardan foydalanib, millionlab shaharlar uchun yechim topish mumkin!
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Muhammad al-xozazmiy nomidagi toshkent axborot texnologiyalari universiteti dasturiy injiniring fakulteti algoritmlarni loyihalash
|
