wake-up-neo.com

Komplexität für Türme von Hanoi?

Ich habe kürzlich das Problem der Türme von Hanoi gelöst. Ich habe eine "Divide and Conquer" -Strategie verwendet, um dieses Problem zu lösen. Ich teilte das Hauptproblem in drei kleinere Unterprobleme auf, und es wurden folgende Wiederholungen erzeugt.

T (n) = 2T (n-1) + 1

Das zu lösen führt zu

O (2 ^ n) [exponentielle Zeit]

Dann habe ich versucht, die Memo-Technik zu verwenden, um das Problem zu lösen, aber auch hier war die räumliche Komplexität exponentiell und der Speicherplatz war bald erschöpft, und das Problem war für größere n immer noch unlösbar.

Gibt es eine Möglichkeit, das Problem in weniger als exponentieller Zeit zu lösen? Was ist die beste Zeit, in der das Problem gelöst werden kann?

11
user1581106

Es hängt davon ab, was Sie mit "gelöst" meinen. Das Problem des Turms von Hanoi mit 3 Stiften und n-Datenträgern erfordert 2**n - 1-Schritte, um zu lösen. Wenn Sie also die Züge auflisten möchten, können Sie offensichtlich nichts besser als O(2**n) tun, da das Auflisten von k-Dingen O(k) ist. 

Wenn Sie dagegen nur die Anzahl der erforderlichen Züge wissen möchten (ohne sie aufzählen), ist die Berechnung von 2**n - 1 eine viel schnellere Operation.

Erwähnenswert ist auch, dass die Aufzählung der Bewegungen iterativ mit der Komplexität von O(n) space wie folgt durchgeführt werden kann (disk1 ist die kleinste Festplatte):

while true:
    if n is even:
        move disk1 one peg left (first peg wraps around to last peg)
    else:
        move disk1 one peg right (last peg wraps around to first peg)

    if done:
        break
    else:
        make the only legal move not involving disk1
10
verdesmarald

Sie können die Wiederholung lösen und ein geschlossenes Formular erhalten.

T (n) = 2 · T (n - 1) + 1

T (n) = 2 * (2 * T(n-2) + 1) + 1

T (n) = (2 ^ 2) * T(n-2) + 2 ^ 1 + 2 ^ 0

T (n) = (2 ^ k) * T(n-k) + 2 ^ (k-1) + 2 ^ (k-2) + ... + 2 ^ 0

Löst man dies, kommt das Geschlossene heraus zu sein

T (n) = (2 ^ n) - 1 mit T(0) = 0

Verwenden Sie nun die Potenzierung durch Quadrieren.

11
sukunrt

Leider ist es nicht möglich, dieses Problem in kürzerer Zeit zu lösen, da die Anzahl der Bewegungen, die erforderlich sind, um die Position aller Hanoi-Türme zu ändern, exponentiell ist .. Die beste Lösung ist also linear nach der Anzahl der Schritte O (T), also der Anzahl Schwanzlösung ist exponentiell O (2 ^ n)

3
Gloomcore

Es hängt etwas davon ab, welche Art von Darstellung Sie akzeptieren. Stellen Sie sich die folgende Darstellung vor:

OneMove
    from : integral
    to   : integral

Solution
    step_one   : optional reference to Solution
    step_two   : OneMove
    step_three : optional reference to Solution

Eine solche Darstellung kann tatsächlich in linearer Komplexität erstellt werden, da viel Wiederholung involviert ist.

Ich habe es gerade ausprobiert, eine solche Lösung für Höhe 64 zu bauen, dauerte weniger als eine Millisekunde. Es dauert natürlich immer noch einen Schritt 2n-1 Schritte.

Sie haben keine Sprache angegeben, aber wenn Sie Code in C++ benötigen, löschen Sie eine Zeile.

0
sp2danny

Es gibt genau 2 ^ n-1-Züge, also können wir für die Auflistung alles besser machen als die Komplexität von O (2 ^ n).

Die Aufzählung der erforderlichen Züge ist in O(1) möglich (naja, O (log n), wenn Sie Ganzzahlen beliebiger Größe nehmen):

(define (fbs n i) (if (even? n) (fbs (/ n 2) (+ i 1)) i))

(define (fb n) (fbs n 1))

(define (hanois n i m) 
  (
    cond 
    ((= i m) "DONE")
    (else 
          (define k (fb i))
          (print "move disk " k " " (if (even? (+ n k)) "left" "right"))
          (hanois n (+ 1 i) m))))

(define (hanoi n) (hanois n 1 (expt 2 n)))

[Planen]

Beachten Sie, dass dieser Algorithmus aufgrund von Arithmetik einen Overhead von log n hat (und der Algorithmus fb die Position des niedrigstwertigen gesetzten Bits ermittelt). Jede naive Lösung, die ein beliebiges Inkrement/Dekrement eines Zählers beinhaltet, hat den gleichen Overhead.

0
masterxilo