Telekomunikatsiya texnologiyalari va kasbiy ta’lim fakulteti

Dinamik dasturlash — Maʼlumotlar tuzilmasi

Dinamik dasturlash muammoni kichikroq muammolarga ajratishda boʻlinish (divide) va yengishga (conquer) oʻxshaydi. Ammo boʻlinish va yegishdan farqli oʻlaroq, ushbu kichik muammolar mustaqil ravishda hal etilmaydi. Aksincha, ushbu kichik muammolarning natijalari esga olinadi va shu kabi yoki bir-birini toʻldiruvchi kichik muammolar uchun ishlatiladi.
Dinamik dasturlash bizda muammolar mavjud boʻlgan joylarda qoʻllaniladi, ularni oʻxshash kichik muammolarga boʻlish mumkin, natijada ularning natijalari qayta ishlatilishi mumkin. Koʻpincha, ushbu algoritmlar optimallashtirish uchun ishlatiladi. Qoʻl ostidagi kichik muammoni hal qilishdan oldin, dinamik algoritm ilgari yechilgan kichik muammolarning natijalarini oʻrganishga harakat qiladi. Eng yaxshi yechimga erishish uchun kichik muammolarning yechimlari birlashtirish
Shunday qilib, biz aytishimiz mumkinki:
• Muammoni kichik muammolarga boʻlish imkoniyati mavjud boʻlishi kerak.
• Kichik muammolarni maqbul yechimidan foydalangan holda maqbul yechimga erishish mumkin.
• Dinamik algoritmlar Memozatsiyadan foydalanadi.
Taqqoslash
Mahalliy optimallashtirishga murojaat qilingan greedy algoritmlardan farqli oʻlaroq, dinamik algoritmlar muammoni umumiy optimallashtirishga asoslanadi.
Umumiy yechimga erishish uchun yechimlar birlashtiriladigan algoritmlarni boʻlish va yengishdan farqli oʻlaroq, dinamik algoritmlar kichikroq masalaning natijasini ishlatadi va undan keyin katta-kichik masalani optimallashtirishga harakat qiladi. Dinamik algoritmlar Memoizatsiyadan foydalanib, yechilgan muammolarning natijasini eslaydi.
Misol
Dinamik dasturlash usuli yordamida quyidagi kompyuter muammolarini hal qilish mumkin:
• Fibonacci raqam seriyasi
• Knapsack muammosi
• Hanoi minorasi
• Floyd-Warshall tomonidan olib boriladigan eng qisqa yoʻl
• Dijkstra tomonidan olib boriladigan eng qisqa yoʻl
• Loyihani rejalashtirish
Dinamik dasturlash yuqoridan-pastga va pastdan yuqoriga qarab ishlatilishi mumkin. Va, albatta, aksariyat hollarda, oldingi yechimlarga murojaat qilish, CPU aylanishiga qaraganda qayta hisoblashdan koʻra arzonroq hamda samaraliroq boʻlishi ham mumkin.


Halqasimon bog’langan ro’yhatlar
Halqasimon bog’langan ro’yhatlarda tugunlar halqa ko’rinishda o’zaro bog’langan bo’ladi.Ya’ni oxirgi element korsatkichi NULL emas, birinchi elementga yo’naltirilgan bo’ladi.Bunday tuzilmalar qachon ishlatiladi, agar bir qancha yarayonlar bir vaqtning o’zida aynan bir resurslarni ishlatadigan bo’lsa, biz resurslarni teng taqsimlagan xolda ishlatilishini ta’minlashimiz kerak bo’ladi.

Tasavvur qilamiz, o’sha yarayonlar 6,5,8,10 sonlari bo’lsin, xuddi yuqoridagi rasmdagidek. Tuzilmaga current nomli ko’rsatkich orqali muroyaat qilamiz. Bitta elementga muroyaat qilib, shu yarayonni bayarilishini ta’minlash, ya’ni aktivlashtirish uchun uning qiymatini qaytaramiz va keying elementga o’tamiz.

Halqasimon ro’yhatlar ikki hil bo’ladi:

•