DSA tabulyatsiya

Tabulyatsiya

Tabulyatsiya — masalalarni yechish uchun ishlatiladigan usul.

Tabulyatsiya jadvaldan foydalanadi: unda avval eng oddiy qism masalalarning natijalari saqlanadi. So‘ngra jadval biz izlayotgan to‘liq masalaning natijasini topgunimizcha tobora ko‘proq qism masala natijalari bilan to‘ldiriladi.

Tabulyatsiya usuli masalalarni "pastdan yuqoriga" (bottom-up) yechadi deyiladi, chunki u avval eng oddiy qism masalalarni yechadi.

Tabulyatsiya dinamik dasturlashda qo‘llaniladigan usul, ya’ni tabulyatsiyadan foydalanish uchun biz yechmoqchi bo‘lgan masala ustma-ust tushuvchi qism masalalardan iborat bo‘lishi kerak.

Tabulyatsiya yordamida \(n\)-Fibonachchi sonini topish

Fibonachchi sonlari turli dasturlash usullarini, jumladan, tabulyatsiya qanday ishlashini namoyish qilish uchun juda qulay.

Tabulyatsiya avval eng kichik Fibonachchi sonlari \(F(0)=0\) va \(F(1)=1\) bilan to‘ldiriladigan jadvaldan foydalanadi (pastdan yuqoriga). Jadvalda saqlanadigan keyingi Fibonachchi soni \(F(2)=F(1)+F(0)\) bo‘ladi.

Keyingi Fibonachchi soni har doim oldingi ikki sonning yig‘indisiga teng:

\[ F(n)=F(n-1)+F(n-2) \]

Shu tarzda jadval biz izlayotgan \(n\)-Fibonachchi sonini topgunimizcha keyingi Fibonachchi sonlari bilan to‘ldirilib boradi.

def fibonacci_tabulation(n):
    if n == 0: return 0
    elif n == 1: return 1

    F = [0] * (n + 1)
    F[0] = 0 
    F[1] = 1

    for i in range(2, n + 1):
        F[i] = F[i - 1] + F[i - 2]
    
    print(F)
    return F[n]
  
n = 10
result = fibonacci_tabulation(n)
print(f"\nThe {n}th Fibonacci number is {result}")

\(n\)-Fibonachchi sonini topishning boshqa usullari qatoriga rekursiya yoki uning memoizatsiya yordamida yaxshilangan versiyasi kiradi.

Tabulyatsiya — pastdan yuqoriga yondashuv

Nima uchun tabulyatsiya "pastdan yuqoriga" yondashuv deb atalishini yaxshiroq tushunish uchun quyidagi chizmalarga qarang.

Solishtirish uchun \(n\)-Fibonachchi sonini topishning "yuqoridan pastga" rekursiya yondashuvi chizmasiga qarang.

Tabulyatsiya yondashuvi 10-Fibonachchi sonini topish uchun jadvalni \(F(0)\) va \(F(1)\) dan boshlab pastdan yuqoriga qura boshlaydi.

Rekursiv yondashuv \(F(10)\) ni topishga harakat qilishdan boshlaydi, ammo uni topish uchun \(F(9)\) va \(F(8)\) ni chaqirishi kerak va shu tarzda funksiya chaqiruvlari yakuniy javobga birlashtiriladigan qiymatlarni qaytara boshlashidan oldin u \(F(0)\) va \(F(1)\) gacha pastga tushib boradi.

Tabulyatsiya yordamida yechiladigan boshqa masalalar

\(n\)-Fibonachchi sonini topish kabi, tabulyatsiya boshqa masalalarning yechimini topish uchun ham ishlatilishi mumkin:

• 0/1 ryukzak masalasi — bu ryukzakka (oddiy orqa sumkaga) joylashimiz mumkin bo‘lgan, har biri turli qiymatga ega buyumlar to‘plami haqidagi masala. Masalani yechish uchun biz joylaydigan buyumlarning umumiy qiymatini maksimal qiladigan buyumlarni topishimiz kerak, ammo ryukzakning vazn chegarasi borligi sababli xohlagan barcha buyumlarni ololmaymiz.
• Eng qisqa yo‘l masalasini Bellman-Ford algoritmi yordamida yechish mumkin, u ham grafdagi eng qisqa yo‘llarni topish uchun tabulyatsiyadan foydalanadi. Aniqroq aytganda, Bellman-Ford algoritmidagi tabulyatsiya yondashuvi "distances" massividagi qiymatlarning yangilanish usulida namoyon bo‘ladi.
• Kommivoyajyor masalasini Held-Karp algoritmi yordamida aniq yechish mumkin, u ham tabulyatsiyadan foydalanadi. Bu algoritm ushbu darslikda tavsiflanmagan, chunki u brute force \(O(n!)\) dan yaxshiroq bo‘lsa-da, baribir unchalik samarali emas \(O(2^n n^2)\) va ancha murakkab.

Dinamik dasturlashda tabulyatsiya

Sahifa boshida aytilganidek, tabulyatsiya (xuddi memoizatsiya kabi) dinamik dasturlash deb ataladigan usulda qo‘llaniladi.

Dinamik dasturlash — masalalarni yechish uchun algoritmlarni loyihalash usuli.

Dinamik dasturlash ishlashi uchun biz yechmoqchi bo‘lgan masala quyidagi ikki xususiyatga ega bo‘lishi kerak:

• Masala kichikroq, ustma-ust tushuvchi qism masalalardan tashkil topgan bo‘lishi kerak. Masalan, \(F(3)\) Fibonachchi sonining yechimi \(F(2)\) va \(F(1)\) Fibonachchi sonlarining yechimlari bilan ustma-ust tushadi, chunki \(F(3)\) ni \(F(2)\) va \(F(1)\) ni birlashtirib olamiz.
• Masala, shuningdek, optimal qism tuzilmaga ega bo‘lishi kerak, ya’ni masalaning yechimini uning qism masalalari yechimlaridan tuzish mumkin bo‘lishi kerak. \(n\)-Fibonachchi sonini topishda \(F(n)\) ni \(F(n-1)\) va \(F(n-2)\) ni qo‘shish orqali topish mumkin. Demak, \(F(n)\) ni topish uchun oldingi ikki sonni bilish yetarli emas, ularni qanday birlashtirishni bilishimiz uchun tuzilmani ham bilishimiz kerak.

Dinamik dasturlash haqida keyingi sahifada batafsil o‘qing.