Ř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.


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$.

Puzzle je vyřešeno, když obsah každého vrcholu odpovídá jeho označení.
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átu
graph(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átem
solve(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]

5 komentářů:

  1. Anonymní ... (3. června 2011 3:09)

    Vyborne, este tomu najst lepsi LookUp a je to dokonale.

  2. Ivan ... (20. června 2011 16:20)

    Díky. Co myslíte tím LookUp?

  3. Anonymní ... (21. června 2011 6:31)

    No lepsi dizajn predsa. ;-)
    O trosku.

  4. Anonymní ... (2. června 2012 15:21)

    Dekuji moc krat dekuji tohle mi chybelo

  5. Anonymní ... (11. prosince 2014 2:12)

    Ahoj, mám 2 příklady na orientovaný graf v prologu ale nevím jak to napsat. Pomůžete mi?

Okomentovat