Masala qo’yilishi. Evristik algoritmlar gts algoritmini tuzish

REJA:

• 
  Algoritmlarini o'rganish, chuqurlik va eni bo'yicha aylanib o'tuvchi graflar
  
• 
  Kommivoyajer masalasini va uning yechilishi
  
• 
  Masala qo’yilishi.
  
• 
  Evristik algoritmlar
  
• 
  GTS algoritmini tuzish
  

Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.

• 
  Algoritm tushunchasi zamonaviy matematika va informatikaning asosiy tushunchalaridan biri hisoblanadi. Algoritm termini o’rta asrlar ulug’ matematigi al-Xorazmiy nomidan kelib chiqqan. XX asrning 30-yiligacha algoritm tushunchasi ko’proq matematik ma’no emas, balki metodologik ma’noni kasb etar edi. Algoritm deganda, u yoki bu masalalar sinfini yechish imkonini beruvchi aniq ifodalangan chekli qoidalar majmui tushunilgan. EHM larning paydo bo’lishi bilan algoritm tushunchasi yanada keng tarqaldi. EHM va dasturlash usullarining rivojlanishi algoritmlarni ishlab chiqish avtomatlashtirishdagi zaruriy bosqich ekanligini tushunishga yordam berdi. EHM larning paydo bo’lishi algoritmlar nazariyasining rivojlanishiga olib keldi. Algoritmlarni tuzish – bu ijodiy ish bo’lib, ixtiyoriy zaruriy algoritmni tuzish uchun umumiy usullar mavjud emas, kishining ijodiy qobiliyatiga bog’liq.
  

: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 i 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 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.