Soluzione Towers of Hanoi migliore di O (2^n)?

Question

C'è una soluzione per torri di Hanoi cui tempo di esecuzione è inferiore a O (2 ⁿ) dove n è il numero di dischi di muoversi? La mia soluzione richiede O (2 ⁿ) ora.

Inoltre, la soluzione di seguito è con ricorsione. Possiamo utilizzare la programmazione dinamica con il concetto di memoizzazione per risolvere questo problema in un tempo minore?

public void towersOfHanoi(
     int num, 
     MyStack<Integer> from, 
     MyStack<Integer> to, 
     MyStack<Integer> spare 
) { 
    if (num == 1) { 
     int i = from.pop(); 
     to.push(i); 
     System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName()); 
     return; 
    } 
    towersOfHanoi(num - 1, from, spare, to); 
    towersOfHanoi(1, from, to, spare); 
    towersOfHanoi(num - 1, spare, to, from); 
} 

MyStack è una versione estesa di Stack di classe in Java che aggiunge un campo name e di accesso.

Inoltre, ci sono variazioni dello stesso problema?

Answer 1

Dato che la risoluzione di Towers di Hanoi richiede sempre 2^n - 1 passaggi ... no, non si troverà un algoritmo più veloce, perché richiede O (2^n) solo per stampare i passaggi, molto meno li calcoliamo.

Answer 2

Non provo (come ha fatto Stephen), ma proverò a spiegare intuitivamente che 2^n-1 sono min: In ogni stato, ci sono solo tre possibili mosse per i dischi. Lasciate rappresentare lo stato corrente come seq ordinato (1, 1, .., 1) in modo tale che il primo numero indichi dove si trova il disco più grande, e l'ultimo numero dice dove si trova il disco più piccolo. (1, 1, .., 1) significa che tutti i dischi sono in posizione 1. Anche da (1, 1, ..1) ci sono solo due stati discendenti: (1, 1, ... 2) e (1, 1, .... 3). Da (1, 1, 2 ...) ci sono tre stati discendenti:

1. Ritornare alla (1, 1, 1 ..)
2. goto (1, 1, ..., 3)
3. goto (1, 1, ... 3, 2)

Se si continua, si otterrà il grafico per il quale i nodi sono i possibili stati e i bordi (transizioni) sono "mosse" del disco.

Si otterrà l'immagine come mostrato di seguito (se si continua, apparirà come triangolo e ai vertici sarà (1, 1, ... 1), (2, 2, ..2), (3 3, ... 3)). Il numero di passaggi è in realtà il percorso nel grafico.

Se si cammina lungo il bordo del triangolo, il numero di passaggi in 2^n-1. Tutti gli altri percorsi sono della stessa lunghezza o più lunghi.

Se si utilizza la strategia: spostare tutti i dischi tranne il più grande di inserire 3, quindi spostare i larges a posto 2, e, infine, spostare tutte le forme 3 a 2, la formula può essere concepita nel seguente modo:

f (n) =
f (n -1) // sposta tutti tranne più grande da 1 a 3
+ 1 // spostarsi più grande dal 1 al 2
+ f (n -1) // sposta tutto da 3 a 2
->
f (n) = 1+ 2 * f (n-1)

la soluzione di questa equazione ricorrente si dà il numero di passi richiesti da tale strategia (che risulta essere il numero minimo di passi)

Answer 3

La soluzione alle torri di Hanoi è ineluttabilmente 2 ⁿ. In una soluzione di programmazione dinamica, tuttavia, ciascun sottoproblema viene calcolato una sola volta e quindi il problema viene risolto combinando la prima soluzione per sottoproblemi, lo spostamento del disco corrente e la seconda soluzione per sottoproblemi.

Quindi ci sono due componenti nel generare ciascuna soluzione: allocare la memoria per la soluzione presente e quindi riempire quella memoria. L'allocazione della memoria è approssimativamente indipendente dalla dimensione della memoria allocata ed è il componente costoso. La copia di memoria è lineare nella dimensione della memoria copiata, che, sebbene veloce, è esponenziale in n come soluzione alle Torri.

Tempo = c * n + c * 2 ⁿ, dove c >> c . I.e, inizia lineare e termina esponenziale.

Link to article appearing in ACM's SIGCSE Inroads magazine (September 2012)

Answer 4

Le torri standard del problema Hanoi si occupa di 3 pioli.

Tuttavia, se abbiamo k-peg, la complessità temporale sarebbe O (2^(n/(k-2))).

ho risolto questo problema con 4 picchetti e 5 picchetti e complessità tempo determinato è O (2^(n/2)) e O (2^(n/3)) rispettivamente