Řešení hlavonamů v Prologu
Tato práce vznikla jako součást zápočtového programu na předmětu Neprocedurální programování, MFF UK. Jedná se o řešení konkrétního druhu hlavolamu v programovacím jazyce Prolog.
Ukázka: čirou náhodou jsem na internetu našel flash hru (výše), která přesně odpovídá popisovanému problému (autorem je Douglas Ensley, FlashAndMath.com). Do stejné kategorie hlavolamů patří např. Patnáctka.
Posouvací puzzle na obecném grafu
Popis problému
Mějme neorientovaný graf na n vrcholech, každý jeho vrchol je označen číslem z $[0, n-1]$ a zároveň obsahuje číslo z $[0, n-1]$. Vrcholu obsahujícímu $0$ říkejme "prázdný" vrchol. Čísla se posouvají mezi vrcholy s použitím prázdného vrcholu, tj. obsahy vrcholů $U$ a $V$ můžeme prohodit, pokud je mezi nimi hrana a jeden z nich obsahuje $0$.
Ukázka: čirou náhodou jsem na internetu našel flash hru (výše), která přesně odpovídá popisovanému problému (autorem je Douglas Ensley, FlashAndMath.com). Do stejné kategorie hlavolamů patří např. Patnáctka.
Poznatky Wilsona (1974)
- řešení může existovat pouze pro vrcholově 2-souvislé grafy (nemá smysl zkoumat např. stromy)
- obecně neřešitelné pro graf theta0 a kružnice
- bipartitní graf (např. mřížka) - řešitelné pouze pro sudé permutace, kterých je polovina
- v ostatních případech řešitelné vždy
Algoritmus řešení
Řešíme postupným zkoušením všech možností, ovšem pouze do stanovené hloubky. V každém kroku vybíráme další krok prioritně dle heuristiky.Heuristika
Definujme domácí vzdálenost vrcholu $v$ jako délku nejkratší cesty od označení $v$ do obsahu $v$, tj, nejmenší počet tahů pro posun "domů". Definujme rozladěnost grafu jako součet domácích vzdáleností přes všechny vrcholy. Puzzle je vyřešené, jakmile rozladěnost klesne na 0. Pokud z vrcholu obsahujícího $0$ máme více možností tahu, vybíráme z nich prioritně podle vlivu na rozladěnost grafu. Nejdříve ty, které ji zmenší, pak ty, co ji nezmění, nakonec ty, co ji zvětší.Poznámky k mé implementaci
- Pro hledání nejkratších cest používám Floyd-Warshallův algoritmus.
- Pro seřazení vrcholů dle priority používám Insertion sort.
- Nedovoluji v řešení cykly délky 2 (Např. když hledáme řešení dlouhé do 10 kroků a řešením je [1,2,3,4], potom [1,2,1,2,3,4] nevrátím, ačkoli to je řešení a má do 10 kroků.
Zdrojový kód v Prologu
Stručná dokumentace k programu
Vstup
Vstupní graf může být definován kdekoli v souboru s programem použitím predikátugraph(Název, g(V, E)).Název je název grafu, pomoci kterého k němu budeme přistupovat V značí seznam vrcholů ve tvaru
[označení-obsah, označení-obsah, ...]E značí seznam hran ve tvaru
[e(označení, označení), e(označení, označení), ...]
Ukázka
graph(ctverec, g( [0-1, 1-2, 2-3, 3-0], [e(0,1), e(1,2), e(2,3), e(3, 0)] ) ).Což znamena takovýto graf
Spuštění výpočtu
Výpočet se spustí predikátemsolve(Název, Max-tahů).
- Název je název grafu v predikátu "graph"
- Max-tahů je horní hranice pro počet tahů ve výstupních řešeních.
Výstup
Výstupem programu jsou všechny posloupnosti tahů do stanovené délky řešící hlavolam. Jsou ve tvaru[vrchol, vrchol, vrchol, ...]vrchol je označení vrcholu, který si v daném kroku prohazuje obsah s nulovým vrcholem. Tahy jsou uspořádány zleva. Pokud vám dané řešení nevyhovuje, vygenerujte si další zmáčknutím ";". Pro náš výše uvedený graf je řešením toto
[2, 1, 0]Stejně jako toto
[0, 1, 2, 3, 0, 1, 2, 3, 0]
Již vložené vsupy
Pro účely testování jsem do souboru přepsal některé grafy z výše uvedené URL a je možné se na ně dotazovat. Jsou to: graph1, graph3, graph5, graph7, graph9, graph11, graph17, graph30. Vyzkoušejte např. solve(graph1, 8).Nejkratší řešení hlavolamů výše
Zadal jsem některé hlavolamy ze výše uvedené hry do programu a toto je výstup. Pokud chcete, můžete zadat zbytek a vypočítat si další hlavolamy, Patnáctky apod.Číslo | Řešení |
---|---|
1 | [2,4,3,2,1,0], [2,3,4,2,1,0], [1,2,4,3,2,0], [1,2,3,4,2,0] |
3 | [4,3,0,2,1,0], [4,3,0,1,2,0], [3,4,0,2,1,0], [3,4,0,1,2,0], [2,1,0,4,3,0], [2,1,0,3,4,0], [1,2,0,4,3,0], [1,2,0,3,4,0] |
5 | [3,2,1,0,3,4,1,0], [1,4,3,0,1,2,3,0] |
7 | [5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0], |
9 | [1,5,2,3,4,5,6,0] |
11 | [5,4,1,2,5,4,1,0], [5,2,1,4,5,2,1,0], [1,4,5,2,1,4,5,0], [1,2,5,4,1,2,5,0] |
17 | [1,2,5,4,3,2,1,0,5,4,3,2,1,0] |
30 | [7,6,3,2,7,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,3,2,7,0] |
Vyborne, este tomu najst lepsi LookUp a je to dokonale.
Díky. Co myslíte tím LookUp?
No lepsi dizajn predsa. ;-)
O trosku.
Dekuji moc krat dekuji tohle mi chybelo
Ahoj, mám 2 příklady na orientovaný graf v prologu ale nevím jak to napsat. Pomůžete mi?