Fan nomi: Algoritmlarni loyihalash Laboratoriya ishi 4 Mavzu



Download 86,69 Kb.
bet1/3
Sana22.03.2021
Hajmi86,69 Kb.
#61874
  1   2   3
Bog'liq
AL L4
1e51c3d3-be1b-4024-95fd-bc417e01c0a5, 1e51c3d3-be1b-4024-95fd-bc417e01c0a5, Товарлар экспертизаси, ~$skalda topshiriq, 2 5332441080417748518, 2 5332441080417748518, 2 5332441080417748518, ANGLIYANING TARIXIY OBIDALARI, oraliq, oraliq, Taqriz Fazliddin, izerp 91 928, 2 5389041508064167523, 2 5389041508064167523

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLO GIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI

Fan nomi: Algoritmlarni loyihalash

Laboratoriya ishi - 4

Mavzu: Dinamik dasturlash masalasini yechish.

Topshirdi: Karimov Shermuhammad

Guruh: CAL014

Toshkent – 2020

Variant 10



Nazariy ma’lumot:

Masala qo’yilishi. Djek – kompyuterlar sotish bo’yicha agent (kommivoya- jer), uning qaramog’ida 20 ta shahar bor. ishlayotgan kompaniya yo’l xarajatlari- ning 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.

Dastlabki ma’lumotlar Djek tasarrufidagi shaharlar ro’yhati va narxlar matrisasi ko’rinishida berilgan. Bu yerda matrisa shahardan j shaharga borish narxiga teng bo’lgan c(i,j) elementlardan tashkil topgan ikki o’lchamli massiv. Shaharlar soni 20 ta bo’lsa, matrisa -  bo’ladi.

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.



Evristik algoritmlar.

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


  1. U odatda shartli ravishda optimal bo’lmasa ham, yahshi yechimlarni topish kerak.


  2. Uni ixtiyoriy ma’lum aniq algoritmdan ko’ra, amalga oshirish tezroq va soddaroq bo’lishi kerak.



Odatda yaxshi algoritmlar evristik bo’lib chiqadi. Faraz qilaylik, biz tez ishlay- digan 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.


Download 86,69 Kb.

Do'stlaringiz bilan baham:
  1   2   3




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

    Bosh sahifa
davlat universiteti
ta’lim vazirligi
axborot texnologiyalari
maxsus ta’lim
zbekiston respublikasi
guruh talabasi
O’zbekiston respublikasi
nomidagi toshkent
o’rta maxsus
texnologiyalari universiteti
toshkent axborot
davlat pedagogika
xorazmiy nomidagi
rivojlantirish vazirligi
pedagogika instituti
Ўзбекистон республикаси
tashkil etish
haqida tushuncha
vazirligi muhammad
таълим вазирлиги
O'zbekiston respublikasi
toshkent davlat
махсус таълим
respublikasi axborot
kommunikatsiyalarini rivojlantirish
vazirligi toshkent
saqlash vazirligi
fanidan tayyorlagan
bilan ishlash
Toshkent davlat
Ishdan maqsad
sog'liqni saqlash
uzbekistan coronavirus
respublikasi sog'liqni
fanidan mustaqil
coronavirus covid
koronavirus covid
vazirligi koronavirus
covid vaccination
qarshi emlanganlik
risida sertifikat
sertifikat ministry
vaccination certificate
o’rta ta’lim
matematika fakulteti
haqida umumiy
fanlar fakulteti
pedagogika universiteti
ishlab chiqarish
moliya instituti
fanining predmeti