Thursday, September 12, 2013

Фибоначийн дарааллын N дэх утгыг олох. Динамик програмчлал

Фибоначийн дараалал гэдэг бол
1, 1, 2, 3, 5, 8, 13, 21, 34, 55 .....
буюу эхний хоёр ширхэг тоо нь 1 тэй тэнцүү, бусад тоонууд нь өмнөх хоёр тооныхоо нийлбэртэй тэнцүү байдаг тийм чанартай дарааллыг хэлдэг.



Тэгвэл фибоначийн N дэх тоог хэрхэн олох вэ?
алгоритм ёсоор хялбархан рекурсив функц дуудалттайгаар дараах байдлаар биччихэж болно.

def fib(n):
    if n<=2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

print fib(100)

их хялбархан байгаа биз? Гэхдээ энэ функц даанч маш удаан ажиллах болно. бараг fib(100) буюу 100-р утгыг олох гэхэд л таны компютер хичнээн хурдтай хүчтэй байсан ч маш удаан ажиллах болно. Тухайн хэлний хамгийн их рекурс дуудах хязгаараас хэтэрвэл програм тань шууд алдаа зааж унана. Энэ алгоритм нь өөрөө экспоненциал хугацаагаар ажиллана яагаад вэ гэвэл функцийн өмнөх дуудалтуудыг алхам тутам үргэлж дахин дахин тооцоолсоор тооцооллын хэмжээ үлэмж өснө.

Тэгвэл энэ алгоритмыг хэрхэн хурдтай ажиллуулдаг болгох вэ?
Үүний тулд динамик програмчлал хэрэглэе. ДП гэдэг бол асуудлын дэд асуудлууд оновтой шийдэгдвэл асуудал бүхэлдээ оновчтой шийдэгдэнэ гэсэн зарчим дээр тулгуурласан алгоритм юм. Би буруу хэлсэн бол комментээр засч өгөөрэй ;)

Дээрхи фибоначийн алгоритм удаан ажиллаад байгаа шалтгаан нь гэвэл рекурсив дуудалтын утгандаа өмнөх олчихсон байж болох үр дүнг ерөөсөө ашиглахгүйгээр шинээр дуудалт хийгээд байгаад оршино. Энэ дутагдлыг арилгахын тулд энгийн dictionary өгөгдлийн бүтцийг ашиглаж өмнө олсон утгуудаа хадгалан ашиглах байдлаар алгоритмаа сайжруулая. Динамик програмчлалд өмнөх дэд асуудлын шийдлийг санах ойд хадгалж аваад дараа дараагийн асуудлыг шийдэхэд хэрэглэх нь хичнээн их ач холбогдолтой нь эндээс харагдах байхаа.

ДП дээрээс доош хэлбэр
dic = {}
def fib(n):
    if n<=2:
        return 1
    else:
        if n in dic:
            return dic[n]
        else:
            result = dic[n] = fib(n-1)+fib(n-2)
            return result

print fib(100)
print fib(1000)
print fib(5000)

За одоо fib(1000), fib(5000), fib(10000) гэж их тоотой дуудалт өглөө ч гэсэн програм тань нүд ирмэхийн зуур ажиллах болно.

ДП доороос дээш хэлбэрээр
dic = {}
def fib(n):
    for i in range(1,n+1):
        if i<=2:
            dic[i] = 1
        else:
            dic[i] = dic[i-1]+dic[i-2]
    return dic[n]