8

実行時間がO（2 n）未満のハノイの塔のソリューションはありますか？ここで、 nは移動するディスクの数です。私の解決策はO（2 n）時間かかります。

また、以下の解決策は再帰を使用することです。メモ化の概念で動的計画法を使用して、これをより短時間で解決できますか？

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は、フィールドとアクセサStackを追加するJavaのクラスの拡張バージョンです。name

また、同じ問題のバリエーションはありますか？

4

5 に答える 5

17

ハノイの塔の解決には常に2^n-1ステップが必要です...いいえ、ステップを印刷するだけでO（2 ^ n）が必要であり、計算がはるかに少ないため、より高速なアルゴリズムを見つけることはできません。 。

于 2012-05-21T02:19:28.113 に答える
10

私は（スティーブンがしたように）証明しませんが、2 ^ n-1が最小であることを直感的に説明しようとします。すべての状態で、ディスクの可能な移動は3つだけです。現在の状態を順序付けられたseq（1、1、..、1）として表し、最初の数字は大きい方のディスクがどこにあるかを示し、最後の数字は最小のディスクがどこにあるかを示します。（1、1、..、1）は、すべてのディスクが位置1にあることを意味します。また、（1、1、.. 1）からは、（1、1、... 2）と（ 1、1、.... 3）。（1、1、... 2）から、3つの降順状態があります。

  1. （1、1、.. 1）に戻ります
  2. goto（1、1、...、3）
  3. goto（1、1、... 3、2）

続行すると、ノードが可能な状態であり、エッジ（遷移）が「ディスク移動」であるグラフが表示されます。

以下のような画像が表示されます（続行すると三角形のようになり、頂点は（1、1、... 1）、（2、2、.. 2）、（3、3、。 ..3））。ステップ数は、実際にはグラフのパスです。

三角形の端に沿って歩くと、2^n-1のステップ数になります。他のすべてのパスは同じ長さ以上です。

ここに画像の説明を入力してください

戦略を使用する場合：最大のものを除くすべてのディスクを配置3に移動し、次に大きいものを配置2に移動し、最後にすべてのフォーム3を2に移動します。式は、次のように考案できます。

f（n）=
f（n -1）//1から3に最大を除くすべてを移動
+1 //1から2に最大を移動
+f（n -1）//3から2にすべてを移動
->
f（ n）= 1+ 2 * f（n-1）

その反復方程式の解は、その戦略に必要なステップ数を示します（これはたまたま最小ステップ数です）

于 2012-05-21T04:54:11.067 に答える
10

ハノイの塔の解決策は必然的に2nです。ただし、動的計画法ソリューションでは、各サブ問題は1回だけ計算され、最初のサブ問題ソリューション、現在のディスク移動、および2番目のサブ問題ソリューションを組み合わせることで問題が解決されます。

したがって、各ソリューションの生成には2つのコンポーネントがあります。現在のソリューションにメモリを割り当てることと、そのメモリを埋めることです。メモリの割り当ては、割り当てられたメモリのサイズにほぼ依存せず、高価なコンポーネントです。メモリコピーは、コピーされたメモリのサイズが線形であり、高速ですが、タワーのソリューションとしてnで指数関数的になります。

時間=c1 * n + c 2 * 2 n 、ここでc 1 >>c2 。つまり、線形で始まり、指数関数で終わります。

ACMのSIGCSEInroadsマガジンに掲載されている記事へのリンク（2012年9月）

于 2012-10-12T18:37:29.030 に答える
2

ハノイの塔の標準的な問題は、3つのペグを扱います。

ただし、kペグがある場合、時間計算量はO（2 ^（n /（k-2）））になります。

4つのペグと5つのペグでこの問題を解決しました。結果として生じる時間計算量は、それぞれO（2 ^（n / 2））とO（2 ^（n / 3））です。

于 2015-02-25T21:46:52.137 に答える
-1

これは再帰的なものよりも約7％高速です。動きをリストに保存するので、後で使用できます。必要に応じて印刷して、コンテナを削除することもできます。

```
unsigned long i;  
static const int MAXNUMBEROFDISKS = 32;
vector<int> pow2Vec;
uint_fast32_t mPinFrom    = 0;
uint_fast32_t mNumDisk    = 0;
unsigned long numDiskLong = 0;
uint_fast32_t mOffset[MAXNUMBEROFDISKS];
uint_fast32_t mDir[MAXNUMBEROFDISKS]          = { 0 };
uint_fast32_t mPositionDisk[MAXNUMBEROFDISKS] = { 0 };
const uint_fast32_t mRedirectArr[5] = { 2, 0, 1, 2, 0 };




Algos::Algos()
{ 
  for (int i = 0; i < MAXNUMBEROFDISKS; ++i)
  {
    pow2Vec.push_back(pow(2, i));
    mOffset[i] = 1;
  }

  for (int i = 1; i < MAXNUMBEROFDISKS; i += 2)
  {
    mDir[i] = 2;
  }

  mOffset[0] = 0;
}




void Algos::calculListBinExperiment(vector<tuple<int, int, int>>& listeFinale, int nbDisk)
{
  listeFinale.resize(pow2Vec[nbDisk] - 1);
  _BitScanForward(&i, nbDisk);
  for (int noCoup = 1; noCoup < pow2Vec[nbDisk] ; ++noCoup)
  {
    _BitScanForward(&numDiskLong, noCoup);
    mNumDisk = numDiskLong;
    mPinFrom = mPositionDisk[mNumDisk];
    mPositionDisk[mNumDisk] = mRedirectArr[mPositionDisk[mNumDisk] + mDir[mNumDisk + 
    mOffset[i]]];
    listeFinale[noCoup - 1] = make_tuple(mNumDisk, mPinFrom, mPositionDisk[mNumDisk]);
  }
}
```
于 2020-11-17T21:53:42.933 に答える