Newsgroup: it.hobby.enigmi
Titolo: Torre di Hanoi evoluta

Tutti qui conoscono il giochino della Torre di Hanoi (base con 3 pioli, una
serie di dischi concentrici, ecc.), e relativa tecnica di soluzione (un po'
di tempo fa, ad un mio post, Dario Uri mi aveva illustrato un metodo molto
efficace).
Ma come mi comporto se ho piu' di tre pioli? Con n dischi ed m pioli (m>=n),
la soluzione e' banale (sposto un disco a piolo, e poi ricompongo il cono),
ma negli altri casi (m<n, m>3) che faccio?
Bye by Massimo 8-]


Se il problema e` quello di spostare una torre da un piolo all'altro, una
risposta da matematico sarebbe: "mi riconduco al caso precedente" :-)
Cioe`: ho un algoritmo che mi permette di spostare una torre di altezza
qualsiasi avendo 3 pioli, se ne ho di piu` ne uso solo 3 e sono a posto.
Se invece, il tuo problema e` trovare il numero minimo di mosse, allora la cosa
cambia. Da un punto di vista AI e` un problema di pianificazione, credo che si
possa semplicemente estendere il programma che risolve il problema con 3 pioli.
Ciao ciao,
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli

 possa semplicemente estendere il programma che risolve il problema con 3
pioli.
definire "semplicemente" , please... ;)
Silv:o)


Hai ragione, scusa.
Metto in fondo il programma Prolog che fornisce la soluzione ottima.
Mi vergogno profondamente di averlo scritto in una versione cosi` naif e cosi`
inefficiente! Puo` essere migliorato parecchio (scusate, ma adesso devo
lavorare!!!)
Il programma viene invocato cosi`:
minmosse(Numero di mosse minimo in ingresso,Numero minimo trovato,Stato
Iniziale, StatoFinale).
Lo stato viene rappresentato come una lista; ciascun elemento della lista e` un
piolo. In ogni piolo c'e` una lista di dischi; la lista vuota [] rappresenta un
piolo vuoto ;-)
Esempio:
[eclipse 2]: minmosse(3,N,[[1,2,3],[],[]],[[],[],[1,2,3]]).
3
4
5
6
7
8
N = [1->3, 2->3, 2->1, 1->3, 3->2, 1->2, 1->3]
Yes (0.08s cpu)
La lista di mosse va letta in senso inverso ... si comincia a muovere il disco
di sopra dal piolo 1 al 3, poi dal piolo 1 al 2, ecc.
Un'esecuzione con 4 pioli:
minmosse(3, M, [[1, 2, 3, 4], [], [], []], [[], [], [], [1, 2, 3, 4]]).
3
4
5
6
7
8
9
10
M = [1->4, 3->4, 3->1, 2->4, 1->4, 1->2, 2->3, 1->3, 1->2]
Yes (17.37s cpu)
(Vergognosamente lento ...)
Ciao ciao,
Marco
=============================================================================
:- lib(fd).
% hanoi(MosseRimaste,MosseIn,MosseOut,StatoIniz,StatoFin)
hanoi(0,_,_,_,_):- !,fail.
hanoi(N,_,_,Sin,Sfin) :-
    conta_differenze(Sin,Sfin,Diff),
    Diff/2 >N,!,fail.
hanoi(_,M,M,S,S).
hanoi(N,MosseIn,MosseOut,StatoIniz,StatoFin):-
    mossa(M,StatoIniz,StatoTemp),
    N1 is N-1,
    hanoi(N1,[M|MosseIn],MosseOut,StatoTemp,StatoFin).
mossa(From->To,StatoIniz,StatoFin) :-
    on_top(Top,StatoTemp,StatoIniz,From),
    on_top(Top,StatoTemp,StatoFin,To),
    From \= To.
on_top(Top,[[]|T],[[Top]|T],1). % puoi metterlo in un piolo vuoto
on_top(Top,[[H|Stack]|T],[[Top,H|Stack]|T],1) :-
    Top<H.
on_top(Top,[Stack|T],[Stack|R],N) :-
    on_top(Top,T,R,N1),
    N is N1+1.
minmosse(N,M,StatoIn,StatoFin) :-
    writeln(N),
    hanoi(N,[],M,StatoIn,StatoFin),!.
minmosse(N,M,StatoIn,StatoFin) :-
    N1 is N+1,
    minmosse(N1,M,StatoIn,StatoFin).
conta_differenze([],[],0).
conta_differenze([H|T],[H|T1],N) :- !,
    conta_differenze(T,T1,N).
conta_differenze([_|T],[_|T1],N) :-
    conta_differenze(T,T1,N1), % Qui si puo` fare meglio...
    N is N1+1.
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli

 Metto in fondo il programma Prolog che fornisce la soluzione ottima.
Purtroppo non conosco assolutamente il prolog, e pur avendo cercato di
comprendere la logica del del programma, non ci sono proprio riuscito.
Potresti dare una descrizione verbale dell'algoritmo?
La variante classica è formalizzabile in poche parole (è proprio quello il
fascino della ricorsione: a volte brucia risorse esponenziali, ma con molta
eleganza). Per questa variante non sono riuscito a trovare una formulazione
valida, e tutti i tentativi di generalizzazione sono miseramente falliti :((
Ciao, Silv:o)

Silvio Sergio, giustamente, chiede:

Certo, mi scuso per la brevita` del mio post precedente, ma ieri ero davvero
impegnato :-(
Concordo perfettamente sul fatto che la ricorsione e` meravigliosa: il Prolog e`
basato proprio su questo, infatti in Prolog non esiste iterazione, ma tutto deve
essere fatto ricorsivamente. 
Comunque passo alla descrizione dell'algoritmo. E` un algoritmo di Intelligenza
Artificiale, quindi si suppone che chi lo ha scritto non conosca gia` la
soluzione, ma si aspetta che sia l'algoritmo a trovarla. Non e` quindi una
generalizzazione dell'algoritmo che dice: "sappiamo come spostare una torre di
altezza 1. Se sappiamo come spostare una torre di altezza N allora sappiamo
spostarne una di altezza N+1"
L'algoritmo in questione parte da uno stato, genera una delle possibili mosse e
si trova quindi in un altro stato. Se lo stato ottenuto e` quello finale, bene,
altrimenti prova ad aggiungere un'altra mossa e cosi` via. Ogni volta che viene
aggiunta una mossa viene inoltre inserito un punto di scelta (perche' ci
potrebbero essere altre mosse possibili). Questo viene fatto automaticamente dal
Prolog. Se non si arriva ad una soluzione, si fa backtracking all'ultimo punto
di scelta inserito. Viene, in pratica, esplorato un albero che rappresenta
l'insieme delle successioni di mosse che partono dallo stato iniziale.
L'esplorazione dell'albero e` limitata in profondita`, altrimenti rischieremmo
di generare una successione infinita di mosse, che porterebbe ad un loop. Si
cercano quindi prima le successioni di lunghezza 1, se non si trova soluzione si
passa alla lunghezza 2, ecc. In questo modo siamo sicuri di ottenere l'ottimo.
Se facessimo solo cosi`, sarebbe una ricerca un po' "forza bruta", che
risulterebbe inapplicabile anche per problemi piccoli. Viene quindi inserita
un'euristica per "immaginare" quante mosse mancano ancora alla soluzione. Se
siamo limitati a soluzioni di lunghezza 5, stiamo costruendo una soluzione che,
per ora, ha tre mosse e per arrivare alla soluzione finale dobbiamo spostare 3
dischi, e` inutile sperare di farcela: in 2 mosse non si spostano 3 dischi!
Ora, l'euristica che ho presentato nel mio post precedente era molto naif:
contava il numero di pioli identici nelle 2 situazioni che vogliamo confrontare.
Dicevo quindi: il numero di mosse che mancano e` maggiore del numero di pioli
che non sono identici diviso per 2. Per questo il programma era cosi` lento. Ad
esempio, per passare dalla situazione:
 |	|	|	|
 1	|	|	|
 2	5	|	|
 3	6	4	7
=========================
alla situazione:
 |	|	|	1
 |	|	|	2
 |	5	|	3
 |	6	4	7
=========================
la mia euristica dice: "i pioli diversi sono il primo ed il quarto, quindi il
numero di mosse necessario e` senz'altro superiore a 1". Chiaramente, si puo`
fare di meglio.
A questo punto vi sottometto un quesito: Fornire un'euristica migliore. 
Tenete presente che l'euristica deve essere "ottimistica", nel senso che non
deve mai fornire un valore piu` grande del numero di mosse minimo che e`
_davvero_ necessario.


 alla soluzione.
Già. Il problema di potare gli alberi di ricerca è cruciale, così come
l'efficacia delle euristiche per la valutazione della posizione. Penso ad
esempio agli scacchi. Appena ho un po' di tempo vedrò di dedicarmi alla
ricerca di euristiche valide.
Per ora vorrei abbandonare l'AI e cercare qualche algoritmo simile all'Hanoy
classico.
Parto con una considerazione:
E' ovvio che prima o poi dovremo spostare il primo disco dal piolo origine a
quello destinazione. In quel momento tutti gli altri dischi dovranno stare
nei restanti n-2 pioli. A quel punto non possiamo far di meglio che ripetere
le mosse al conrtrario e riaccumulare tutta la catasta sul piolo di
destinazione. Se ci fosse un modo per riaccatastare in meno mosse di quelle
usate per liberare il disco grande, allora avremmo potuto usarlo - al
contrario - nella prima fase!
Quindi a mio avviso il problema si riduce ad una ricerca della miglior
sequenza che liberi un piolo da una catasta, lasciando libero alla fine
anche un'altro piolo prefissato.
Faccio un esempio: 5 pioli e 10 dischi.
P1:9876543210-
P2:-----------
P3:-----------
P4:-----------
P5:-----------
il primo passo consiste nel liberare il disco 9, terminando con P5 libero da
dischi
P1:9----------
P2:?????------
P3:?????------
P4:?????------
P5:-----------
A questo punto, alla maniera dell'Hanoy classico, spostiamo il 9 e
riaccatastiamo tutto su P5. Ricapitolando
A: spostiamo m-1 dischi lasciando libero il piolo target
B: spostiamo il disco maggiore sul piolo target
C: riaccatastiamo le m-1 pedine (simmetrica di A)
La differenza, non da poco, è che l'operazione A (e la sua simmetrica C)
*non è* una versione
ridotta del problema di partenza. Quindi, apparentemente, niente ricorsione.
Silv:o)


In un attimo di panico, ho elaborato un piccolo algoritmo, che implica anche
la ricorsione classica. Spero solo abbia qualche barlume di lucidita' 8-)
Torre di n dischi e m pioli:
Soluzione minima
2(n-1)+1 mosse, se m >= n+1. Infatti, sposto n-1 dischi su un piolo diverso
ciascuno; l'n-simo disco viene messo sul piolo di destinazione e con altre
n-1 mosse ricostruisco la torre.
Soluzione massima
(2^n)-1 mosse, con m = 3 (e' la soluzione classica)
Soluzione intermedia
L'idea e' di dividere la torre originaria in piu' sotto-torri, scaturita dal
fatto che spostare due torri da n/2 dischi comporta meno mosse che spostarne
una da n dischi.
Quindi:
- divido la torre in m-2 sezioni. Dato che difficilmente le sezioni avranno
lo stesso numero di dischi, faccio in modo che le sezioni con piu' dischi
siano quelle vicino alla base;
- sposto le m-2 sezioni, ciascuna su un piolo diverso, mettendo l'ultima sul
piolo di destinazione;
- a questo punto, ricostruisco la torre rimettendo le sezioni a posto
nell'ordine giusto.
Ascii-art:
   1      I      I      I      I
___2___   I      I      I      I
   3      I      I      I      I
   4      I      I      I      I
___5___   I      I      I      I
   6      I      I      I      I
   7      I      I      I      I
   8      I      I      I      I
-----------------------------------
          I      I      I      I
          I      I      I      I
   3      I      I      I      I
   4      I      I      I      I
___5___   I      I      I      I
   6      I      I      I      I
   7      1      I      I      I
   8      2      I      I      I
-----------------------------------
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   6      I      3      I      I
   7      1      4      I      I
   8      2      5      I      I
-----------------------------------
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      I
   I      I      3      I      6
   I      1      4      I      7
   I      2      5      I      8
-----------------------------------
   I      I      I      I      I
   I      I      I      I      I
   I      I      I      I      3
   I      I      I      I      4
   I      I      I      I      5
   I      I      I      I      6
   I      1      I      I      7
   I      2      I      I      8
-----------------------------------
   I      I      I      I      1
   I      I      I      I      2
   I      I      I      I      3
   I      I      I      I      4
   I      I      I      I      5
   I      I      I      I      6
   I      1      I      I      7
   I      2      I      I      8
-----------------------------------
Bye by Massimo 8-]
P.S. Ora il casino e' tradurre l'algoritmo dalla descrizione a parole ad una
descrizione piu' formale, e da qui in un programma


Questa soluzione e` un caso particolare della soluzione proposta da Silvio, in
cui decidi un modo per dividere la torre iniziale, mentre lui l'aveva lasciata
non descritta. Non e` comunque una soluzione ricorsiva, nel senso che per
effettuare la prima mossa ti rifai all'algoritmo classico (che usa un solo piolo
di "appoggio"). E` solo nella prima mossa che usi tutti i pioli a disposizione.
Io credo, comunque, che sia una soluzione molto vicino a quella ottima, e ci
fornisce quindi un'ottima euristica nel programma di IA. La formula per
calcolare il numero di mosse necessario dovrebbe essere piu` o meno questa,
nell'ipotesi semplificativa che n sia divisibile per m-2:
2*(m-2)*(2^(n/(m-2))-1)
infatti spostiamo 2 volte n-2 alberi di altezza n/(m-2).
Credo si possa fare qualcosa di meglio: quando "scomponiamo" la torre, abbiamo a
disposizione piu` pioli vuoti nelle prime mosse, per cui dovrebbe essere piu`
conveniente avere le sezioni piu` alte con tanti dischi e quelle piu` basse con
meno dischi. La stessa cosa accade quando "ricomponiamo" la torre: nelle ultime
fasi (quando spostiamo i dischi piu` piccoli) abbiamo a disposizione molti pioli
vuoti, per cui dovrebbe essere un'operazione piu` semplice e quindi anche qui ci
conviene avere i settori con i dischi piccoli piu` grossi.
Credo proprio che una buona soluzione (se non proprio la soluzione ottima) si
ottenga con una opportuna ripartizione della torre nel primo step.
Se ho tempo, piu` tardi scrivo un programma (in Prolog, amo troppo questo
linguaggio).


 ottenga con una opportuna ripartizione della torre nel primo step.
La cosa di cui non sono affatto sicuro è che la cosa migliore sia trasferire
una torre in una serie di altre torri ancora formate da elementi contigui.
Mi spiego: chi ci assicura che per l'esempio descritto prima non sia meglio
passare per
P1:------------
P2:73----------
P3:862---------
P4:541---------
P5:A9----------
se così fosse, non si potrebbe proseguire ricorsivamente, mentre se l'ottimo
è quello proposto da Massimo, oppure questo:
P1:A-----------
P2:987---------
P5:654---------
P4:321---------
P5:------------
allora la ricorsione funzionerebbe, perchè si tratterebbe di spostare pile o
cime di pile da un piolo ad un altro.
Silv:o)

 fornisce quindi un'ottima euristica nel programma di IA.
Come non detto, e` stata una svista ... 
L'euristica deve essere ottimistica e questa non lo e` :-(
Ciao ciao,
Marco
-- 
Marco Gavanelli
DIF - Ferrara University
IC-Parc visiting student
William Penney Laboratory - Imperial College
Exhibition Road
London SW7 2AZ 
FAX: 
+44 20 7594 8432
 
Tel: 
+44 20 7594 8190
http://www.ing.unife.it/docenti/MarcoGavanelli

 spostarne una da n dischi.
Ho implementato l'algoritmo, combinando la tua idea con la mia.
In pratica divido la torre di partenza in m-2 pezzi escludendo la base, e li
sistemo nei pioli diversi dal piolo target. Poi sposto il disco di base sul
piolo target e rifaccio tutto al contrario. Se ci sono solo tre pioli
(origine, intermedio e destinazione) utilizzo l'Hanoy classico. Appena ho
tempo analizzo la complessità.
Solito esempio: 5 pioli e 10 dischi.
P1:9876543210-
P2:-----------
P3:-----------
P4:-----------
P5:-----------
il primo passo consiste nel liberare il disco 9, terminando con P5 libero da
dischi. Per riempire P4 uso l'Hanoy classico, perché a quel punto ho solo 3
pioli (1,4,5) a disposizione
P1:9----------
P2:012------
P3:345------
P4:678------
P5:-----------
poi sposto il 9 e procedo al contrario: Hanoy classico per svuotare P4, 4
pioli a disposizione per svuotare P3, 5 per riversare P2 su P5.
ciao, Silv:o)


Un mito! Cio significa che anche un prodotto del mio fertile cervelluzzo
puo' dare risultati positivi! 8-)
Bye by Massimo 8-]