Solving Tower of Hanoi dichiarative (Prolog)

Question

Il mio professore ha dato this come esempio di Prolog. È un programma che risolve l'enigma della Torre di Hanoi, in cui devi spostare una pila di dischi in un altro peg spostando un disco dopo l'altro, senza mettere un disco più grande sopra un disco più piccolo.

Ora, questo programma non mi piace. Mi è stato detto che Prolog era destinato alla programmazione dichiarativa. Non voglio programmare come risolvere il problema, voglio scrivere usando Prolog il problema è. Quindi lascia che Prolog risolva.

I miei sforzi finora sono disponibili qui sotto. Esistono due tipi di elenchi che utilizzo, una sequenza di azioni è rappresentata in questo modo: [[1,2],[3,1]]; questo sarebbe "spostare il primo disco dal peg 1 al peg 2, spostare il disco dal peg 3 al peg 1". Il mio secondo tipo di elenco è uno stato , ad esempio, se ci sono tre pioli [[1,2,3], [], []] significherebbe che ci sono tre dischi sul primo peg. I dischi più piccoli hanno numeri più piccoli, quindi la parte anteriore della lista interna è la cima di una pila.

% A sequence of actions (first argument) is a solution if it leads 
% from the begin state (second argument) to the End state (third argument). 

solution([], X, X). 

solution([[FromIdx | ToIdx] | T], Begin, End) :- 
    moved(FromIdx, ToIdx, Begin, X), 
    solution(T, X, End). 

% moved is true when Result is the resulting state after moving 
% a disk from FromIdx to ToIdx starting at state Start 

moved(FromIdx, ToIdx, Start, Result) :- 
    allowedMove(FromIdx, ToIdx, Start), 
    nth1(FromIdx, Start, [Disk|OtherDisks]), 
    nth1(ToIdx, Start, ToStack), 
    nth1(FromIdx, Result, OtherDisks), 
    nth1(ToIdx, Result, [Disk|ToStack]). 

allowedMove(FromIdx, ToIdx, State) :- 
    number(FromIdx), number(ToIdx), 
    nth1(FromIdx, State, [FromDisk|_]), 
    nth1(ToIdx, State, [ToDisk|_]), 
    ToDisk > FromDisk. 

allowedMove(_, ToIdx, State) :- nth1(ToIdx, State, []). 

Il programma di cui sopra sembra funzionare, ma è troppo lento per tutto ragionevolmente complesso. Chiedendo di risolvere il classico Torre di problema Hanoi, passando tre dischi dal primo piolo per la terza e ultima, sarebbe andata in questo modo:

?- solution(Seq, [[1,2,3], [], []], [[], [], [1,2,3]]). 

vorrei apportare alcune modifiche al programma in modo che funzioni per questa query. Come potrei fare per farlo? Durante la creazione di profili, posso vedere che lo nth1 utilizza molto tempo, dovrei liberarmene? Qualcosa che mi dà fastidio è che moved è completamente deterministico e dovrebbe avere solo un risultato. Come posso accelerare questo collo di bottiglia?

Answer 1

La soluzione Prolog ad Hanoi si trova in genere simile a questa. La soluzione scrive le mosse verso lo schermo come li incontra e non raccoglie le mosse in un elenco:

move_one(P1, P2) :- 
    format("Move disk from ~k to ~k", [P1, P2]), nl. 

move(1, P1, P2, _) :- 
    move_one(P1, P2). 
move(N, P1, P2, P3) :- 
    N > 1, 
    N1 is N - 1, 
    move(N1, P1, P3, P2), 
    move(1, P1, P2, P3), 
    move(N1, P3, P2, P1). 

hanoi(N) :- 
    move(N, left, center, right). 

Questo potrebbe essere modificato per raccogliere le mosse in una lista invece con l'aggiunta di un argomento lista in tutto e usando append/3:

move(0, _, _, _, []). 
move(N, P1, P2, P3, Moves) :- 
    N > 0, 
    N1 is N - 1, 
    move(N1, P1, P3, P2, M1), 
    append(M1, [P1-to-P2], M2), 
    move(N1, P3, P2, P1, M3), 
    append(M2, M3, Moves). 

hanoi(N, Moves) :- 
    move(N, left, center, right, Moves). 

Siamo stati in grado di fare il caso più semplice di base senza la write. Il append/3 fa il lavoro, ma è un po 'goffo. Inoltre, lo is/2 in particolare lo rende non relazionale.

Utilizzando un DCG e CLP (FD), lo append/3 può essere eliminato e può essere reso più relazionale.Ecco quello che chiamerei un primo approccio "naive", ed è anche più leggibile:

hanoi_dcg(N, Moves) :- 
    N in 0..1000, 
    phrase(move(N, left, center, right), Moves). 

move(0, _, _, _) --> []. 
move(N, P1, P2, P3) --> 
    { N #> 0, N #= N1 + 1 }, 
    move(N1, P1, P3, P2), 
    [P1-to-P2], 
    move(N1, P3, P2, P1). 

Questo si traduce in:

| ?- hanoi_dcg(3, Moves). 

Moves = [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center] ? a 

no 
| ?- hanoi_dcg(N, [left-to-center,left-to-right,center-to-right,left-to-center,right-to-left,right-to-center,left-to-center]). 

N = 3 ? ; 

(205 ms) no 
| ?- 

Anche se è relazionale, esso ha un paio di problemi:

• punti di scelta "inutile in entrambe le direzioni" questioni
• terminazione a meno vincolati con qualcosa di simile N in 0..1000

Sento che c'è un modo per aggirare questi due problemi, ma non l'abbiamo ancora risolto. (Sono sicuro che se alcuni Prolog più intelligenti di me, come @mat, @false, o @repeat vedono questo, avranno una buona risposta subito.)

Answer 2

Ho guardato la tua soluzione ed ecco alcuni pensavo di averlo:

Quando si move, quello che stai facendo è prendere da una torre e metterne un altro. Esiste un predicato SWI che sostituisce un elemento in un elenco, select/4. Ma vuoi anche avere l'indice dove lo hai sostituito. quindi riscrivilo un po 'e chiamalo switch_nth1, perché non deve più fare molto con select.

% switch_nth1(Element, FromList, Replacement, ToList, Index1) 
switch_nth1(Elem, [Elem|L], Repl, [Repl|L], 1). 
switch_nth1(Elem, [A|B], D, [A|E], M) :- 
    switch_nth1(Elem, B, D, E, N), 
    M is N+1. 

Dal momento che stiamo operando su lista di liste, avremo bisogno di due switch_nth1 chiamate: uno per sostituire la Torre prendiamo da, e uno di mettere sulla nuova torre.

Un predicato move potrebbe apparire come questo (scusate ho modificato un po 'gli argomenti). (Dovrebbe essere chiamato allowed_move perché non esegue mosse che non sono consentite).

move((FromX - ToX), BeginState, NewState):- 
    % take a disk from one tower 
    switch_nth1([Disk| FromTowerRest], BeginState, FromTowerRest, DiskMissing, FromX), 
    % put the disk on another tower. 
    switch_nth1(ToTower, DiskMissing, [Disk|ToTower], NewState, ToX), 

    % there are two ways how the ToTower can look like: 
    (ToTower = [];    % it's empty 
    ToTower = [DiskBelow | _], % it already has some elements on it. 
    DiskBelow > Disk). 

se si collega dentro il vostro solution si tristemente incorrere in alcuni problemi di terminazione, dal momento che nessuno ha detto che uno Stato che già è stato raggiunto non dovrebbe essere un passo proprio sulla strada. Quindi, dobbiamo tenere traccia di dove eravamo già e non consentire la continuazione quando viene raggiunto uno stato conosciuto.

solution(A,B,C):-solution_(A,B,C,[B]). 

solution_([], X, X,_). 
solution_([Move | R], BeginState, EndState, KnownStates):- 
    move(Move, BeginState, IntermediateState), 
    \+ memberchk(IntermediateState, KnownStates), % don't go further, we've been here. 
    solution_(R, IntermediateState, EndState, [IntermediateState | KnownStates]). 

Detto questo, questa soluzione è ancora molto imperativo - non ci dovrebbero essere le soluzioni più bello là fuori, dove realmente sfruttare recursion.

Answer 3

Per "dichiarativo" presumo tu intenda qualcosa vicino al vecchio slogan di "in Prolog, scrivere una domanda è avere la risposta". Lascia che Prolog scopra la risposta invece di me semplicemente codificando in Prolog la risposta che dovevo scoprire da solo.

Basta definire un predicato legal_move, indicando la condizione iniziale e finale e l'esecuzione di una ricerca standard di qualsiasi varietà, porta a soluzione estremamente molto inefficiente che fare marcia indietro un bel po '.

Fare un computer per ottenere una soluzione efficiente qui mi sembra un problema molto difficile.Per noi umani, però, con un po 'di pensiero la soluzione è ovvia, tagliando anche la ridondanza, facendo qualsiasi paragone e controllando la legalità delle posizioni completamente inutili - la soluzione è efficiente e ogni mossa è legale da costruzione .

Se possiamo spostare N = M + K dischi, possiamo passare M di loro lo stesso - gli altri due pioli sono vuote, e abbiamo finta inferiori K dischi non ci sono.

Ma dopo aver spostato i M dischi, ci troviamo di fronte con il restante K. Ovunque i M dischi sono andati, non siamo in grado di spostare qualsiasi della K lì, perché per costruzione dischi K sono tutti "più grande" rispetto a qualsiasi della M ("più grande" semplicemente perché erano sotto di loro inizialmente sulla fonte peg).

Ma il terzo piolo è vuoto. È facile spostare un disco lì. Non sarebbe solo peachy se K fosse uguale a 1? Avendo spostato il restante K = 1 disco per il vuoto bersaglio piolo, abbiamo nuovamente far finta non c'è (perché è il "grande") e muovere M dischi su di esso.

L'aggiunta vitale: dal M dischi devono essere spostati bersaglio nella seconda fase, inizialmente essi devono essere spostati in il ricambio.

Tutto questo significa che, se sapevamo come muoverci M dischi, potremmo facilmente spostare M + 1. Induzione, ricorsione, DONE!

Se già sapevi tutto questo, scusa per il carico di verbosità. Il codice:

hanoi(Disks, Moves):- 
    phrase(hanoi(Disks, [source,target,spare]), Moves). 

hanoi(Disks, [S,T,R]) --> 
    { append(M, [One], Disks) }, 
    hanoi(M, [S,R,T]), 
    [ moving(One, from(S), to(T)) ], 
    hanoi(M, [R,T,S]). 
hanoi([], _) --> [ ]. 

Testing:

4 - Hanoi ([1,2,3], _X), maplist (writeln, _X)?.
mobile (1, da (sorgente), a (target))
mobile (2, da (sorgente), a (ricambio))
mobile (1, da (target), a (ricambio))
spostamento (3, da (sorgente), a (target))
mobile (1, da (ricambio), a (sorgente))
mobile (2, da (ricambio), a (target))
movimento (1, da (fonte), a (obiettivo)) ;
false.