Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Toshkent axborot texnologiyalari
universiteti Axborot xavfsizligi fakulteti
712-20 guruh talabasi RAMAZONOV
ASADBEKning Diskret tuzilmalari
fanidan bajargan
MUSTAQIL ISHI.
Bajardi: Ramazonov Asadbek.
Tekshirdi:Mamadaliyev Xusniddin.
MAVZU: Kommivoyajer masalasi (Sayohatchi sotuvchi).
Toshkent 2021.
REJA:
1.Kommivoyajer (Sayohatchi sotuvchi) masalasi haqida tushuncha.
2. Sayohatchi sotuvchi muammosining matematik modeli.
3. Sayohatchi sotuvchi muammosi uchun dastlabki ma’lumotlar.
4. Xulosa.
5. Foydalanilgan adabiyotlar.

Sayohatchi sotuvchi muammosining matematik modeli.
Tuzilgan masala butun sonli masala. Yo’l tarmog’i bilan bog’langan n ta shaharni ko’rib chiqing . Bo’lsin x ij = 1 bo’lsa Seyahatsever dan harakat i th shahardan j- th shahar va x ij = 0 bo’lsa, j- th shahar tashrif buyurdi emas. Keling, shartli ravishda ( n + 1 ) –chi shaharni 1-shahar bilan birlashtirgan holda tanishtiramiz , ya’ni. Dan masofalar ( n + 1 ) th boshqa har qanday boshqa shaharu birinchi birinchi shahardan masofaga teng. Bundan tashqari, agar siz faqat birinchi shaharni tark eta olsangiz, unda ( n + 1 ) th shahar faqat kelishi mumkin. Biz yo’lda ushbu shaharga tashriflar soniga teng qo’shimcha tamsayı o’zgaruvchilarni kiritamiz. U 1 = 0 , u n + 1 = n . Yopiq yo’llardan qochish uchun birinchi shaharni tark eting va ( n + 1 ) ga qayting , biz x ij o’zgaruvchilari va u i ( u i manfiy bo’lmagan butun sonlar) o’zgaruvchilarini bog’laydigan qo’shimcha cheklovlarni kiritamiz .
I
-u j + nx ij ≤ n-1, j = 2..n + 1, i = 1..n, i ≠ j, i = 1 j ≠ n + 10≤u i ≤n, x in uchun +1 = x i1 , i = 2...n

Yuqori qo’sh yig’indi – eng kichik qiymat izlanishi kerak bo’lgan vazifaning maqsad funktsiyasi. Quyidagi nisbatlar o’zgaruvchilarga qo’yilgan cheklovlardir. Bir martalik summalar – X qaror rejasining yagona elementlariga har bir satrda ( 1 ≤ i ≤ n) va har bir ustunda ( 1 ≤ j ≤ n ) bitta pozitsiyani egallash talabini ko’rsating.). Ehtimol, o’quvchilar bunday vazifaning nomini allaqachon uchratgan va ehtimol uning tarixi, mazmuni va navlari bilan tanish. Men bu fikrlarni yana bir bor ko’tarib, boshqa mualliflardan keyin takrorlashni xohlamayman, lekin shunga qaramay, maqolaning keyingi versiyasining ko’rinishini qisqacha tushuntirishim kerak. Maqolani yozishdan oldin men o’quv kitoblari va monografiyalar matnlarining versiyalari, Internetda joylashtirilgan nashrlar bilan tanishdim (men ularni tanqid qilmayman, sharhlarda ko’proq narsa qilingan) va shunday qarorga keldim. Men hali ham o’z matnimni yozishim kerak, uni talabalarimga va boshqa o’quvchilarga o’rganish uchun tavsiya qilishim mumkin.

Muammoning umumiy xususiyatlari . Sayohatchi sotuvchi (fr. Commis voyageur ) – sayr qiluvchi savdogarkeng yo’l tarmog’i bilan bog’langanaholi punktlariga ( n )tashrif buyuradi, ular bo’ylab sayohat tarmoqning i-chi, j-chi nuqtalariorasida alohida to’lanadi. Marshrut (sayohat) bo’yicha siz har bir n nuqtagatashrif buyurishingiz kerak(bir marta) va ketgan joydan qaytishingiz kerak. Bu yopiq muammoningformulasi, siz chiqish nuqtasiga qaytishingiz shart emas va muammo ochiq bo’ladi. Simmetrik muammo. Nosimmetrik sayohatchi sotuvchi muammosi (TSP) xarajat ( Sij = Cji ) o’rtasida har ikki yo’nalishda bo’lganda paydo bo’ladi.i-chi, j-chi nuqtalar bir xil. Yo’nalishni tanlash treyder tomonidan minimallashtirilgan xarajatlar bilan belgilanadi. Asimmetrik sayohatchi sotuvchi muammosi (ATSP) C ji ≠ C ij matritsasining assimetriyasini tan oladi . Yana umumiy holatda, ba’zi shaharlar orasidagi yo’llar yo’q bo’lishi mumkin va ular tanlanmasligi uchun ularcheksiz uzunlikdagi S ji = ∞ matritsasiga yozib qo’yilgan). Qisman buyurtma bilan bog’liq muammo (SOP = ketma-ket tartiblash muammosi), ma’lum bir shaharni talab qiladi Men j shahridan oldin tashrif buyurganman (bunday shartlar bir nechta bo’lishi mumkin). Gamilton sikli muammosini izlash (HCP = Gamilton sikli muammosi) har bir cho‘qqidan aynan bir marta o‘tuvchi ixtiyoriy grafikdagi yopiq yo‘llarnianiqlashdan iborat . TSPda (simmetrik sayohat qiluvchi sotuvchi muammosi) yo’l yopiq va siz istalgan shahardan (va istalgan yo’nalishda) boshlashingiz mumkin. Uchun n shaharlar, bor (n – 1) / 2! Xil yo’llar. Faktorial juda tez o’sadi: n! ~ n n optimal yechim izlanadigan makon esa ulkan bo‘lib chiqadi. Masalan, 15 ta shahar uchun 43 milliard marshrut mavjud 18 ta shahar uchun 177 trln. Shuning uchun sayohatchi sotuvchi muammosi turli xil algoritmlarni sinab ko’rish uchun qiziqarli.

1. 
   Aniq usullar nafaqat qandaydir yechim topadi, balki o’z ishining oxirida bu yechim eng yaxshi ekanligini isbotlaydi. Quyidagilarga e’tibor bering: n-1 raqamlarini almashtirishlarning to’liq ro’yxati (boshlang’ich shahar aniqlangan). N> 15 uchun amalda foydasiz . Yo’naltirilgan orqaga yo’naltirish – bu hozirgi momentgacha bo’lgan eng yaxshi yo’ldan kattaroq uzunlikka ega bo’lgan yo’llarni kesib tashlash bilan ba’zi bir yechimga “bo’lgan” variantlarni sanab o’tish. Filial va bog’langan usul – masofaviy matritsani tahlil qilish tufayli “umidsiz” tugunlarni kesishning eng samarali ma’lum usuli. Optimal yechimni izlashda ikkilik daraxt quriladi (har bir tugunda 2 ta filial hosil bo’ladi : sayohatchi sotuvchi ma’lum bir shaharga boradi yoki unga bormaydi).
   
2. 
   Evristik usullar: ochko’z algoritm; Dantel usuli ; Surma qo’pol kuch; 3. Ehtimoliy usullar: Tavlash usuli; Genetik algoritm.
   

Masalaning to‘liq bog‘langan n- vertexga yo‘naltirilgan grafigi ( digrafi) modeli shundayki , har bir ( i, j ) juft cho‘qqilar o‘rtasida har xil sayohat xarajatlari va Sij ≠ C ji (bir tomonlama harakat) bo‘lgan 2 ta yoy mavjud .

Shunday qilib, sayohatchi sotuvchi muammosining yechimi bizning digrafimizda barcha ( n ) cho’qqilardan bir marta eng past narxda o’tadigan marshrutni topishdan iborat . Digraflarda mavjud bo’lgan barcha yo’llar Gamilton sikllari deb ataladi, ular grafikning cho’qqilari to’plamida bir davrli almashtirishlar bilan aniqlanadi va n ta shahar uchun har doim ½ (n – 1) mavjud! Turli yo’llar.