-masala {a,b,c,d,e} shaharlar berilgan bo’lsa, kommivoyajer masalasini yechish uchun yo’nalishlarning barcha ko’rinishlarini aniqlash dasturini tuzing

Kommivoyajer masalasi, berilgan shaharlarni eng qisqa yo'nalishda bir-biriga bog'liq bo'lgan joylashuvlarda bir qatorda barcha shaharlarni duch kelish masalasidir. Bu masalani yechishning optimal yechimini topish uchun "turdagi barcha yo'nalishlarni tekshirish" (brute-force) algoritmi ishlatiladi. Bu algoritmni Python da ko'rsatib beraylik:

import itertools
def kommivoyajer(shaharlar):
min_masofa = float('inf') # Eng qisqa masofa
optimal_yunalishlar = [] # Optimal yo'nalishlar
# Turdagilarni barcha ko'rish kombinatsiyalarini generatsiya qilish
kombinatsiyalar = itertools.permutations(shaharlar)
for kombinatsiya in kombinatsiyalar:
masofa = 0 # Joriy kombinatsiyadagi masofa
for i in range(len(kombinatsiya) - 1):
shahar1 = kombinatsiya[i]
shahar2 = kombinatsiya[i + 1]
# Shaharlar orasidagi masofani qo'shish
masofa += masofa_aniqlash(shahar1, shahar2)
# Yangi eng qisqa masofani topish
if masofa < min_masofa:
min_masofa = masofa
optimal_yunalishlar = kombinatsiya
return min_masofa, optimal_yunalishlar
# Shaharlar orasidagi masofani aniqlash uchun funktsiya
def masofa_aniqlash(shahar1, shahar2):
# Shaharlar orasidagi masofani qaytarish
# Bu funktsiyani o'zingizning masofa formulangizga moslashtirishingiz kerak
# Masalan, Google Maps API yoki boshqa masofa qaytaradigan xizmatdan foydalanishingiz mumkin
# Bu misolda, masofani 1 deb hisoblaymiz
return 1
# Test qilish
shaharlar = ['a', 'b', 'c', 'd', 'e']
eng_qisqa_masofa, optimal_yunalishlar = kommivoyajer(shaharlar)
# Natijalarni chiqarish
print("Eng qisqa masofa:", eng_qisqa_masofa)
print("Optimal yo'nalishlar:", optimal_yunalishlar)
Ushbu kodga berilgan shaharlar ro'yxati orqali algoritm kommivoyajer masalasini yechadi. masofa_aniqlash funksiyasi shaharlar orasidagi masofani aniqlash uchun o'zingizning formulangizga moslashtirilishi kerak. Bu misolda, masofani 1 deb hisoblaymiz.
Kodi ishga tushirgandan so'ng, eng qisqa masofa (eng_qisqa_masofa) va optimal yo'nalishlarni (optimal_yunalishlar) chiqarishimiz mumkin.
3-masala
Pitsa tarqatuvchi ishchiga shaharning 6 ta nuqtasidan buyurtma tushdi. Pitsa tarqatuvchi hodimga shu buyurtma berilgan nuqtalar orasidagi masofalar ma’lum. U iqtisodiy tomondan va vaqt bo’yicha yutishga harakat qilmoqchi. Unga eng kam masofa bosib o’tgan holda pitsalarni tarqatib chiqishiga yordam bering.