Algoritmlarda dekompozitsiyalash usullari
Download 411.79 Kb. Pdf ko'rish
|
Algoritmlarda dekompozitsiyalash (1)
ALGORITMLARDA DEKOMPOZITSIYALASH USULLARI. • Hozirgi kunga kelib kompyuter olimlari ko'p sonli masalalarni hal qilishning samarali algoritmlarini olishga imkon beradigan bir qator samarali usullarni ishlab chiqdilar. • Samarali algoritmlarni loyihalashtirishning eng muhim va eng keng qo'llaniladigan usuli bu dekompozitsiyalash deb nomlangan uslubdir. • Ushbu usul n o'lchamdagi masalaning kichikroq masalalarga shunday parchalanishini (bo'linishini) nazarda tutadi, shu kichik muammolarning echimlari asosida dastlabki masalaga echimini osongina olish mumkin. • Biz ushbu texnikaning birlashma tartiblash yoki ikkilik qidiruv daraxtlari kabi bir qator foydalanish usullarini yaxshi bilamiz. • Ushbu usulni ko'rsatish uchun taniqli Xanoy minoralari jumboqini ko'rib chiqamiz. • Uchta A, B va S novda bor, birinchi navbatda A tayoqchasiga bir nechta disklar tiqiladi: eng katta diametrli disk pastki qismida, yuqoridan esa - rasmda ko'rsatilgandek ketma-ket kamayib boruvchi disklar .. • Jumboqning maqsadi disklarni (birma-bir) tayoqdan tayoqqa o'tkazishdir. shuning uchun kattaroq diametrli disk hech qachon kichikroq diametrli diskning ustiga qo'yilmasligi va oxir-oqibat barcha disklar novda ustiga tiqilib qolishi uchun B. S disklarni vaqtincha saqlash uchun ishlatilishi mumkin. • Ushbu jumboqni echish uchun quyidagi oddiy algoritm mos keladi. Tayoqchalar uchburchakning tepalari ekanligini tasavvur qiling. Keling, barcha disklarning harakatlarini raqamlaymiz. Keyin, toq raqamlar bilan harakatlanayotganda, eng kichik diskni uchburchakda qo'shni chiziqqa soat yo'nalishi bo'yicha harakatlantirish kerak. Hatto raqamlangan harakatlar eng kichik disk bilan bog'liq bo'lmagan boshqa haqiqiy harakatlarni amalga oshiradi. • Eng kichik n disklarni A tayoqchadan B tayoqchaga o'tkazish muammosini n o'lchamdagi ikkita kichik muammolardan iborat deb tasavvur qilish mumkin. 1. Birinchidan, A - tayoqdan S tayoqqa n - 1 ta eng kichik disklarni A tayoqchada qoldirib, ko'chirishingiz kerak. Keyin ushbu diskni A dan B ga ko'chirish kerak. Keyin n - 1 diskni C burilish joyidan B tayoqchasiga o'tkazish kerak. Ushbu n - 1 disklarning harakati belgilangan usulni rekursiv ravishda qo'llash orqali amalga oshiriladi. Ko'chib yurmaydiganlardan kamroq, A, B yoki S pinlaridagi harakatlanuvchi disklar ostida nima borligi haqida o'ylashning hojati yo'q, garchi individual disklarning haqiqiy harakati unchalik aniq ko'rinmasa ham, rekursiv qo'ng'iroq stakalari shakllanishi tufayli qo'lda simulyatsiya qilish oson emas, kontseptual nuqtai nazardan, ushbu algoritm hali ham uning to'g'riligini tushunish va isbotlash uchun juda oddiy (va agar rivojlanish tezligi haqida gapiradigan bo'lsak, unda uning tengi yo'q). Parchalanish usuli yordamida algoritmlarni ishlab chiqishda qulaylik bu usulning juda mashhur bo'lishiga olib keldi; bundan tashqari, ko'p hollarda ushbu algoritmlar an'anaviy usullar bilan ishlab chiqilgan algoritmlarga qaraganda samaraliroq. Download 411.79 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling