V ukázkovém příkladu se hledá nejnižší součet ve čtverci 5 × 5 polí, řešit se má matice 80 × 80 prvků. Jen pro představu je v takovém poli přibližně 2.315*10^46 různých cest. Nejkratší cestu lze najít efektivně pomocí Dijkstrova algoritmu, ale nejdříve je potřeba sestavit samotný graf, nad kterým bude algoritmus pracovat.
Pro jednoduchost ukážu řešení na příkladu v zadání. Takto vypadá naše matice:
Jednotlivé položky matice považujme za uzly a vložme mezi ně ohodnocené hrany (světle žlutá pole). Hodnota hrany je polovina součtu hodnot uzlů, které spojuje; pouze u počátečního (resp. koncového) pole se dělí dvěma jen hodnota pole uvnitř tabulky. Při průchodu a sčítání hodnot na hranách dospějeme ke stejnému součtu, jako bychom sčítali hodnoty procházených polí.
Ohodnotíme všechny uzly kladným nekonečnem, jen výchozí uzel ohodnotíme nulou. Sytě azurová pole jsou uzly, které už jsme zpracovali.
Procházíme (poslední) zpracované uzly a součet hodnoty uzlu a příslušné hrany ukládáme do následujícího uzlu vodorovným (resp. svislým) směrem, ale jen pokud je nový součet nižší, než aktuální hodnota následujícího uzlu (viz. obrázek).
Ohodnocená tabulka po průchodu grafem:
Řešení na pastebinu Ideone.
Žádné komentáře:
Okomentovat