Bajardi: yusupova m qabul qidi: masharipova f



Yüklə 20,7 Kb.
səhifə1/2
tarix24.11.2023
ölçüsü20,7 Kb.
#133579
  1   2
MUNIRA Y


MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT
TEXNALOGIYALARI UNIVERSITETI URGANCH FILIALI KOMPYUTER INJINERINGI FAKULTETI 914-22 GURUH DISKRET TUZILMALAR FANIDAN

BAJARDI: YUSUPOVA M



QABUL QIDI: MASHARIPOVA F





MAVZU :Kommivoyajer masalasi algoritmlarini o‘rganish, chuqurlik va eni bo‘yicha aylanib o‘tuvchi graflar, kommivoyajer masalasini yechish

Reja;

1. Masala qo’yilishi.

2.Evristik algoritmlar.

3. GTS algoritmini tuzish

4. Algoritmni baholash
Masala qo’yilishi. 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.
Dastlabki ma’lumotlar Djek tasarrufidagi shaharlar ruyhati 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.


Yüklə 20,7 Kb.

Dostları ilə paylaş:
  1   2




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin