Ramazonov asadbekning Diskret tuzilmalari fanidan bajargan mustaqil ishi

Jadval A – TSP ning (n = 4) yechimlari to’plamini ularning xarakteristikalari bilan ko’rsatish.

T
SP ning yechimlar to’plamini tahlil qilish. A jadvaliga barcha n!=4! = 24 ta mumkin bo’lgan almashtirish – muammoning echimlari (Rejalar X ), ular leksikografik soni bo’yicha tartiblangan. Har bir almashtirish uchun loop kiritilgan (3-ustun). Masalan, 8- qatordagi almashtirish ( 12 ) ( 34 ) 1 → 2 va 1 ← 2 yoy juftlariga mos keladi ; 3 → 4 va 3 ← 4 , ular marshrutni amalga oshirmaydi (bitta tsikl). Va 10- qatordagi almashtirish ( 1234 ) 1 → 2 → 3 → 4 → 1 zanjiriga mos keladi., ya’ni. Yopiq tsikl paydo bo’ldi, unda yo’l grafigining barcha uchlari kiritilgan, lekin faqat bir marta. Matritsaning elementlari ushbu tsiklning yoylarini tanlashga mos keladi: C 12 = 5, C 23 = 6, C 34 = 11, C 41 = 8 . Ularning yig’indisi CF marshrutining CF qiymati = 5 + 6 + 11 + 8 = 30 . Of n! = 4! = Yo’l grafigi cho’qqilari raqamlarining 24 almashinuvi tsiklik (bir davrli) faqat oltita ( n-1)! = (4-1)! = 3! = 6 (ularning soni 10,11.14, 18,19,23). Tarmoqdagi marshrutlar (turlar) – modelning cheklovlari bilan ruxsat etilgan echimlar jadvalda ko’rsatilgan (3-ustun qalin harf bilan). Ular orasida siz o’zingiz yoqtirgan turni tanlashingiz mumkin. 6 ta marshrutning har biri uchun maqsad funksiyasining qiymati hisoblab chiqilgan (CF ning 4-ustun: 30,31,55,45,46,45 ) . Bu qadriyatlar kichik bo’ladi 30 . Garchi u 29 ga teng CF ning pastki chegarasidan oshib ketgan bo’lsa-da . Aynan shu yechim, pasaytirilgan xarajat matritsasiga asoslangan qarorlar daraxtiga muvofiq, optimal T opt = (12) (23) (34) (41) bilan. CF = 30.

Biz xarajatlar matritsasini qisqartirishni amalga oshiramiz. Har bir satrning qisqarish koeffitsientlarini topamiz h i (biz ularni matritsaning o’ng tomonidagi qatorlarga yozamiz) va shundan so’ng har bir ustun h j, so’ngra barcha h ni jamlab , butun matritsaning qisqarish konstantalarini olamiz.

Bundan tashqari, optimal yechimni izlashda C [ n ] arzonlashtirilgan xarajat matritsasi qo’llaniladi. Quyma konstantalarining H yig’indisi ZK ning barcha yechimlariga mos keladigan umumiy qismdir; ya’ni shu asosda h i konstantalarni ayirish , matritsaning barcha chiziqlarini keltirish va so’ngra konstantalarni bir-biri bilan yig’ish yo’li bilan olinadi. Bundan kelib chiqadiki, hech qanday turda (ruxsat etilgan yechim) bu qiymatni kamaytirish mumkin emas. Hatto T opt NGCP = 29 dan oshadi , garchi faqat bitta.

Albatta, bir taqqoslash H deb ro’yxat usuli namoyishlari bilan olingan barcha tur uchun CF jadval smeta bilan H bo’ladi kamroq ularning hammasi dan. Shu sababli H maqsad funksiyaning pastki chegarasi (LHCF) deb ataladi, masalaning butun yechimlari to’plami uchun CF bahosi, ya’ni daraxtning ildiz tugunlari uchun.