Migrate from GitHub to SourceForge with this tool. Check out all of SourceForge's recent improvements.
Close

Home

Jindřich Bašek

Úloha PRP: přesun na šachovnici s penalizací
Vstupní data:

n = přirozené číslo představující velikost strany čtvercové šachovnice S[1..n,1..n], n>= 5
P[1..n,1..n] = množina celých kladných čísel z intervalu <1,255> ohodnocení políček šachovnice (představující penalizaci)
k = celé číslo představující počet jezdců na šachovnici S, 2n ≤ k ≤ n*(n+1)/2
Pravidla a cíl hry:

Počáteční stav je tvořen k jezdci umístěnými po řádcích v horní trojúhelníkové části šachovnice S, kterou nazveme oblast X. Každý jezdec se může na šachovnici pohybovat podle šachových pravidel (tah ve tvaru písmene L a může táhnout pouze na volné pole).

Cílem hry je převést počáteční stav na cílový, ve kterém jsou jezdci symetricky umístěni po řádcích v dolní trojúhlenikové části šachovnice S, kterou nazveme oblast Y (oblast Y je středově symetrická s oblastí X).
Úkol:

Nalézt posloupnost tahů jezdců pro dosažení cíloveho stavu tak, aby součet penalizací navštívených políček byl minimální.
Výstup algoritmu:

Číslo udávající minimální penalizaci a posloupnost tahů vedoucích z počátečního do cíloveho stavu. Tahy zapisujte ve formátu dvojice (startovní a koncová pozice jezdce v tomto tahu = odkud a kam jezdec v danem tahu táhnul).

Počáteční a cílový stav pro n=5 a k=15.

Počáteční a cílový stav pro n=5 a k=10.
Sekvenční algoritmus:

Sekvenční algoritmus je typu BB-DFS s neomezenou hloubkou stavového prostoru (při tazích jezdců mohou vznikat cykly). Hloubku prohledávání musíme omezit horní mezí (viz dále). Cena, kterou minimalizujeme, je součet penalizací použitých políček. Algoritmus končí, když je cena rovna dolní mezi a nebo když prohledá celý stavový prostor do hloubky dané horní mezí.

Těsná dolní mez není známa. Triviální dolní mez na minimální penalizaci určíme nasledujícím způsobem: pro každého jezdce z oblasti X určíme minimální počet tahů, které musí provést, aby se dostal na libovolnou pozici v oblasti Y. Následně pro každého jezdce vygenerujte všechny existující cesty s minimálním počtem tahů a ze všech těchto cest vybereme tu, která má nejmenší penalizaci. Součet těchto k minimálních penalizací tvoří odhad triviální dolní meze.

Horní mez na penalizaci, vhodnou k ořezávání stavového prostoru, stanovte jako dvojnásobek triviální dolní meze.
Paralelni algoritmus:

Paralelní algoritmus je typu PBB-DFS-V.