Dag‘al kuch” usuli. Xasis algoritmlar “Dag`al kuch” usuli bilan tartiblash. Kommuvoyajer masalasi

“Dag‘al kuch” usuli. Xasis algoritmlar
“Dag`al kuch” usuli bilan tartiblash. Kommuvoyajer masalasi.

Algoritmlar nazariyasida “ajrat va xukmronlik qil” tamoyili bo`yicha qurilgan algoritmlarni yaxlit sinfi bor. “Ajrat va xukmronlik qil” paradigmasi dastlabki murakkab masalani ikkita yoki undan ko`proq nisbatan sodda masalalarga bo`luvchi algoritmlarni birlashtiradi. Ushbu sodda masalalarni yechimiga asoslanib keyinchalik dastlabki masalala yechimi quriladi. Xozirg ivaqtda algoritmlashni ushbu tamoyili ko`p yo`nalishlarda muvaffaqiyatli qo`llaniladi. Bu yerda biz ularni ba’zilari xaqida ma’lumotlar beramiz va “dag’al kuch” usulini amalda qo`llash metodikasini keltiramiz.

“Dag`al kuch” atamasi foydalanishga kiritilishi shu bilan bog`liqki, masala qismlarga bo`linganda ko`p xolda bo`lish amali xaqida o`ylab ham o`tirilmaydi. Keyinroq ko`ramizki bunga extiyoj ham bo`lmaydi. Ushbu tamoyilni tasavvur qilish uchun soddamasalani ko`raylik.
Berilgan sonlar yig`indisini toping. Albatta yig`indini ifodada berilgan ketma-ketlikda to`g`ridan-to`g`ri bajarish mumkin. Bu xolda yig`indi asta-sekin oshib boradi. Ikkinchi usul: avval juft-jufti bilan qo`shib olib keyin yana juftlab qo`shib olamiz Bu xolda oraliq yig`indilar nisbatan kichik bo`ladi.
Ikkita natural sonlar x va y uchun eng katta umumiy bo`luvchini (EKUB) topuvchi Yevklid algoritmini eslaylik. Agar bu sonlar katta bo`lsa masala ancha murakkab bo`ladi. Agar ularning ayirmasi ham EKUB ga bo`linishini hisobga olsak, masalani soddalashtirib x, z sonlar uchun EKUB ini topishga o`tishimiz mumkin. Ularni o`sish tartibida joylashtirib xdeb belgilasak, u xolda biz masalani avvalgi faqat kichik qiymatlardagi berilishiga qaytamiz. Bu usulni y-x=x shart bajarilguncha davom ettiramiz va EKUB=x ni olamiz. Ta’biiyki, bu dastlabki x emas. Misol tariqasida quyidagini ko`ramiz:
x=24; y=64.
1-chiqadam z=y-x=40 x=24; y=40
2- chiqadam z=y-x=16 x=16; y=24
3- chiqadam z=y-x=8 x=8; y=16
4- chiqadam z=y-x=8 bu yerda z=x=8 EKUB bo`ladi.
Sonlar massivini o`sish tartibida tartiblash masalasini ko`rib chiqamiz. Ushbu masalani yechish usullaridan biri qo`shni elementlarni o`sish tartibida asta-sekin o`rin almashtirilishi. Bu algoritmni blok-sxemasini keltiramiz. Bizga n ta elementdan iborat a₁,a₂,…,a_n sonlar massivi berilgan bo`lsin. Ularni o`sish tartibida joylashtirishimiz lozim. Agar dastlabki xolatni saqlab qolish zaruriyati bo`lsa, u xolda biz b<sub>i</sub>=a<sub>i</sub> bo`lgan ishchi massivi b₁, b₂,…,b_n ni shakllantirishimiz mumkin.
Algoritmining blok – sxemasini tuzamiz:

Boshlanishh



Kirit.N;A;B



k=1÷n-1

ha

i=1÷n-1



yo`q






C= ; ; =c



Tamom

Chiqish B

Ushbu algoritm bajarilishi jarayonini tushuntirish uchun a_n=min(a₁,a₂,…,a_n) bo`lgan holni ko`ramiz. Agar k=1 bo`lganda I bo`yicha sikl n=1 marta solishtirish bajarib, b_n,,b_n-1, larni o`rnini almashtiradi va a<sub>n</sub> ham b<sub>n-1</sub> ni o`rnini egallaydi. k=2 bo`lganda yana I bo`yicha siklda n-1 marta solishtirishlar bajarilib a_n ni o`rnini b<sub>n-2</sub> egallaydi va xokazo, shundan so`ng k=n-1 bo`lganda a<sub>n,</sub> b<sub>1</sub> o`rnini egallaydi, ya’ni zarur bo`lgan joyini egallaydi.

Tabiiyki, hisoblash davomida hamma a_i lar ham o`z o`rnini egallaydi. Shunday qilib, bu algoritm bo`yicha (n-1)(n-1) marta solishtirishni amalga oshirish kerak. Algoritmning samaradorligi bajarilgan amallar soniga qarab baholanadi. Ushbu algoritmda taqqoslash operasiyasi murakkab (ko`p mehnat talab qiladigan) amal bo`ladi, bundan kelib chiqadiki algoritmning murakkabligi (n-1)<sup>2</sup> tartibida bo`ladi.



8 7 6 5

4 3 2 1

8 7

6 5

4 3

2 1






8

7

6

5

4

3

2

1

7 8

5 6

3 4

1 2

5 6 7 8

1 2 3 4

1 2 3 4 5 6 7 8

Bu masalani yechishning yana bir algoritmi, “ajrat va xukmronlik qil” tamoili asosida ishlaydigan algoritm bo`ladi. Ushbu algoritmga ko`ra barcha massiv ikkita (teng) qismga bo`linadi, o`z navbatida bu qismlar ham ikki qismga bo`linadi. Qismlarga bo`lish xar bir qismda bitta element qolguncha davom ettiriladi. Shundan so`ng, bo`linmaning kichik qismlarning har birida tartiblashtirish amalga oshiriladi, so`ngra ushbu qismlarni berilgan massivga teskari tartibda birlashtirib boriladi. Bu jarayon dastlabki massiv tartiblangan xolda olinguncha davom etadi. Algortmning ishlash tamoyilini (prinsipini) sxematik ravishda Misol yordamida tasvirlaymiz, bu yerda berilgan massiv quyidagi ko`rinishda 8;7;6;5;4;3;2;1 bo`ladi.

Ushbu algoritmga muvofiq n sonli massivni tartiblashtirish uchun nlog₂n ga solishtirish amalini bajarish zarurligiga ishonch xosil qilish qiyin emas. Demak, bu usul yanada samaraliroq bo`ladi. Sonli to`plamni ikki qismga bo`lishda biz “qo`pol” qilib a₁, a₂,…a_m birinchi qismi, a_m+1, a_m+2,…,a_2m ikkinchi qismi qilib bo`lib oldik. Siz albatta askarlarni bo`linishi kabi bo`lishingiz mumkin, ya’ni birinchi turgan askar birinchi qismga, ikkinchi turgan askar ikkinchi qismga va x.k. “Ajrat va xukmronlik qil” tamoilini qo`llash sifatida hisoblash paydo bo`lishidan ancha oldin kirtilgan pochta xizmatidagi manzillarni indekslash usulini keltirish mumkin.
Pochta indekslariga ko`ra xatlar geografik joylashuviga qarab, avval viloyatlar, keyin shaharlar, so`ng tumanlar bo`yicha bo`linib pochta aloqasi bo`limlariga yuboriladi undan so`ng po`chtachilar orqali manzilga yetkaziladi. O`zingizni pochta indeksingizni eslab ko`ring, undagi xar bir raqam geografik bo`linishga egaligini ko`rish mumkin. Shu bilan birga saralovchi avtomat indekslar bo`yicha xatlarni aloxida paketlarga ajratadi.
Yana bir turdagi masalada “Ajrat va xukmronlik qil” tamoili qo`llanilib, bu rekursiv funksiyalar yoki algoritmlardir. Agar rekursiya mavjud bo`lsa funksiya o`z ichida o`ziga ega bo`ladi. Buni shartli ravishda quyidagicha yozish mumkin: