4. Laboratoriya mashg’uloti Mavzu: Kommivoyajer haqidagi masala Ishning maqsadi

Filial va chegara usuli
Littlening algoritmi MVIG ning maxsus holatidir, ya'ni. eng yomon holatda, uning murakkabligi to'liq qidiruvning murakkabligiga teng. Nazariy tavsif quyidagicha:
Rafning barcha Gamilton sikllarining S to'plami mavjud. S ning har bir bosqichida biz chekka (i, j) qidiramiz, uning marshrutdan chiqarilishi pastki bahoni maksimal darajada oshiradi. Keyinchalik, to'plam ikkita ajratilgan S1 va S2 ga bo'linadi. S1 - chekka (i, j) ni o'z ichiga olgan va (j, i) ni o'z ichiga olmaydi. S2 - (i, j) ni o'z ichiga olmagan barcha tsikllar. Keyinchalik, har bir to'plam yo'lining uzunligi uchun pastki chegara hisoblab chiqiladi va agar u allaqachon topilgan yechim uzunligidan oshsa, to'plam o'chiriladi. Agar shunday bo'lmasa, S1 va S2 to'plamlari S bilan bir xil tarzda ishlanadi.
Algoritmik tavsif. Masofa matritsasi mavjud M. diagonali cheksiz qiymatlar bilan to'ldirilgan, chunki erta tsikllar sodir bo'lmasligi kerak. Pastki chegarani saqlaydigan o'zgaruvchi ham mavjud.
Shuni ta'kidlash kerakki, siz ikki turdagi cheksizlikni kuzatib borishingiz kerak - biri matritsadan satr va ustun o'chirilgandan so'ng qo'shiladi, shunda erta davrlar bo'lmaydi, ikkinchisi qirralarning tashlab yuborilganda. Ishlar biroz keyinroq ko'rib chiqiladi. Birinchi cheksizlikni inf1, ikkinchisini inf2 deb belgilaymiz. Diagonal inf1 bilan to'ldirilgan.
1. Har bir satrning har bir elementidan berilgan qatorning minimal elementi ayiriladi. Bunday holda, qatorning minimal elementi pastki chegaraga qo'shiladi
2. Har bir ustundan minimal element xuddi shunday ayiriladi va pastki chegaraga qo'shiladi.
3. M(i, j) ning har bir nol elementi uchun (i, j) elementning o‘zidan tashqari i qator va j ustunning minimal elementlari yig‘indisiga teng koeffitsient hisoblanadi. Bu koeffitsient eritmaning pastki chegarasi (i, j) undan chiqarib tashlansa, uning qanchalik oshishi kafolatlanganligini ko'rsatadi.
4. Maksimal koeffitsientga ega element qidiriladi. Agar ulardan bir nechtasi bo'lsa, istalganini tanlashingiz mumkin (baribir, qolganlari rekursiyaning keyingi bosqichlarida ko'rib chiqiladi)
5. 2 ta matritsa ko'rib chiqiladi - M₁ va M₂. M₁ i qator va j ustuni olib tashlangan M ga teng. Unda inf1 bo'lmagan k ustun va l qator mavjud va M(k, l) element inf1 ga teng. Avval aytib o'tganimizdek, bu erta tsikllarning oldini olish uchun kerak (ya'ni, birinchi bosqichlarda (k, l) == (j, i)). M₁ matritsasi chetini (i, j) o'z ichiga olgan to'plamga mos keladi. Ustun va qatorni olib tashlash bilan birga, chekka (i, j) yo'lga kiritiladi.
6. M₂ M matritsaga teng, uning elementi (i, j) inf2 ga teng. Matritsa chetini (i, j) o'z ichiga olmaydigan yo'llar to'plamiga mos keladi (chet (j, i) chiqarib tashlanmasligini tushunish muhimdir).
7. M₁ va M₂ matritsalari uchun 1-bandga o'ting.
Evristik M₁ matritsaning pastki chegarasi M₂ matritsasinikidan katta emasligi va birinchi navbatda, chekka (i, j) ni o'z ichiga olgan filial hisobga olinadi.
Bir misolni ko'rib chiqing:


Javob yo’li:3=>4=>2=>1=>5=>3 Uzunligi: 41