Mavzu: Xasislik algoritmlari Algoritmlarni loyihalash fani Reja: xasis algoritmlar

3. Xasis tanlov amalga oshirilgandan so'ng qism masala qolsin, ushbu qism masalaning optimal yechimini qilingan xasis tanlov bilan birlashtirganda qo’yilgan masalaning optimal yechimiga olib kelishini ko'rsating. Yuqorida tavsiflangan jarayon keyingi vazifalarda qo'llaniladi.

• 3. Xasis tanlov amalga oshirilgandan so'ng qism masala qolsin, ushbu qism masalaning optimal yechimini qilingan xasis tanlov bilan birlashtirganda qo’yilgan masalaning optimal yechimiga olib kelishini ko'rsating. Yuqorida tavsiflangan jarayon keyingi vazifalarda qo'llaniladi.
• Eslatma. Har qanday xasis algoritmning markazida deyarli har doim dinamik dasturlash uslubidagi yanada murakkab yechim bo'ladi.

xasis tanlov xususiyatlari

• Yuqorida aytib o'tilgan xasis algoritmning asosiy tarkibiy qismlaridan birinchisi xasis tanlov xususiyatidir: global maqbul yechimni lokal maqbul (xasis) tanlov orqali olish mumkin. Boshqacha qilib aytganda, qaysi tanlovni tanlash lozimligini muhokama qilib, biz joriy vazifada eng yaxshi hisoblanadigan tanlovni qilamiz; vujudga kelgan qism masalalarning natijalari hisobga olinmaydi. Xasis algoritmlarning va dinamik dasturlashdan farqini ko'rib chiqamiz. Dinamik dasturlashda har bir bosqichda tanlov qilinadi, lekin odatda bu tanlov qismmasalalarning yechimlariga bog'liq bo’ladi. Shuning uchun, dinamik dasturlash usulida odatda masalalar yuqoriga yo'naltirib yechiladi, ya'ni avval sodda qism masalalar, so'ngra murakkabroq masalalar qayta ishlanadi.

xasis tanlov xususiyatlari

• Xasis algoritmda joriy vaqtda eng yaxshi hisoblangan tanlov amalga oshiriladi, shundan so'ng ushbu tanlov natijasida yuzaga kelgan qism masala hal qilinadi. Xasis algoritmda qilingan tanlov oldingi tanlovlarga bog'liq bo'lishi mumkin, ammo u keyingi qism masalalarning biron bir tanlovi yoki yechimiga bog'liq bo'lolmaydi. Shunday qilib, qism masalalar o’sish tartibida yechiladigan dinamik dasturlashdan farqli o'laroq, xasis strategiya odatda kamayish tartibida amalga oshiriladi, bunda xasis tanlov birma-bir amalga oshirilganda, joriy masalaning har bir nusxasi soddalashtirilgan holatga keltiriladi.