Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Ta’rif 1 . Gamilton sikli – bu yo’naltirilgan grafikning yo’li bo’lib, uning har bir cho’qqisini bir martadan o’z ichiga oladi, dastlabkisidan tashqari.

Ta’rif 2 . O’rin almashish matritsasi ( 0, 1 ) – matritsa bo’lib , uning pozitsiyasi raqami satrga va tartibli pozitsiyasi ustunga mos keladigan almashtirishga mos keladi. Bunday matritsalar diagonal deb ataladi, ular TSP dizaynlarini amalga oshiradilar.

Ta’rif 3 . Bir davrli almashtirish permutatsiya deb ataladi – bir siklga mos keladigan S n simmetrik guruhining n darajali elementi .

4 ta shahar uchun oddiy misol . Ushbu misoldan foydalanib, biz MVG asoslarini hal qilmasdan ko’rsatamiz va tavsiflaymiz. O’quvchi maqolani o’qib chiqqandan so’ng, o’zi osongina yechim topishi mumkin. Bu misolda IHG ning barcha nazorat qoidalari o’z-o’zini sinab ko’rish uchun javoblarga ega. Birinchidan, biz tarmoq va bog’langan usulning (MBG) barcha elementlari bilan, ishlatiladigan tushunchalar va belgilashlar bilan, lekin MBG tafsilotlarisiz ShKni yechish jarayonining mohiyatini ko’rsatamiz. 1-rasmda ko’rsatilgan: optimal yechim qidirish daraxtining ildizi: R ildizida barcha mumkin bo’lgan echimlar to’plami R = {( 1234 ), ( 1243 ), ( 1432 ), ( 1423 ), ( 1324 ), ( 1342 ) }; ildiz barcha 6 ni o’z ichiga oladiyechimlar – S n nosimmetrik guruhning bir davrli almashtirishlari ; daraxtning boshqa tugunlari X va Y belgilari bilan ko’rsatilgan ; X har doim hozirda qayta ishlangan tugunning nomi sifatida ishlatiladi; bola tugunlari X (tarmoqlanish natijalari) musbat Y va salbiy Y – algoritm tarmoqlanishdan bosh tortadigan tugun (yuqorida yoki pastki qismida chizilgan) (bu bosqichda marshrut yangi filial bilan kengaytirilmaydi va tugun).

Shakl 1. Sayohatchi sotuvchi muammosining optimal yechimi uchun to’liq qidiruv daraxti.

Keling, marshrutlarni oddiy ro’yxatga olishning kichik bir misoli bilan yechim yo’nalishini ko’rsatamiz. Ushbu misol IHMning umumiy printsipi va tushunchalarini ko’rsatish uchun mo’ljallangan. Tafsilotlar quyida to’liq batafsil ko’rib chiqiladi. Shu maqsadda biz 4 ta tugunli yo’l tarmog’i, jadvalning o’ng katakchasi uchun pivot jadvalini hosil qilamiz.

Dastlabki ma’lumotlar va sayohat xarajatlari matritsasining qisqarishi (ij) majmui S {( i, j kamayishiga Matrix hujayralari)} C [4] nol qadriyatlar bilan hosil bo’ladi. Biz marshrutni qurishni boshlaymiz (1-rasm) yuqoridan 1 , shu jumladan filial ( 1-2 ), biz S 12 = ∞ elementiga yuqori narx belgilash orqali salbiy filialni ( 1-2 ) marshrutga kiritishni taqiqlaymiz . Bunday holda, daraxtning ildizidagi yechimlar to’plami birinchi navbatda Y va Y ikkita kichik to’plamga bo’linadi, keyin olingan kichik to’plamlarning har biri kichikroqlarga bo’linadi va eritmalarning kichik to’plamlarini bo’lish jarayoni har bir kichik to’plam bitta yechimni o’z ichiga olguncha davom etishi mumkin. Ammo ko’pincha bu narsaga kelmaydi. Boshqa protseduralar jarayonga xalaqit beradi va jarayonning rivojlanishi boshqa yo’nalishlarda sodir bo’ladi. Ba’zan siz boshlangan marshrutdan uni tugatmasdan voz kechishingiz va ilgari to’xtatilgan va to’xtatilganiga qaytishingiz kerak. Gap shundaki, marshrut qurishda uning sifati nazorat qilinadi. Agar marshrut sifatini ilgari uzilgan marshrutga qaytish orqali yaxshilash mumkin bo’lsa, unda nuqsonli (past sifatli) marshrutni davom ettirishga arzimaydi. E’tibor bering, muammoning echimlari n ta burchak (shahar) ning almashtirishlari bilan modellashtirilgan , ya’ni. S n darajali algebraik simmetrik guruhning elementlarin . Barcha almashtirishlar ruxsat etilgan echimlar emas va, albatta, ruxsat etilganlarning hammasi ham maqbul bo’lmaydi. Nosimmetrik almashtirish guruhida konjugat elementlarning ajratilgan sinflariga bo’linish amalga oshiriladi. Bunday sinflardan biri mumkin bo’lgan echimlar to’plamidan iborat – bu bir davrli almashtirishlar sinfidir, ya’ni. Barcha elementlarni o’z ichiga olgan tsiklni tashkil etuvchi almashtirishlar