Tarmoq va chegaralar usuli
Download 69.25 Kb.
|
Nilufar, komivoyajer masalasi
- Bu sahifa navigatsiya:
- Foydalangan adabyotlar
R E J A: Kommivoyajer haqida. Kommivoyajer masalasi. Tarmoq va chegaralar usuli. Kommivoyajer haqidagi masala Xar bir shaxarni grafning chuqqisi. shaxarlar orasidagi yo’lni qirralar, ular orasidagi sayoxat baxosini shu qirraning og’irligi deb tasavvur qilishi mumkin. Bundan shunday xulosa chiqarish mumkinki, qisqa yo’lni qidirish algoritmi kommivoyajer masalasini hal qiladi, biroq bu unday emas. Kommivoyajer xakidagi masalaning kanday ikki shargi uni kiska yul xakidagi masaladan farklaydi? Birinchidan biz xamma shaxarlarga tashrif buyurishimiz kerak. kiska yulni izlash algoritmi esa berilgan ikki shaxarlar orasidagi yulni beradi. Аgar kiska yulni ganlash algoritmi bergan kiska bulakli yulni yigsak, bu yul baʼzi shaxarlardan bir necha marta utadi. Ikkinchi fark kiska yulni izlashda dastlabki nuktaga kaytishni talab kilishdan iborat. Bu masala NP sinfiga tegishli ekanligini kursagish uchun uni yukorida yoritilgan ikki kadamli amal yordamida kanday yechish mumkinligini tushunish zarur. Kommivoyajer xakidagi masalaning birichi kadamida shaxarlarning baʼzi tartiblashtirilishi asosiy uringa chikadi. Bu determinallash magan jarayon bulganligi uchun xar safar yangi tartib iaydo buladi. Generatsiya jarayonini polinomial vaktda amalga oshirish mumkin: biz shaxarlar ruyxatini saklashimiz mumkin, tasodifiy rakamni asosiylashtirishimiz, shu nomdagi shaxarni ruyxatdan tanlashimiz va u Yana iaydo bulmasligi uchun ruyxatdan chikarishimiz mumkin. Bunday jarayon O(N) ichida amalga oshiriladi, bu yerda N - shaxarlar soni. Ikkinchi kadamda berilgan gargibdagi shaxarlar buyicha sayoxatlar baxosini xisoblash amalga oshiriladi. Buning uchun biz ruyxatdagi shaxarlarning ketma-ket juftlari orasidagi sayoxat baxosini jamlashimiz kerak, buning uchun xam O(N) jarayoni talab kilinadi. Ikala kadam xam polinomial, chunki kommivoyajer masalasi NP sinfiga tegishli. Prezidentimiz olib borayotgan ijtimoiy–iqtisodiy siyosatda mamlakat hayotining barcha jabhalarini rivojlantirishga, ayniqsa, yosh avlodni milliy tiklanish mafkurasi ruhida tarbiyalashga juda katta eʼtibor berilmoqda. Hozirgi kunda taʼlim olayotgan yoshlar Respublikamizning kelajagidir. Shu sababli yuksak malakali oʼqituvchilar tayyorlash va ularning malakasini oshirish masalalariga katta eʼtibor berilmoqda. Kommivoyajer masalasi. Kommivoyajer-daydi sotuvchi maʼnosini bildirib, masalaning qoʼyilishi juda ham soddadir. Yaʼni kommivoyajer h ta shaharning har biriga faqat bir martadan tashrif buyurib, barcha shaharlarni shunday aylanib chiqishi kerakki, natijada umumiy ketadigan xarajat (chiqim, sarf) minimal boʼlsin. Аgar, biz shaharlarni bir marta aylanib chiqishni marshrut deb atasak, aniqki, bunday marshrutlar soni koʼpi bilan (h-1)!ta boʼladi. Tarmoqlar va chegaralar usuli. Biz tarmoqlar va chegaralar usulini kommivoyajer masalasini yechish uchun qoʼllanishini koʼramiz. Faraz etaylik cij sonlari i-shahardan j-shaharga oʼtish uchun ketadigan xarajatni bildirsin. Аgar i shahardan j shaharga oʼtishning iloji boʼlmasa, cij ni yetarlicha katta son deb olamiz (buni cij =∞ deb belgilaymiz), i-shahardan yana i-shaharga oʼtildi, deyish maʼnosiz boʼlganligi sababli cij =∞ deb olinadi. Shundan soʼng nxn oʼlchamli (cij) jadval (matritsa) hosil boʼladi, u xarajat jadvali deb ataladi. Yana bir bor taʼkidlab oʼtamizki, jadvalning i satri j ustuni kesishgan joydagi cijelement i-shahardan j-shaharga oʼtish uchun ketgan sarf-xarajatni bildiradi. Endi jadvalni keltirish tushunchasini kiritamiz. Buning uchun, avval jadval satrlari keltiriladi, yaʼni jadvalning har bir satr elementlaridan shu satrning kichigi mos ravishda ayirib tashlanadi. Barcha satrlari va ustunlari keltirilgan jadval keltirilgan deb ataladi. Demak, keltirilgan jadvalning har bir satri va ustunida kamida bitta nol element ishtirok etgan boʼladi. Jadval satr va ustunlari eng kichik elementlarining yigʼindisi h bilan belgilanib, u jadvalning keltirish koeffitsienti deyiladi Misol sifatida quyidagi harajat jadvalini koʼraylik Jadval satrlarini keltirish uchun, uning oʼng tarafiga mos satrning eng kichik elementini yozib chiqamiz va satr elementlaridan uni ayirib quyidagi jadvalga ega boʼlamiz. Hosil boʼlgan C* jadvalning ustunlarini keltirish maqsadida jadval ostiga mos ustunning eng kichik elementi yoziladi va u ustun elementlaridan ayirib chiqiladi, natijada quyidagi jadval hosil boʼladi. C** jadval keltirilgan boʼlib, uning har bir satr va ustunida kamida bittadan nol element bor. Koʼrilayotgan jadvalning keltirish koeffitsienti h quyidagi songa teng h=3+1+2+1+4+4+0+3+0+0+0+0=18. Keltirish koeffitsienti h eng kam xarajatli oʼtishlarning umumiy harajatini bildirib, bu xarajatni beruvchi marshrutni xar vaqt ham aniqlab boʼlmaydi. Yuqorida koʼrilgan misolda eng kam harajatli (h=18) marshrutni aniqlasak, u ikkita bir biriga bogʼlanmagan oʼtishlardan (tsikllardan) iborat boʼlib qoladi, yaʼni 1→5→3→2→1 va 4→6→4. Bu esa qoʼyilgan masalaning yechimini bermaydi. Demak, jadvalni keltirish bilan har vaqt ham qoʼyilgan masalaning yechimini olib boʼlmas ekan. Umuman, tarmoqlar va chegaralar usuli ikkita muhim bosqichdan iboratdir. 1) tarmoqlash; 2) chegaralarni aniqlash. Bu graf oʼzaro birlashtirilgan doirachalardan iborat boʼlib, ularning har biri maʼlum bir xossali marshrutlar toʼplamini aniqlaydi. Yuqorida koʼrgan misolda h=18 edi, demak, xarajati 18 dan kichik boʼlgan marshrut yoʼq ekan. Barcha marshrutlar toʼplamini tarmoqlash uchun keltirilgan S** jadvalning nol elementlari darajalari aniqlanadi. Masalan, c15**=0 ning darajasini topish uchun, birinchi satrdagi eng kichik element-1ga, beshinchi ustundagi eng kichik element-1 qoʼshiladi va hosil boʼlgan 2 soni shu nolning darajasi sifatida yozib qoʼyiladi. Xuddi shunday c32**=0 ning darajasini topish uchun uchinchi satrdagi eng kichik-0 ga ikkinchi ustundagi eng kichik element-4 qoʼshiladi va hosil boʼlgan 4 soni c32**ning darajasi sifatida yozib qoʼyiladi. Darajasi eng katta boʼlgan nol element s53**=0 dir, demak, tarmoqlanish grafi koʼrinishda boʼladi. Jadvalning oʼlchami bittaga kamayadi. Bunda, shuni alohida taʼkidlash lozimki, shaharlarning tartib raqamlari albatta saqlanib (yozilib) qolishi shart, aks holda chalkashliklar kelib chiqadi. Shundan soʼng, toʼla boʼlmagan marshrut i→j, j→i (i→j) belgi i-shahardan j-shaharga oʼtishni bildiradi) yoʼqotiladi, buning uchun Cij**element belgisiga almashtirilib yozib qoʼyiladi. Bizning misolda bu jadval quyidagi koʼrinishga ega boʼladi. Shundan soʼng, hosil boʼlgan yangi jadval keltirilib, uning keltirish koeffitsienti, oldingi keltirish, koeffitsienti boʼlgan h ga qoʼshib yoziladi (h2*). Oxirgi jadvaldan koʼrinib turibdiki, u keltirilgan jadval ekan, demak, uning keltirish koeffitsienti nolga teng. Bunda belgini olgan chap doirachaga mos chegara (h4), h1ga nolning eng katta darajasi qoʼshib aniqlanadi.() belgili oʼng doirachaga mos kelgan chegarani (h*3) topish uchun oxirgi jadvaldan k-satr va l-ustun chiqarib (oʼchirib tashlanadi) va toʼla boʼlmagan marshrutlar ∞ belgisi yordamida taqiqlanadi. Shundan soʼng, hosil boʼlgan jadvalning keltirish koeffitsienti h ga h*1 qoʼshilib oʼng doiracha yoniga yozib qoʼyiladi. K,l juftlik sifatida 3→2ni, yoki 6→4ni olish mumkin. Masalan, 3→2ni olaylik. U holda quyidagi grafga ega boʼlamiz. (2,1) belgili doirachada 5→3→2→1 oʼtishlarni oʼz ichiga olgan marshrutlar toʼplami boʼlib, toʼla boʼlmagan 5→3→2→1→5 marshrutni yoʼqotish maqsadida birinchi satr, beshinchi ustun kesishgan elementni ∞ belgiga almashtiramiz va ikkinchi satr birinchi ustunni oʼchirib tashlaymiz, natijada, quyidagi jadval hosil boʼladi Xulosa qilib shuni aytishimiz kerakki, iqtisodi masalalarni yechishda, yaʼni eng kam xarajatni topib olish ham mumkin. Sayohatchi sotuvchi muammosi (yoki sayohatchi sotuvchi muammosidan TSP ) eng mashhur kombinatoriy optimallashtirish muammolaridan biri bo'lib , u belgilangan shaharlardan kamida bir marta o'tib, keyin asl shaharga qaytish uchun eng foydali marshrutni topishdan iborat. Muammoning sharoitida marshrutning rentabellik mezoni (eng qisqa, eng arzon, yig'indisi mezon va boshqalar) va masofalar, xarajatlar va shunga o'xshashlarning tegishli matritsalari ko'rsatilgan. Qoidaga ko'ra, marshrut har bir shahar orqali faqat bir marta o'tishi kerakligi ko'rsatilgan - bu holda tanlov Gamilton tsikllari orasida amalga oshiriladi. Muammoni umumiy shakllantirishning bir nechta maxsus holatlari mavjud, xususan, geometrik sayohatchi sotuvchi muammosi (shuningdek, tekislik yoki Evklid deb ataladi, masofa matritsasi samolyotdagi nuqtalar orasidagi masofani aks ettirganda), metrik sayohatchi sotuvchi muammosi uchburchak tengsizligi xarajat matritsasi bo'yicha qondiriladi ), simmetrik va assimetrik sayohatchi sotuvchi muammolari. Shuningdek, muammoning umumlashtirilishi, ya'ni umumiy sayohatchi sotuvchi muammosi deb ataladi . Optimallashtirish muammosi bayoni NP-qiyin muammolar sinfiga kiradi, ammo ko'pgina alohida holatlar kabi. “Qaror muammosi” versiyasi (ya’ni, berilgan k qiymatidan ortiq bo‘lmagan marshrut bor-yo‘qligini so‘raydi ) NP-to‘liq muammolar sinfiga kiradi. Sayohatchi sotuvchi muammosi transkompüter muammolaridan biridir: hatto nisbatan kam sonli shaharlar (> 66) bo'lsa ham, uni bir necha milliard yildan kamroq vaqt ichida nazariy jihatdan taxmin qilinadigan har qanday kompyuterlar tomonidan variantlarni sanab o'tish usuli bilan hal qilib bo'lmaydi. Sayohatchi sotuvchi muammosi bilan bog'liq Gamilton siklini topish muammosi. Bunday muammoning misoli, hech bo'lmaganda 18-asrdan beri ma'lum bo'lgan ritsarning harakati muammosi [1] . Leonhard Eyler unga 1759 yildagi "Hech qanday tadqiqotga to'g'ri kelmaydigan qiziq savolning yechimi" nomli katta asarini bag'ishlagan [2] . Gamilton siklini topish muammosining yana bir misoli ikosian : matematik jumboq bo'lib, unda siz har bir cho'qqiga bir marta tashrif buyuradigan dodekadr (20 ta tugunli grafik) orqali o'tishingiz kerak. Ushbu muammoni 19-asrda Uilyam Gamilton taklif qilgan , u ham shunday yo'llar sinfini aniqlagan. 1832 yilda “Sayohatchi sotuvchi – mol yetkazib berish va ishlarida muvaffaqiyat qozonish uchun o‘zini qanday tutishi va nima qilishi kerak – eski kurerdan maslahat” (nem. Der Handlungsreisende – wie er sein) nomli kitob nashr etildi. soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur ), bu muammoni tavsiflaydi, lekin uni hal qilish uchun matematik apparatdan foydalanmaydi. Ammo u Germaniya va Shveytsariyaning ba'zi hududlari uchun marshrutlarning namunalarini taqdim etadi. Matematik optimallashtirish muammosi sifatida birinchi eslatmalar Karl Mengerga tegishli bo'lib , u 1930 yilda matematik kollokviumda uni quyidagicha shakllantirgan: Biz messenjer muammosini (chunki bu savol har bir pochtachi uchun tug'iladi, xususan, ko'plab sayohatchilar buni hal qilishadi) cheklangan joylar to'plami orasidagi masofa ma'lum bo'lgan eng qisqa yo'lni topish muammosi deb ataymiz. Ko'p o'tmay, Prinston universitetidan Xassler tomonidan taklif qilingan sayohatchi sotuvchi muammosining mashhur nomi paydo bo'ldi. Ta'rifning qulayligi va yaxshi echimlarni topishning nisbiy qulayligi bilan bir qatorda, sayohatchi sotuvchi muammosi haqiqatan ham maqbul yo'lni topish juda qiyin vazifa bo'lganligi bilan ajralib turadi. Ushbu xususiyatlarni hisobga olgan holda, 20-asrning ikkinchi yarmidan boshlab, sayohatchi sotuvchi muammosini o'rganish yangi optimallashtirish algoritmlarini ishlab chiqish modeli sifatida nazariy jihatdan amaliy ma'noga ega emas. Bugungi kunda keng tarqalgan diskret optimallashtirish usullarining ko'pchiligi, masalan, kesish, tarmoq va bog'langan va evristik algoritmlarning turli xil variantlari misol sifatida sayohatchi sotuvchi muammosidan foydalangan holda ishlab chiqilgan. 1950—1960 - yillarda sayohatchi sotuvchi muammosi AQSh va Yevropa olimlarining eʼtiborini tortdi. Muammoni o'rganishga muhim hissa Jorj Danzig, Delbert Rey Fulkerson ( ing. Delbert Rey Fulkerson ) va Selmer Jonson ( ing. Selmer M. Jonson ) tegishli bo'lib, ular 1954 yilda RAND korporatsiyasi institutida muammoni shaklda shakllantirganlar. Diskret optimallashtirish muammosi va uni hal qilishning kesish usuli. Ushbu usuldan foydalanib, ular 49 ta shaharda bitta muammoli bayonot uchun sayohatchi sotuvchi yo'lini qurdilar va uning optimalligini asosladilar. 1960—1970-yillarda muammo koʻpgina olimlar tomonidan ham nazariy, ham uni informatika, iqtisodiyot, kimyo va biologiyada qoʻllash nuqtai nazaridan oʻrganildi. 1972 yilda Richard Karp Gamilton yo'llarini topish muammosining NP-to'liqligini isbotladi , bu polinomning qaytarilishi tufayli sayohatchi sotuvchi muammosining NP-qattiqligini nazarda tutadi. Ana shu xossalariga tayanib, u amaliyotda muammoning yechimini topishning murakkabligini nazariy asoslab berdi. 1970-yillarning oxiri va 1980-yillarda Martin Grötschel ( Nemis Martin Grötschel ), Manfred Padberg ( Germaniya Manfred Padberg ) va Jovanni Rinaldi ( Italiya Giovanni Rinaldi ) va boshqalar yangi bo'linish usullaridan foydalangan holda tekislik, filiallar va chegaralarni hisoblashda katta muvaffaqiyatlarga erishildi. 2393 ta shahar bilan bog'liq muammoning alohida holati uchun. 1990- yillarda Devid Applegeyt, Robert Biksbi, Vashek Chvatal va Uilyam Kuk Concorde dasturi bo'yicha record o'rnatdilar. Gerxard Reinelt ( nemis Gerxard Reinelt) TSPLIB ni yaratdi - tadqiqotchilarning turli guruhlari ishi natijalarini solishtirish uchun turli darajadagi murakkablikdagi sayohatchi sotuvchi muammosining standartlashtirilgan misollari to'plami. 2005 yil mart oyida 33 810 tugun bilan bog'liq muammo Concord dasturi tomonidan hal qilindi : 66 048 945 uzunlikdagi yo'l hisoblab chiqilgan va qisqaroq yo'llar yo'qligi isbotlangan. Aprelda 2006 yilda 85 900 tugunli misol uchun yechim topildi. Parchalanish usullaridan foydalanib , uzunligi optimaldan 1% dan kam bo'lgan millionlab tugunlar bilan bog'liq muammolarning echimlarini hisoblash mumkin Foydalangan adabyotlar: Levitin A. V. 3-bob. Qo'pol kuch usuli: sayohatchi sotuvchi muammosi // Algoritmlar. Rivojlanish va tahlilga kirish - M . : Uilyams , 2006. - S. 159-160. - 576 b. — ISBN 978-5-8459-0987-9. Tomas X. Kormen, Charlz I. Leyserson, Ronald L. Rivest, Klifford Shtayn. Algoritmlar: qurilish va tahlil = Algoritmlarga kirish. - 2-nashr. - M .: "Uilyams" , 2006. - S. 1296. - ISBN 0-07-013151-1. IN VA. Dono. Sayohatchi sotuvchi muammosi . - M . : "Bilim" , 1969. - S. 62. Download 69.25 Kb. Do'stlaringiz bilan baham: 
|