CURRENT APPROACHES AND NEW RESEARCH IN
MODERN SCIENCES
International scientific-online conference
14
KOMMIVOYAJER MASALASI. TARMOQLAR VA CHEGARALAR USULI
Mamatova Zilolaxon Xabibulloxonovna
Farg‘ona davlat universiteti, dotsent, pedagogika
fanlari bo‘yicha falsafa doktori (PhD)
ORCID: 0009-0009-9247-3510
E-mail: mamatova.zilolakhon@gmail.com
Tojimatov Inomjon Ikromjon o‘g‘li
Farg‘ona Davlat Universiteti Amaliy matematika yo‘nalishi 3-kurs
22.09-guruh talabasi
E-mail: tojimatovinomjon13@gmail.com
https://doi.org/10.5281/zenodo.15302818
Annotatsiya:
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:
CURRENT APPROACHES AND NEW RESEARCH IN
MODERN SCIENCES
International scientific-online conference
15
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
CURRENT APPROACHES AND NEW RESEARCH IN
MODERN SCIENCES
International scientific-online conference
16
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
2
1
5
B
0
∞
1
0
1
4
C
3
0
1
8
∞
0
D
2
3
2
2
0
∞
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).
Yangi kichik jadval:
CURRENT APPROACHES AND NEW RESEARCH IN
MODERN SCIENCES
International scientific-online conference
17
C
D
C
∞
0
D
0
∞
Bu yangi jadval uchun satr va ustun minimumlarini ayirish: C qatori
minimum: 0
D qatori minimum: 0
C ustun minimum: 0
D ustun minimum: 0
Hech qanday kamaytirish shart emas.
Chegara hisoblash: Yo'l masofasi A → B = 20
Oldingi quyi chegara: 64
Hozirgi satr/ustun kamaytmasi: 0
Yangi chegara = 64 + 20 = 84
Davom ettirish: B dan C ga, C dan D ga, D dan A ga ketishlar ketma-ket
tanlanadi.
Har safar jadval qisqaradi va chegara yangilanadi.
Oxir-oqibat topilgan optimal yo‘l: A → B → C → D → A
Va umumiy masofa:
A → B: 20
B → C: 30
C → D: 12
D → A: 35
Jami: 20 + 30 + 12 + 35 = 97
Tahlil:
Tarmoqlash orqali barcha imkoniyatlar tekshirildi.
Chegaralash orqali yomon variantlar erta chiqarib tashlandi.
Natijada umumiy hisoblashlar soni kamaydi.
Umumiy xulosa
Kommivoyajer masalasi (TSP) matematik modellashtirish, algoritmik
yondashuvlar va kombinatorik optimallashning eng muhim vakillaridan biri
hisoblanadi. Ushbu masala nazariy jihatdan murakkab bo‘lishiga qaramay, u
ko‘plab real hayotiy sohalarda — transport logistikasidan tortib, robototexnika,
chip dizayni va genetik tahlilga qadar — keng qo‘llaniladi. Aynan shuning uchun
ham bu masalaning samarali va ishonchli yechim usullarini ishlab chiqish ilmiy
va amaliy nuqtayi nazardan dolzarb masaladir.
CURRENT APPROACHES AND NEW RESEARCH IN
MODERN SCIENCES
International scientific-online conference
18
Tarmoqlar va chegaralar usuli bu borada eng muhim va ishonchli
algoritmik yondashuvlardan biri bo‘lib, ayniqsa kichik va o‘rta o‘lchamli TSPlar
uchun optimal natija berish imkoniyatiga ega. Ushbu usulning kuchli jihati
shundaki, u barcha ehtimoliy yechimlarni tekshirib chiqmasdan turib, optimal
yo‘lni topishga xizmat qiladi. Bunda "pastki chegara" tushunchasidan
foydalanish orqali yomon natija beradigan yo‘nalishlar erta aniqlanib, hisoblash
jarayonidan chiqarib tashlanadi. Bu esa hisoblash vaqtini va resurslarni sezilarli
darajada tejaydi.
Tadqiqot davomida olib borilgan eksperimental hisob-kitoblar natijasida
aniqlanganki, tarmoqlash va chegaralash orqali optimal marshrutni aniqlash
nafaqat matematik aniqlikka, balki algoritmik samaradorlikka ham olib keladi.
Misol tariqasida tahlil qilingan 4 ta shaharli TSP holatida umumiy quyi chegara,
tarmoqlanishlar soni, qadamlar bo‘yicha kamaytirish va optimal marshrut aniq
bosqichlarda kuzatildi. Bu usul orqali 97 birlikdan iborat optimal umumiy
masofa aniqlanib, barcha shaharlar faqat bir martadan ziyorat qilindi va
boshlang‘ich nuqtaga qaytildi.
Adabiyotlar:
1.
G. Dantsig, R. Fulkerson, S. Jonson, "Katta miqyosdagi sayohatchi-sotuvchi
muammosini hal qilish", 1954 yil.
2.
R. Bellman, "Sayohatchi sotuvchi muammosini dinamik dasturlash bilan
davolash", 1956 yil.
3.
M. Xeld, R. Karp, "Sayohatchi-sotuvchi muammosi va minimal kenglikdagi
daraxtlar", 1962 yil.
4.
Lawler, Lenstra, Rinnooy Kan va Shmoys, "Sayohatchi sotuvchi
muammosi: Kombinatoriy optimallashtirish bo'yicha boshqariladigan sayohat",
1985 yil.
5.
Applegate, Bixby, Chvátal, Kuk, "Sayohatchi sotuvchi muammosi:
Hisoblash tadqiqoti", 2007 yil.
6.
Axuja, Magnanti, Orlin, "Tarmoq oqimlari: nazariya, algoritmlar va
ilovalar", 1993 yil.
