河內的解決方案比O（2^n）好？

是否有河內構成的運行時間小於O（2 ^Ñ）其中Ñ是磁盤的數量來移動的塔的溶液？我的解決方案需要O（2 ⁿ）時間。河內的解決方案比O（2^n）好？

此外，下面的解決方案是遞歸。我們可以使用動態規劃與memoization的概念來解決這個在較短的時間？

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領域和存取。

另外，是否有同樣的問題的任何變化？

來源

2012-05-21 dharam

「有溶液河內塔的運行時間小於O（2^n），其中n是要移動的磁盤數量？「 - 是的。這就是所謂的作弊:-) –

我們該怎麼做？ – dharam

...你拿起整個堆棧，並立即移動它。不，沒有任何方法遵循比2^n更好的規則。 –

鑑於解決河內塔總是需要2^n-1步......不，你不會找到更快的算法，因爲它需要O（2^n）來打印出步驟，更少計算它們。

來源

2012-05-21 02:19:28

我不會證明（就像斯蒂芬那樣），但我會直觀地解釋2^n-1是最小的：在每個狀態下，磁盤只有三種可能的移動。讓我們將當前狀態表示爲有序seq（1,1，...，1），這樣第一個數字表示更大磁盤的位置，最後一個數字表示最小磁盤的位置。（1,1，...，1）表示所有磁盤都在位置1上。同樣從（1,1，.1）中只有兩種下降狀態：（1,1，... 2）和1,1，... 3）。從（1,1，... 2）有三個降狀態：

回到（1,1，... 1）
轉到（1,1，...，3）
轉到（1,1，... 3，2）

如果繼續下去，你會得到圖爲其節點是可能的狀態和邊緣（過渡）是「移動硬盤」。（1，1，... 1），（2，2，。2），（3）和（3），3，... 3））。步數實際上是圖中的路徑。

如果沿着三角形的邊緣走，步數在2^n-1。所有其他路徑長度相同或更長。

enter image description here

如果您使用的策略：移動除了最大所有磁盤放置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-21 04:54:11

+1手繪gfx :-) – hirschhornsalz

溶液河內的塔是不可避免的2 ⁿ。然而，在動態規劃解決方案中，每個子問題只計算一次，然後通過組合第一個子問題解決方案，當前磁盤移動和第二個子問題解決方案來解決問題。

因此，在生成每個解決方案時有兩個組件：爲當前解決方案分配內存，然後填充該內存。內存分配大致與分配的內存大小無關，是昂貴的組件。內存複製在複製的內存大小上是線性的，儘管速度很快，但是作爲Towers的解決方案在n中是指數級的。

時間= C * N + C個 * 2 ^Ñ，其中c >> C 2 。即，它開始線性並結束指數。

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

來源

2012-10-12 18:37:29

對此主題的精彩見解！起初，我不太容易理解，直到我自己從[通過谷歌搜索找到這個網站]（http://penguin.ewu.edu/~trolfe/DynamicHanoi/）的靈感來實現它，然後我開始意識到示例程序和回答者都是同一個人。謝謝@蒂姆羅爾夫！我很幸運能夠在網絡上追蹤你的蹤跡。 :-) – RayLuo

河內問題的標準塔處理與3個釘。但是，如果我們有k-pegs，則時間複雜度爲O（2 ^（n /（k-2）））。

我已經解決了這個問題，4個釘和5個栓釘和時間複雜性，導致爲O（2 ^（N/2））和O（2 ^（N/3））分別

來源

2015-02-25 21:46:52 JavaHopper

河內的解決方案比O（2^n）好？

回答

相關問題