Algoritmlarda dekompozitsiyalash usullari

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.