Kommivoyajer masalasi reja: Algoritmlarini o'rganish, chuqurlik va eni bo'yicha aylanib o'tuvchi graflar



Download 20,8 Kb.
bet3/5
Sana13.06.2022
Hajmi20,8 Kb.
#666203
1   2   3   4   5
Bog'liq
Kommivoyajer masalasi

Djek – kompyuterlar sotish bo’yicha agent (kommivoyajer), uning qaramog’ida 20 ta shahar bor. ishlayotgan kompaniya yo’l harajatlarining 50% ni to’laydi. Djek uning qaramog’ida bo’lgan har ikki shahar orasida yo’l harajatini hisoblab chiqqan. Masala yo’l harajatlarini kamaytirishdan iborat. Biz Djekga yo’l harajatlarini kamaytirishga yordam berishimiz kerak. Djekning marshruti o’zi yashagan shahardan boshlanib, qolgan hamma shaharlarni bir martadan o’tib, yana o’z shahriga qaytib kelishi kerak. Demak, biz tuzayotgan ruyhatda har bir shahar faqat bir marta uchrashi kerak, Lekin Djek yashagan shahar ikki marta uchrab, ruyhatning birinchi va oxirgi elementlari bo’ladi. Undan tashqari, ruyhatdagi shaharlar tartibi Djekning marshrutini belgilaydi. Ruyhatdagi ikkita oxirgi shaharlar orasidagi yo’l narxi – bu butun marshrut narxi deb hisoblanadi. Demak, agar biz Djekga eng kichik narxdagi ruyhatni tuzib bersak, masalani yechgan bo’lamiz.


  • Djek – kompyuterlar sotish bo’yicha agent (kommivoyajer), uning qaramog’ida 20 ta shahar bor. ishlayotgan kompaniya yo’l harajatlarining 50% ni to’laydi. Djek uning qaramog’ida bo’lgan har ikki shahar orasida yo’l harajatini hisoblab chiqqan. Masala yo’l harajatlarini kamaytirishdan iborat. Biz Djekga yo’l harajatlarini kamaytirishga yordam berishimiz kerak. Djekning marshruti o’zi yashagan shahardan boshlanib, qolgan hamma shaharlarni bir martadan o’tib, yana o’z shahriga qaytib kelishi kerak. Demak, biz tuzayotgan ruyhatda har bir shahar faqat bir marta uchrashi kerak, Lekin Djek yashagan shahar ikki marta uchrab, ruyhatning birinchi va oxirgi elementlari bo’ladi. Undan tashqari, ruyhatdagi shaharlar tartibi Djekning marshrutini belgilaydi. Ruyhatdagi ikkita oxirgi shaharlar orasidagi yo’l narxi – bu butun marshrut narxi deb hisoblanadi. Demak, agar biz Djekga eng kichik narxdagi ruyhatni tuzib bersak, masalani yechgan bo’lamiz.

Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:


  • Evristika yoki evristik algoritm – algoritm deb ta’riflanishi uchun quyidagi hususiyatlarga ega bo’lishi kerak:

  • U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak. Odatda yahshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlaydigan va barcha test topshiriqlariga javob beradigan algoritmni tuzdik, lekin uning to’g’riligini isbotlab bilmaymiz. Shunday isbot berilmaguncha, algoritm evristik deb tushuniladi.Misol tariqasida quyidagi algoritmni ko’rib chiqamiz:

  • GTS algoritmi: (kommivoyajer). N ta shaharlar va C narxlar matrisasi berilgan kommivoyajer masalasi uchun U shahardan boshlab COST narxli TOUR yaqinlashgan yechimni topish kerak. Qadam 0: [Insiallashtirish] TOUR:=0; COST:=0; V:=U; Qadam 1: [Hama shaharlarni o’tish] For k:=1 to N-1 do qadam 2; Qadam 2: [Keyingi vektorga o’tish]Faraz qilaylik, (V,W) – V shahardan W ga olib borayotgan eng kichik narxli vektor. Unda:

  • TOUR:=TOUR+(V,W); COST:=COST+C(V,W);

  • V:=W; Qadam 3: [Marshrutni tugatish] TOUR:=TOUR+(V,1);COST:=COST+C(V,1);Marshrutni tasvirlash uchun biz matematikada graf yoki tur deb nomlanayotgan chizmadan foydalanamiz. Umuman tur – bu nuqtalar va bir nechta yoki barcha ikki nuqtalarni bog’layotgan chiziqlar to’plami, undan tashqari chiziqlar ustida qiymatlar ham berilishi mumkin.

  • Masalani soddalashtirish uchun beshta shahar uchun yechim topamiz. Rasm. 1a – narxlar matrisasi. Rasm. 1b – turli model ko’rsatilgan.

Download 20,8 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




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