用任意輸入解決河內塔

Question

我想解決河內塔任意（但有效）輸入。
例如我有3盤遊戲：

A B C 

| | | 
| | 1 
| 3 2 

迭代和維基百科上給出的遞歸算法失敗，該輸入。遞歸停止在錯誤的位置或嘗試非法移動，並且迭代不會終止。

有沒有一個「簡單」的算法來解決這個問題？ 我發現的唯一的其他問題是Towers of Hanoi - giving help to the user mid game，這兩個答案都沒有幫助。

Answer 1

簡單，但不是很有效的回答：

首先在小問題上運行算法得到一個標準的大，然後在更大的問題運行算法。
在給定的例子，你可以運行SolveHanoi(2, C, B)然後SolveHanoi(3, B, A)所有三個圓盤從給定的狀態轉移到A.

更有效的解決方案：

注意，遞歸解決方案（如果我沒有記錯我的權利）在較小的問題上運行算法，移動一張光盤，然後在相同的小問題上運行算法，但稍有不同。

我建議你嘗試（或以某種方式檢查），運行原始算法，但不是全部 - 只是需要從給定狀態運行的部分。

澄清：

望着給出的例子，認爲這樣的：
如果有一個遊戲，所有的光盤是在調查B和你需要將它們移動到A，算法將：
1.移動光盤1 & 2至C.
2.移動3至A.
3.移動1 & 2至A.

你分別給予輸入是4的階段＃1後的泰特。

你的解決方案應該這樣做：
1.實現什麼是可能的初始狀態（沒有太多選項，因爲有三個輪詢開始）。
2.在NOT-REAL-OP模式下運行遞歸算法（沒有實際做任何移動），直到達到給定狀態。
3.繼續以REAL-OP模式運行算法。

希望這有幫助。

Answer 2

對於維基百科上的解決方案：它們只是將堆棧從一個引腳移到另一個引腳，而不是任何輸入。您可能會考慮使用一些路徑查找算法（適用於任何有效輸入和預期輸出）。

define state := a state of the hanoi tower (the positions of all elements on the pins). 

define listMoves := returns a list of all valid moves that can made from the specified state 

define solve: 
    input: state start , state end 
    output: void 

    list visited 
    list nextStates 
    add(nextStates , start) 

    while NOT isEmpty(nextStates) 
     state s = remove(nextStates , 0) 

     if s == end 
      return 

     add(visited , s) 

     for state n : listMoves(s) 
      if NOT contains(visited , n) 
       add(nextStates , n) 
       add(visited , n) 

這只是一些簡單的BFS。你可以使用Dijkstra或A *。

Answer 3

嗯，我會說有一個「簡單」的算法：一個蠻力，遞歸搜索所有可能的移動，直到你找到目標狀態。作爲一種算法，這很「容易」，但可能需要一些時間來處理，具體取決於問題的大小。另外，對於使用m個圓盤的n個樁，可能存在幾個狀態，所以較大的拼圖可能會造成記憶問題。

例如，使用Dijkstra's algorithm：

• Dijkstra的 「圖」 是所有可能的板狀況的集合。
• 迪傑斯特拉的「節點」是一個單板狀態。
• 從一個節點到下一個節點的「距離」是到達那裏所需的移動次數 。

然後，您可以使用「infinite graph」優化來避免必須枚舉初始化階段中的所有狀態。

回到實用性，我認爲主要問題是「什麼是存儲板狀態的最佳方式？」。我使用稍微不同的實施例在這裏爲了清楚（3樁，4片）：

A B C 
| | | 
| 3 1 
| 4 2 

一種簡單的方法，其模型的板。將具有用於每個樁一個整數數組，每個包含的數在該樁光碟：

A -> [] 
B -> [3,4] 
C -> [2,1] 

然而，我的第一本能會走輪的其它方法，並且只是存儲包含樁每個盤是在單個陣列（1是C，2是C， 3在B上，4在B上）：

Discs = [C,C,B,B]  // four entries, one for each disc 

這完全捕獲了單個陣列中的電路板狀態，並且很容易比較（如果需要，您可以在此存儲單個字符串：「CCBB」）。

要計算下一個可能的移動，只需遍歷該數組：第一次看到一個字母，即該堆上最小的光盤（A上沒有任何內容，3是B的頂部，1是C的頂部）：

Piles = [0,3,1]  // three entries - one for each pile 

然後你就可以移動到空樁（0）或更大的數字的任何條目，所以可能的行動是：

3 -> 0 : B -> A : Discs[3] = "A" // move disc 3 from B to A giving [C,C,A,B] 
1 -> 0 : C -> A : Discs[1] = "A" // move disc 1 from C to A giving [A,C,B,B] 
1 -> 3 : C -> B : Discs[1] = "B" // move disc 1 from C to B giving [B,C,B,B] 

我想，如果我真的寫了這個我可能最終會緩存盤子狀態下每個堆中最小的光盤，以便每次都重新計算它，但是這個想法是 一樣。

祝你好運。

Answer 4

河內迭代解決方案塔 import java.util.Arrays;

公共類TowerOfHanoi {

private static int SIZE = 5; 

private class stack { 

    stack(int size) { 
     dataElements = new int[size]; 
    } 
    int[] dataElements; 

    int top = -1; 

    private void push(int element) { 
     dataElements[++top] = element; 
    } 

    private int pop() { 
     if(top==-1) { 
      return -1; 
     } 
     int topEle = dataElements[top]; 
     dataElements[top]=0; 
     top --; 
     return topEle; 
    } 

    private int top() { 
     if(top==-1) { 
      return -1; 
     } 
     return dataElements[top]; 
    } 

    private boolean isEmpty() { 
     return top == -1; 
    } 
} 

public static void main(String[] args) { 
    towerOfHanoi(SIZE); 
} 

private static void towerOfHanoi(int number) { 
    initialize(number); 
    if(number % 2 == 0) { 
     solveEven(number); 
    } else { 
     solveOdd(number); 
    } 
} 

private static int recentMoved = -1; 

private static stack source = new TowerOfHanoi().new stack(SIZE); 
private static stack intermediate = new TowerOfHanoi().new stack(SIZE); 
private static stack destination = new TowerOfHanoi().new stack(SIZE); 

private static void solveEven(int number) { 

    while(destination.top < number-1) { 
     if(!movePlates(source, intermediate, destination)) { 
      if(!movePlates(intermediate,destination,source)) { 
       if(!movePlates(destination, source, intermediate)){ 
        continue; 
       } 
      } 
     } 
    } 

} 



private static boolean movePlates(stack from , stack dest1 ,stack dest2) { 
    boolean movedPlate = false; 
    if(from.top()== recentMoved) { 
     return movedPlate; 
    } 
    if((!from.isEmpty()) && from.top()<(dest1.top()==-1?10000:dest1.top())) { 
     dest1.push(from.pop()); 
     recentMoved=dest1.top(); 
     movedPlate = true; 
    } 
    else if((!from.isEmpty()) && from.top()<(dest2.top()==-1?10000:dest2.top())){ 
     dest2.push(from.pop()); 
     recentMoved=dest2.top(); 
     movedPlate = true; 
    } 
    if(movedPlate) 
     display(); 
    return movedPlate; 
} 

private static void display() { 
    Arrays.stream(source.dataElements).forEach(System.out::print); 
    //.stream().fl.forEach(System.out::print); 
    System.out.print("\t"); 
    Arrays.stream(intermediate.dataElements).forEach(System.out::print); 
    System.out.print("\t"); 
    Arrays.stream(destination.dataElements).forEach(System.out::print); 
    System.out.print("\n"); 
} 


private static void initialize(int number) { 
    for(int i=number;i>0;i--) { 
     source.push(i); 
    } 
} 

private static void solveOdd(int number) { 
    while(destination.top < number-1) { 
     if(!movePlates(source, destination, intermediate)) { 
      if(!movePlates(destination,intermediate,source)) { 
       if(!movePlates(intermediate, source, destination)){ 
        continue; 
       } 
      } 
     } 
    } 

} 

}