Reja Xasislik algoritmlari haqida tushuncha
Download 309.73 Kb. Pdf ko'rish
|
Reja Xasislik algoritmlari haqida tushuncha
- Bu sahifa navigatsiya:
- Sumka( рюкзак) masalasi
Texnik terminlar bilan: har bir qadamda mahalliy maqbul yechim tanlanadi
va oxirida siz global miqyosda eng maqbul yechimni olasiz. Ishonasizmi yoki yo'qmi, bu oddiy algoritm rejalashtirish muammosining maqbul yechimini muvaffaqiyatli topmoqda! Albatta, xasislik algoritmlar har doim ham ish bermaydi. Ammo ularni amalga oshirish juda oson! Boshqa misolni ko'rib chiqaylik. Sumka( рюкзак) masalasi Aytaylik, Siz ochko’z o'g'risiz. Siz sumkangiz bilan do'kondasiz va u yerdagi narsalarni o'g'irlashingiz mumkin. Ammo siz faqat sumkangizga mos keladigan og’irlikdagi narsalarni olishingiz mumkin. Sumka 35 funtni ko’tarishi mumkin. Siz sumka ichiga yig'ilishi mumkin bo'lgan maksimal qiymatga ega tovarlar to'plamini olishingiz kerak. Siz qanday algoritmdan foydalanasiz? Bunda , Xasislik algoritm juda oddiy ko'rinadi: - Sumkaga to'g'ri keladigan eng qimmat narsani tanlang. - Sizning sumkangizga mos keladigan keyingi eng qimmat narsani tanlang ... va hokazo. Ayrim vaqtlarda bu algoritm ishlamay qolishi mumkin. Masalan, uchta narsani o'g'irlashingiz mumkin deylik. Sumka umumiy og'irligi 35 funtdan oshmaydigan tovarlarga mos keladi. Eng qimmat mahsulot - magnitafon, siz uni tanlaysiz. Endi boshqa joy qolmadi. Siz 3000 dollarlik tovarlar oldingiz. Shoshmay turing! Agar siz magnitafon o'rniga noutbuk va gitara tanlasangiz, tovarlar narxi 3500 dollarni tashkil etadi! Shubhasiz, Xasislik strategiya optimal yechimni ta'minlamaydi. Biroq, natija optimal darajadan unchalik uzoq emas. Keyingi bobda men to'g'ri echimni qanday hisoblashni tushuntiraman. Ammo do'konga kirgan o'g'ri idealga intilishi qiyin. “Yetarlicha yaxshi” yechim yetarli bo’ladi. Ikkinchi misol bizni quyidagi xulosaga olib keladi: Ba'zida ideal yaxshining aksidir. Ba'zi hollarda masalani yaxshiyechimini topish uchun bu algoritm yetarli. Bunday masalalarda Xasislik algoritmlar juda yaxshi ishlaydi, chunki ular oson amalga oshiriladi va natija odatda optimal yechimga yaqin bo’ladi. Download 309.73 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling