Kommivoyajer haqida masala

Kommivoyajer haqida masala

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 ro’yxati 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 - 20´ 20 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 ro’yxatda har bir shahar faqat bir marta uchrashi kerak, Lekin Djek yashagan shahar ikki marta uchrab, ro’yxatning birinchi va oxirgi elementlari bo’ladi. Undan tashqari, ro’yxatdagi shaharlar tartibi Djekning marshrutini belgilaydi. Ro’yxatdagi ikkita oxirgi shaharlar orasidagi yo’l narxi – bu butun marshrut narxi deb hisoblanadi. Demak, agar biz Djekga eng kichik narxdagi ro’yxatni 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, yaxshi 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 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: