KOMMIVOYAJER MASALASI. TARMOQLAR VA CHEGARALAR USULI
DOI:
https://doi.org/10.5281/zenodo.15302818Keywords:
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.Abstract
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.
References
G. Dantsig, R. Fulkerson, S. Jonson, "Katta miqyosdagi sayohatchi-sotuvchi muammosini hal qilish", 1954 yil.
R. Bellman, "Sayohatchi sotuvchi muammosini dinamik dasturlash bilan davolash", 1956 yil.
M. Xeld, R. Karp, "Sayohatchi-sotuvchi muammosi va minimal kenglikdagi daraxtlar", 1962 yil.
Lawler, Lenstra, Rinnooy Kan va Shmoys, "Sayohatchi sotuvchi muammosi: Kombinatoriy optimallashtirish bo'yicha boshqariladigan sayohat", 1985 yil.
Applegate, Bixby, Chvátal, Kuk, "Sayohatchi sotuvchi muammosi: Hisoblash tadqiqoti", 2007 yil.
Axuja, Magnanti, Orlin, "Tarmoq oqimlari: nazariya, algoritmlar va ilovalar", 1993 yil.
