Bajaruvchi: Bekmatov e tekshiruvchi: Axmedov f samarqand-2022 5-mavzu. P, Np, np-to’liq masalalar


Mavzu: Kommivoyajer haqidagi masala



Download 0,6 Mb.
bet4/6
Sana15.06.2022
Hajmi0,6 Mb.
#672519
1   2   3   4   5   6
Bog'liq
5-hafta, Bekmatov

Mavzu: Kommivoyajer haqidagi masala
Ishning maqsadi:Marshrutlar haqidagi masalani yechish va uni tahlil qilish
Kerakli jihozlar: Kompyuter, proyektor, doska, C++ dasturlash tili
Kommivoyajer (fr. commis voyageur) — sayohatchi savdogar. Kommivoyajer masalasi transport logistikasida muhim vazifa bo'lib, transportni rejalashtirish bilan shug'ullanadigan sanoatdir. Kommivoyajer uy xo'jaligida zarur bo'lgan va unchalik zarur bo'lmagan tovarlarni sotish uchun n nuqtani aylanib o'tishi va oxir-oqibat boshlang'ich nuqtasiga qaytishi kerak. Bu eng foydali aylanma marshrutni aniqlash uchun talab qilinadi. Marshrut rentabelligining o'lchovi sifatida (aniqrog'i, kamchilik) umumiy sayohat vaqti, yo'lning umumiy qiymati yoki eng oddiy holatda, marshrut uzunligi bo'lishi mumkin.
Kommivoyajer masalasi eng mashhur kombinatoriy optimallashtirish masalalaridan biri bo'lib, u belgilangan shaharlardan kamida bir marta o'tib, keyin asl shaharga qaytib keladigan eng foydali marshrutni topishdan iborat.
Ko'rinib turibdiki, masalani aylanma yo'lning barcha variantlarini sanab o'tish va eng maqbulini tanlash orqali hal qilish mumkin. Masala shundaki, mumkin bo'lgan marshrutlar soni n o'sishi bilan juda tez o'sib boradi (u n ga teng! - nuqtalarni buyurtma qilish mumkin bo'lgan usullar soni).
Masalan, 100 ball uchun variantlar soni 158 xonali raqam bilan ifodalanadi - hech qanday kalkulyator bunga dosh berolmaydi! Bir soniyada million variantni saralashga qodir kuchli kompyuter 310 144 yil davomida masala bilan kurashadi. Kompyuterning ishlashini 1000 baravar oshirish, garchi 1000 baravar kam bo'lsa-da, lekin variantlarni sanab o'tish uchun dahshatli vaqtni beradi. Har bir marshrut varianti uchun boshlang'ich nuqta (n variant) va aylanma yo'nalish (2 variant) tanlashda farq qiluvchi 2 * n ekvivalent mavjudligi ham vaziyatni saqlab qolmaydi. Ushbu kuzatishni hisobga olgan holda ro'yxatga olish variantlar bo'yicha biroz qisqartiriladi.
Filial va chegara usuli
Littlening algoritmi MVIG ning maxsus holatidir, ya'ni. eng yomon holatda, uning murakkabligi to'liq qidiruvning murakkabligiga teng. Nazariy tavsif quyidagicha:
Rafning barcha Gamilton sikllarining S to'plami mavjud. S ning har bir bosqichida biz chekka (i, j) qidiramiz, uning marshrutdan chiqarilishi pastki bahoni maksimal darajada oshiradi. Keyinchalik, to'plam ikkita ajratilgan S1 va S2 ga bo'linadi. S1 - chekka (i, j) ni o'z ichiga olgan va (j, i) ni o'z ichiga olmaydi. S2 - (i, j) ni o'z ichiga olmagan barcha tsikllar. Keyinchalik, har bir to'plam yo'lining uzunligi uchun pastki chegara hisoblab chiqiladi va agar u allaqachon topilgan yechim uzunligidan oshsa, to'plam o'chiriladi. Agar shunday bo'lmasa, S1 va S2 to'plamlari S bilan bir xil tarzda ishlanadi.
Algoritmik tavsif. Masofa matritsasi mavjud M. diagonali cheksiz qiymatlar bilan to'ldirilgan, chunki erta tsikllar sodir bo'lmasligi kerak. Pastki chegarani saqlaydigan o'zgaruvchi ham mavjud.
Shuni ta'kidlash kerakki, siz ikki turdagi cheksizlikni kuzatib borishingiz kerak - biri matritsadan satr va ustun o'chirilgandan so'ng qo'shiladi, shunda erta davrlar bo'lmaydi, ikkinchisi qirralarning tashlab yuborilganda. Ishlar biroz keyinroq ko'rib chiqiladi. Birinchi cheksizlikni inf1, ikkinchisini inf2 deb belgilaymiz. Diagonal inf1 bilan to'ldirilgan.



Download 0,6 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish