KOMMIVOYAJER MASALASI. TARMOQLAR VA CHEGARALAR USULI

Аннотация

Kommivoyajer masalasi – kombinatorika va optimallash sohalarida uchraydigan eng mashhur va murakkab masalalardan biridir. Ushbu masalada sayohatchi (kommivoyajer) shaharlar bo‘ylab safar qilishi va har bir shaharga faqat bir marta tashrif buyurib, yakunda boshlang‘ich nuqtaga qaytishi talab qilinadi. Maqsad – umumiy safar masofasini yoki xarajatni minimal qilish. Tarmoqlar va chegaralar usuli bu masalani yechish uchun samarali algoritmik metodlardan biri hisoblanadi. Ushbu maqolada kommivoyajer masalasining mohiyati, matematik modeli, tarmoqlar va chegaralar usulining ishlash mexanizmi va uning samaradorligi haqida batafsil ma'lumot beriladi. Kalit so‘zlar: Kommivoyajer masalasi, tarmoqlar va chegaralar usuli, kombinatorik optimallash, branch and bound, NP-murakkab masalalar, safar marshruti, optimallash, matematik modellashtirish, graf nazariyasi, minimal masofa, qaror daraxti, pastki va yuqori chegaralar, eksplisit qidiruv, heuristik algoritmlar, shaharlar oralig‘i. Kommivoyajer masalasi (TSP – Traveling Salesman Problem) ilmiy va amaliy jihatdan katta ahamiyatga ega bo‘lib, uni transport logistika, chip dizayni, robot harakatlanishi va hatto genetik tahlil sohalarida uchratish mumkin. TSP – NP-murakkab masala bo‘lib, kichik o‘lchamdagi holatlar uchun aniq yechim topish mumkin bo‘lsa-da, shaharlari soni oshgani sari hisoblash murakkabligi eksponensial ravishda o‘sadi. Jarayonlar tadqiqoti, operatsiyalarni tadqiq qilish va kombinatorik optimallashda kommivoyajer masalasi markaziy o‘rinni egallaydi. Masalaning klassik shakli shunday ifodalanadi: Berilgan shaharlar to‘plami va ularning orasidagi masofalar ma’lum. Har bir shaharni faqat bir marta ziyorat qilib, boshlang‘ich shaharga qaytgan holda eng qisqa marshrutni aniqlang. Adabiyotlar tahlili: Kommivoyajer masalasi ustida yuzlab olimlar tadqiqotlar olib borgan: 14 CURRENT APPROACHES AND NEW RESEARCH IN MODERN SCIENCES International scientific-online conference G. Dantzig, R. Fulkerson va S. Johnson (1954) - TSP uchun liniyali dasturlash modelini taklif qilgan. R. Bellman (1956) – Dinamik dasturlash asosida TSP yechimining ko‘p bosqichli strukturasi haqida tadqiqot qilgan. M. Held va R. Karp (1962) – TSP uchun dinamika va tarmoqlar va chegaralar usullarini rivojlantirgan. Lawler, Lenstra, Rinnooy Kan va Shmoys (1985) - NP-murakkab masalalar to‘plamida TSPning o‘rni haqida keng qamrovli sharh berganlar. Adabiyotlar ko‘rsatadiki, TSPni aniq yechish uchun ko‘plab turli metodlar ishlab chiqilgan, biroq ular orasida tarmoqlar va chegaralar (Branch and Bound) usuli samaradorligi bilan ajralib turadi. Tadqiqot metodologiyasi: Ushbu maqolada kommivoyajer masalasini yechish uchun tarmoqlar va chegaralar usuli asosida quyidagi metodlar qo‘llanildi: 1. Matematik modellashtirish: Masalaning mohiyatini ifodalovchi matematik model tuzildi. Bu modelda har bir shaharni faqat bir marta ziyorat qilish, yakunda boshlang‘ich shaharga qaytish va umumiy masofani minimallashtirish kabi asosiy shartlar ifodalandi. 2. Grafik struktura asosida tahlil: Shaharlar o‘zaro bog‘langan tugunlar (graf teoremasi asosida) shaklida qaralib, ularning orasidagi masofalar yo‘l og‘irliklari sifatida belgilandi. Bu tahlil orqali vizual va strukturaviy ko‘rinish yaratilib, yechim algoritmini qulaylashtiruvchi asos shakllantirildi. 3. Tarmoqlash (Branching): Qidiruv daraxti hosil qilish maqsadida qaror nuqtalarida (ya'ni, har bir bosqichda tanlov mavjud bo‘lgan holatlarda) ehtimoliy yo‘nalishlar bo‘yicha tarmoqlanish amalga oshirildi. Har bir tarmoqda yangi pastki matritsalar hosil qilinib, yo‘l tanlovi asosida tahlil davom ettirildi. 4. Chegaralash (Bounding): Har bir tarmoq uchun minimal xarajatni baholovchi quyi chegara (lower bound) hisoblab chiqildi. Buning uchun satr va ustun minimumlarini ayirish usuli (matritsa kamaytirish) qo‘llanildi. Bu orqali qisman yo‘llar asosida butun yo‘l uchun eng kam mumkin bo‘lgan masofa aniqlanib, resurslar tejab qolindi. Misol: KOMMIVOYAJER MASALASI: TARMOQLAR VA CHEGARALAR USULI Boshlang'ich masofalar jadvali A B C D 15 CURRENT APPROACHES AND NEW RESEARCH IN MODERN SCIENCES International scientific-online conference A ∞ 20 42 35 B 20 ∞ 30 34 C 42 30 ∞ 12 D 35 34 12 ∞ 1-qadam: Satrdan minimumlarni ayirish (Row reduction) Satrlar bo‘yicha eng kichik qiymatlarni topamiz: A qatori minimum: 20 B qatori minimum: 20 C qatori minimum: 12 D qatori minimum: 12 Yangi jadval A B C D A ∞ 0 2 1 2 5 B 0 ∞ 1 1 0 4 C 3 1 ∞ 0 0 8 D 2 2 0 ∞ 3 2 2-qadam: Ustundan minimumlarni ayirish (Column reduction) Ustunlar bo‘yicha eng kichik qiymatlarni topamiz: A ustun minimum: 0 B ustun minimum: 0 C ustun minimum: 0 D ustun minimum: 0 Demak, ustunlardan hech narsa ayirmaymiz. Hisob-kitoblar: Satrdan ayirganlar yig‘indisi: 20 + 20 + 12 + 12 = 64 Ustundan ayirganlar yig‘indisi: 0 Umumiy quyi chegara (lower bound): 64 + 0 = 64 Tarmoqlanish (Branching) — Birinchi tarmoq: A → B A shahridan B ga ketishni tanlaymiz. Qoidalar: A qator va B ustun o‘chiriladi. B → A yo‘li taqiqlanadi (∞ qilinadi). Y