13

私は最近、ハノイの塔の問題を解決していました。私はこの問題を解決するために「分割統治」戦略を使用しました。メインの問題を3つの小さなサブの問題に分割したため、次の再発が発生しました。

T（n）= 2T（n-1）+1

これを解決すると、

O（2 ^ n）[指数時間]

次に、メモ化手法を使用してそれを解決しようとしましたが、ここでもスペースの複雑さが指数関数的であり、ヒープスペースがすぐに使い果たされ、nが大きい場合でも問題は解決できませんでした。

指数関数的な時間未満で問題を解決する方法はありますか？問題を解決できる最適な時期はいつですか。

4

5 に答える 5

15

それはあなたが「解決した」とはどういう意味かによります。3つのペグとnディスクを使用するハノイの塔の問題は2**n - 1解決するために動きが必要です。したがって、動きを列挙したい場合は、物事をO(2**n)列挙するよりも明らかにうまくいくことはできません。kO(k)

一方、必要な移動数を（列挙せずに）知りたいだけの場合は、計算2**n - 1がはるかに高速な操作になります。

また、移動の列挙は、次のようにO(n)スペースの複雑さを繰り返して実行できます（disk1最小のディスクです）。

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
于 2012-09-12T07:38:24.783 に答える
14

漸化式を解いて閉じた形を得ることができます。

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（nk）+ 2 ^（k-1）+ 2 ^（k-2）+ ... + 2 ^ 0

これを解決することで、クローズドフロムが出てきます

T（n）=（2 ^ n）-1（T（0）= 0）

次に、二乗による指数を使用します。

于 2012-09-12T07:39:42.710 に答える
3

残念ながら、すべてのハノイの塔の位置を変更するために必要な移動の数は指数関数的であるため、この問題を短時間で解決することは不可能です。したがって、最良の解はステップ数O（T）に応じて線形であるため、テール数の解は指数関数O（2 ^ n）になります。

于 2012-09-12T08:40:30.043 に答える
0

正確に2^n-1の動きがあるので、それらすべてをリストするために、O（2 ^ n）時間計算量よりもうまくいくことはできません。

必要な移動の列挙は、O（1）（任意のサイズの整数を取る場合はO（log n））スペースで可能です。

(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)))

[図式]

このアルゴリズムには、算術演算（およびfb最下位セットビットの位置を検出するアルゴリズム）のためにlognのオーバーヘッドがあることに注意してください。カウンターでのあらゆる種類のインクリメント/デクリメントを含む単純なソリューションでも、同じオーバーヘッドが発生します。

于 2017-10-17T11:57:26.473 に答える
0

それはあなたが受け入れる表現の種類に少し依存します。次の表現を想像してみてください。

OneMove
    from : integral
    to   : integral

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

多くの繰り返しが含まれるため、このような表現は実際には線形の複雑さで作成できます。

私はそれを試しましたが、高さ64のこのようなソリューションの構築には1ミリ秒もかかりませんでした。もちろん、それをステップスルーするには、2n -1ステップかかります。

言語を指定しませんでしたが、C ++のコードが必要な場合は、1行削除してください。

于 2017-11-10T10:08:24.150 に答える