DSA kommivoyajyor masalasi

Kommivoyajyor masalasi

Kommivoyajyor masalasining shartiga ko‘ra, siz savdo vakilisiz va bir qancha shahar yoki qishloqlarga borib chiqishingiz kerak.

Held-Karp algoritmidan tashqari (u ancha murakkab va ko‘p vaqt talab qiladi, (\(O(2^n n^2)\)), shuning uchun bu yerda tavsiflanmaydi), eng qisqa marshrutni topishning barcha mumkin bo‘lgan marshrutlarni tekshirishdan boshqa yo‘li yo‘q.

Bu masalani yechishning vaqt murakkabligi \(O(n!)\) ekanini anglatadi, ya’ni 6 ta shahar uchun 720 ta marshrutni, 8 ta shahar uchun 40 320 ta marshrutni tekshirish kerak, agar 10 ta shaharga borishingiz kerak bo‘lsa, 3,6 milliondan ortiq marshrutni tekshirishga to‘g‘ri keladi!

Kommivoyajyor masalasi (TSP) o‘rganish uchun qiziqarli masala, chunki u juda amaliy, ammo uni yechish shu qadar ko‘p vaqt talab qiladiki, hatto atigi 20-30 ta cho‘qqili grafda ham eng qisqa marshrutni topish deyarli imkonsiz bo‘lib qoladi.

Agar kommivoyajyor masalasini yechish uchun samarali algoritmimiz bo‘lganida, bu ko‘plab sohalarda, masalan, chip dizayni, transport marshrutlarini rejalashtirish, telekommunikatsiya va shaharsozlikda juda katta o‘zgarishlarga olib kelgan bo‘lardi.

Kommivoyajyor masalasini barcha marshrutlarni tekshirish orqali yechish

Kommivoyajyor masalasining optimal yechimini topish uchun barcha mumkin bo‘lgan marshrutlarni tekshiramiz va har safar qisqaroq marshrut topganimizda uni saqlab qo‘yamiz, shunda oxirida eng qisqa marshrutga ega bo‘lamiz.

Afzalligi: Umumiy eng qisqa marshrutni topadi.

Kamchiligi: Juda ko‘p hisob-kitob talab qiladi, ayniqsa shaharlar soni ko‘p bo‘lganda, ya’ni juda ko‘p vaqt oladi.

Masalaga yechim topishning bunday usuli brute force (to‘liq tanlash) deb ataladi.

Brute force aslida algoritm emas, u shunchaki barcha imkoniyatlarni tekshirish orqali yechim topishni anglatadi — odatda buni qilishning yaxshiroq usuli yo‘qligi sababli.

Eng qisqa marshrutni topishning brute force usuli (yuqorida ko‘rsatilganidek) shunchalik ko‘p vaqt talab qilishining sababi shundaki, biz barcha marshrutlarni tekshiramiz, shaharlar soni ortganda esa mumkin bo‘lgan marshrutlar soni juda tez ortadi.

from itertools import permutations

def calculate_distance(route, distances):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distances[route[i]][route[i + 1]]
    total_distance += distances[route[-1]][route[0]]
    return total_distance

def brute_force_tsp(distances):
    n = len(distances)
    cities = list(range(1, n))
    shortest_route = None
    min_distance = float('inf')
    
    for perm in permutations(cities):
        current_route = [0] + list(perm)
        current_distance = calculate_distance(current_route, distances)
        
        if current_distance < min_distance:
            min_distance = current_distance
            shortest_route = current_route
    
    shortest_route.append(0)
    return shortest_route, min_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = brute_force_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

Kommivoyajyor masalasini ochko‘z algoritm yordamida yechish

Kommivoyajyor masalasini yechish uchun har bir mumkin bo‘lgan marshrutni tekshirish (yuqorida qilganimizdek) aql bovar qilmaydigan darajada ko‘p vaqt talab qilgani sababli, buning o‘rniga har bir qadamda eng yaqin, hali borilmagan shaharga borish orqali qisqa marshrut topishimiz mumkin — bu ancha tezroq.

Afzalligi: Kommivoyajyor masalasining yechimini barcha marshrutlarni tekshirishga qaraganda ancha tezroq topadi.

Kamchiligi: Umumiy eng qisqa marshrutni topmaydi, shunchaki o‘rtacha tasodifiy marshrutdan ancha qisqa bo‘lgan marshrutni topadi.

Kommivoyajyor masalasida har bir qadamda shunchaki eng yaqin, hali borilmagan shaharga borish orqali eng qisqa marshrutning taqribiy yechimini topishning bu usuli ochko‘z (greedy) algoritm deb ataladi.

Ushbu simulyatsiyani bir necha marta ishga tushirib ko‘rganingizdek, topilgan marshrutlar mutlaqo bema’ni emas. Ba’zan, ayniqsa algoritm oxiriga yaqin, chiziqlar kesishib qoladigan hollarni hisobga olmaganda, natijaviy marshrut keyingi shaharni tasodifiy tanlaganimizda hosil bo‘ladiganidan ancha qisqa bo‘ladi.

def nearest_neighbor_tsp(distances):
    n = len(distances)
    visited = [False] * n
    route = [0]
    visited[0] = True
    total_distance = 0

    for _ in range(1, n):
        last = route[-1]
        nearest = None
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and distances[last][i] < min_dist:
                min_dist = distances[last][i]
                nearest = i
        route.append(nearest)
        visited[nearest] = True
        total_distance += min_dist

    total_distance += distances[route[-1]][0]
    route.append(0)
    return route, total_distance

distances = [
    [0, 2, 2, 5, 9, 3],
    [2, 0, 4, 6, 7, 8],
    [2, 4, 0, 8, 6, 3],
    [5, 6, 8, 0, 4, 9],
    [9, 7, 6, 4, 0, 10],
    [3, 8, 3, 9, 10, 0]
]

route, total_distance = nearest_neighbor_tsp(distances)
print("Route:", route)
print("Total distance:", total_distance)

Kommivoyajyor masalasining optimalga yaqin yechimlarini topadigan boshqa algoritmlar

Kommivoyajyor masalasini yechish uchun ochko‘z algoritmdan foydalanishdan tashqari, eng qisqa marshrutning taqribiy yechimlarini topa oladigan boshqa algoritmlar ham mavjud.

Bu algoritmlar mashhur, chunki ular barcha mumkin bo‘lgan yechimlarni haqiqatan tekshirishdan ancha samaraliroq, ammo yuqoridagi ochko‘z algoritm kabi ular ham umumiy eng qisqa marshrutni topmaydi.

Kommivoyajyor masalasining optimalga yaqin yechimini topish uchun ishlatiladigan algoritmlar quyidagilar:

• 2-opt evristikasi: Yechimni bosqichma-bosqich yaxshilaydigan algoritm: har bir qadamda u ikkita qirrani olib tashlaydi va umumiy yo‘l uzunligini kamaytirish uchun ikki yo‘lni boshqacha usulda qayta ulaydi.
• Genetik algoritm: Tabiiy tanlanish jarayonidan ilhomlangan algoritm turi bo‘lib, masalalar, jumladan TSP yechimlarini rivojlantirish uchun tanlash, mutatsiya va chatishtirish (crossover) kabi usullardan foydalanadi.
• Simulated Annealing (imitatsion yumshatish): Bu usul metallurgiyadagi yumshatish (annealing) jarayonidan ilhomlangan. Bu jarayon nuqsonlarni kamaytirish uchun materialni qizdirib, so‘ngra sekin sovitishdan iborat. TSP kontekstida u yechimlar fazosini vaqti-vaqti bilan yomonroq yechimlarga o‘tishga ruxsat beradigan tarzda tadqiq qilib, optimalga yaqin yechimni topish uchun ishlatiladi; bu esa lokal minimumlarda qolib ketishning oldini olishga yordam beradi.
• Chumolilar koloniyasi optimallashtiruvi (Ant Colony Optimization): Bu algoritm chumolilarning uyadan oziq-ovqat manbalarigacha yo‘l topishdagi xatti-harakatidan ilhomlangan. Bu graflar orqali yaxshi yo‘llarni topishga keltirilishi mumkin bo‘lgan hisoblash masalalarini yechish uchun murakkabroq ehtimoliy usuldir.

Kommivoyajyor masalasini yechishning vaqt murakkabligi

Optimalga yaqin yechimni tez olish uchun, ushbu sahifadagi ikkinchi simulyatsiyadagi kabi, har bir qadamda shunchaki eng yaqin, hali borilmagan shaharga boradigan ochko‘z algoritmdan foydalanishimiz mumkin.

Kommivoyajyor masalasini shu tarzda ochko‘z usulda yechish har bir qadamda joriy shahardan boshqa barcha borilmagan shaharlargacha bo‘lgan masofalar taqqoslanishini anglatadi va bu bizga \(O(n^2) \) vaqt murakkabligini beradi.

Ammo ularning barchasi orasidan eng qisqa marshrutni topish ancha ko‘p amal talab qiladi va buning vaqt murakkabligi, yuqorida aytilganidek, \(O(n!)\) ga teng. Bu 4 ta shahar uchun 4! ta mumkin bo‘lgan marshrut borligini anglatadi, bu esa \(4 \cdot 3 \cdot 2 \cdot 1 = 24\) ga teng. Masalan, atigi 12 ta shahar uchun esa \(12! = 12 \cdot 11 \cdot 10 \cdot \; ... \; \cdot 2 \cdot 1 = 479,001,600\) ta mumkin bo‘lgan marshrut bor!

Quyidagi rasmda ochko‘z algoritmning vaqt murakkabligi \(O(n^2)\) ni barcha marshrutlarni solishtirish orqali eng qisqa marshrutni topishning vaqt murakkabligi \(O(n!)\) bilan taqqoslab ko‘ring.

Ammo tekshirishimiz kerak bo‘lgan marshrutlar sonini kamaytirish uchun ikkita narsa qilishimiz mumkin.

Kommivoyajyor masalasida marshrut bitta joyda boshlanib, o‘sha joyda tugaydi, ya’ni sikl hosil qiladi. Bu qaysi shahardan boshlashimizdan qat’i nazar, eng qisqa marshrut uzunligi bir xil bo‘lishini anglatadi. Shuning uchun yuqoridagi simulyatsiyada boshlanadigan shaharni qat’iy tanlab oldik va bu mumkin bo‘lgan marshrutlar sonini \(n!\) dan \((n-1)!\) gacha kamaytiradi.

Shuningdek, bu marshrutlar sikl bo‘ylab o‘tgani uchun marshrut u yoki bu yo‘nalishda bosib o‘tilganda ham bir xil masofaga ega bo‘ladi. Shu sababli aslida marshrutlarning faqat yarmining masofasini tekshirishimiz kerak, chunki qolgan yarmi xuddi shu marshrutlarning teskari yo‘nalishdagisi bo‘ladi, shunday qilib tekshirishimiz kerak bo‘lgan marshrutlar soni aslida \( \frac{(n-1)!}{2}\) ga teng.

Tekshirishimiz kerak bo‘lgan marshrutlar sonini \( \frac{(n-1)!}{2}\) gacha kamaytira olsak ham, vaqt murakkabligi baribir \( O(n!)\) bo‘lib qoladi, chunki juda katta \(n\) uchun \(n\) ni bittaga kamaytirish va 2 ga bo‘lish \(n\) oshirilganda vaqt murakkabligining qanday o‘sishiga sezilarli ta’sir ko‘rsatmaydi.

Vaqt murakkabligi qanday ishlashini yaxshiroq tushunish uchun ushbu sahifaga o‘ting.

Haqiqiy kommivoyajyor masalalari murakkabroq

Kommivoyajyor masalasi kontekstida grafdagi qirra vazni bir nuqtadan boshqasiga borish qanchalik qiyinligini bildiradi va biz minimallashtirmoqchi bo‘lgan narsa — marshrutning umumiy qirra vazni.

Ushbu sahifada hozirgacha qirra vazni ikki nuqta orasidagi to‘g‘ri chiziq bo‘yicha masofa bo‘lib keldi. Bu esa kommivoyajyor masalasini tushuntirish va uni ko‘rsatishni ancha osonlashtiradi.

Ammo real hayotda qirra vazniga ta’sir qiladigan boshqa ko‘plab omillar bor:

1. To‘siqlar: Bir joydan boshqasiga harakatlanayotganda odatda daraxtlar, daryolar, uylar kabi to‘siqlarni chetlab o‘tishga harakat qilamiz. Bu A dan B ga borish uzoqroq va ko‘proq vaqt talab qilishini anglatadi, shuning uchun buni hisobga olish uchun qirra vazni qiymatini oshirish kerak, chunki endi bu to‘g‘ri chiziq emas.
2. Transport tarmoqlari: Sayohat qilganda odatda yo‘l bo‘ylab yuramiz yoki jamoat transporti tizimlaridan foydalanamiz, bu ham bir joydan boshqasiga borish (yoki posilka jo‘natish) qanchalik qiyinligiga ta’sir qiladi.
3. Yo‘l harakati sharoitlari: Tirbandlik ham yo‘lga ketadigan vaqtga ta’sir qiladi, shuning uchun bu ham qirra vazni qiymatida aks etishi kerak.
4. Huquqiy va siyosiy chegaralar: Masalan, chegarani kesib o‘tish bir marshrutni boshqasiga qaraganda tanlash qiyinroq bo‘lishiga olib kelishi mumkin, ya’ni eng qisqa to‘g‘ri chiziqli marshrut sekinroq yoki qimmatroq bo‘lishi mumkin.
5. Iqtisodiy omillar: Yoqilg‘i sarfi, xodimlarning vaqtidan foydalanish, transport vositalariga texnik xizmat ko‘rsatish — bularning barchasi pul talab qiladi va ular ham qirra vaznlarida hisobga olinishi kerak.

Ko‘rib turganingizdek, qirra vaznlari sifatida shunchaki to‘g‘ri chiziqli masofalardan foydalanish haqiqiy masalaga nisbatan juda sodda bo‘lishi mumkin. Bunday soddalashtirilgan masala modeli uchun kommivoyajyor masalasini yechish, ehtimol, amaliy ma’noda optimal bo‘lmagan yechim beradi.

Qirra uzunligi endi shunchaki ikki nuqta orasidagi to‘g‘ri chiziqli masofa bo‘lmaganda kommivoyajyor masalasini vizuallashtirish oson emas, ammo kompyuter bunday holatlarni juda yaxshi uddalaydi.