Linkek
Programozási ismeretek
Alapoktól a speciálisig...
Dinamikus programozás
Rekurzió és táblázat
ELTE dinamikus programozás:
„A dinamikus programozás elnevezés egy probléma-megoldási módszert jelöl. A módszer lényege, hogy a kiindulási problémát részproblémákra bontjuk és a részproblémák megoldásaival fejezzük ki a megoldást. Bár a megoldást rekurzívan fejezzük ki, azonban a tényleges kiszámítás nem rekurzív módon, hanem táblázat-kitöltéssel történik. Ez a módszer hatékony algoritmust eredményez számos fontos probléma megoldására.” (forrás)
MINIMÁLIS KÖLTSÉGŰ ÚT - A feladat szövege
A feladat forrása: geeksforgeeks.org (Min Cost Path | DP-6)
MINIMÁLIS KÖLTSÉGŰ ÚT - R E K U R Z I Ó - Python példa (letöltés: dinamikusprogramozas_koltseg_rekurzioval.py)
Ez a megoldás újra és újra kiszámolja ugyanazokat a részproblémákat. Sok olyan csomópont van, amely többször is feldolgozásra kerül. Ennek a rekurzív megoldásnak az „időbonyolultsága” exponenciális, és rettenetesen lassú.
MINIMÁLIS KÖLTSÉGŰ ÚT - T Á B L Á Z A T - Python példa (letöltés: dinamikusprogramozas_koltseg_tablazattal.py)