使用A*算法求解8字谜板（板数据类型工作良好）

Question

嗨，我正在使用Java创建一个求解程序，使用HeapMinPQ和节点的协助，以解决基于“8字谜”格式的任何板。我已经创建了“board”数据类型，它使用一个二维数组来解释瓷砖（而“0”是空白空间）。在我的SearchNodes中，我有一个优先级整数，它代表“Manhattan”值（我确信该方法工作良好）。问题是，我一直在努力取得进展，尽管我的程序进行了编译，但它只是在没有给出适当的输出（所需的最小移动次数）的情况下运行卡住了。我想我很难理解这一切，但这是我目前要解决的代码...

import java.util.Comparator;
public class Solver {
private SearchNode result;

// Helper search node class.
private class SearchNode {
    SearchNode prev; 
    Board value; 
    int moves = 0; 
    int priority;


    public SearchNode(Board board, SearchNode previous) {
        super();
        this.value = board; 
        prev = previous; 
        if (null != previous) { 
            this.moves = previous.moves + 1; 
        } else { 
            this.moves = 0; 
        } 
         // priority = this.value.hamming() + moves; 
         priority = this.value.manhattan() + moves; 

    }
}

/**
 * Finds a solution to the initial board (using the A* algorithm).
 * @param initial initial board.
 */
public Solver(Board initial) {
    SearchNode root = new SearchNode(initial, null); 
    HeapMinPQ<SearchNode> heap = new HeapMinPQ<SearchNode>(new ManhattanOrder()); 
    heap.insert(root);


     Board twin = initial.twin();
     SearchNode twinRoot = new SearchNode(twin, null); 
     HeapMinPQ<SearchNode> twinHeap = new HeapMinPQ<SearchNode>(new ManhattanOrder()); 
     twinHeap.insert(twinRoot); 


     solve(heap, twinHeap);

}

private void solve(HeapMinPQ<SearchNode> heap, HeapMinPQ<SearchNode> twinHeap) { 
     while (!heap.isEmpty() && !twinHeap.isEmpty()) { 
         if (null != perform(heap)) { 
             return; 
         } 


         if (null != perform(twinHeap)) { 
             result = null; 
             return; 
         } 
     } 
 } 


 private SearchNode perform(HeapMinPQ<SearchNode> heap) { 
     SearchNode n = heap.delMin(); 
     if (n.value.isGoal()) { 
         result = n; 
         return result; 
     } 
     for (Board board : n.value.neighbors()) { 
         SearchNode x = new SearchNode(board, n); 
         if (null != n.prev && n.prev.value.equals(board)) { 
             // don't add neighbors that are same as previous board 
             continue; 
         } 
         heap.insert(x); 
     } 
     return null; 
 }

这是我来自“board”数据类型的“twin”方法。

public Board twin(){
     int dim = this.length; 
     int[][] copy = this.tiles; 
     if (this.length <= 1) 
         return new Board(copy); 
     // Find zero so that we don't exchange with the blank 
     // This looks like a O(dim^2) algorithm, but on average it should finish 
     // in O(1). 
     int row = 0; 
     int col = 0; 
     int value = 0; 
     int lastValue = tiles[0][0]; 
     zerosearch: for (row = 0; row < dim; row++) { 
         for (col = 0; col < dim; col++) { 
             value = tiles[row][col]; 
             // Check col>0 because swap must occur on same row 
             if (value != 0 && lastValue != 0 && col > 0) 
                 break zerosearch; 
             lastValue = value; 
         } 
     } 
     copy[row][col] = lastValue; 
     copy[row][col - 1] = value; 
     return new Board(copy); 


}

这里一定有一个很深的错误计算，我非常肯定它开始于solve（堆，twinHeap）；公共求解器（Board initial）方法中的。如有任何帮助，将不胜感激。

Answer 1

以下是解决8字谜问题的一些技巧：

对于Board类：

>

在实现Board类时，最好使用两个整数变量（如rowIndex和colIndex）来跟踪空白（数字0）的位置。如果你是作为Coursera的作业使用自定义的位置类，可能会导致你无法通过记忆测试。

对于生成一个双板，请注意不要将一个数字与数字为0的空白瓷砖互换。为了生成一个随机双胞胎，最好首先生成两个范围为[0,n*n]的随机值，然后将它们转移到行和列索引。

当生成一块板的邻居时，不要忘记更新空白瓷砖位置索引。

对于求解器类：

>

推荐一个新的私有内部类来描述一个游戏节点。在这个类中，我们可以记录棋盘、移动和上一个节点。并对优先级队列中使用的Hamming方法和Manhattan方法进行了更新,以实现对期望节点的查询。

为了避免进入长时间循环，在将节点插入优先级队列之前，请检查该节点是否已经在队列中。

以下是Coursera提供的一些有用的解释和建议:http://coursera.cs.princeton.edu/algs4/checklists/8puzzle.html

我的代码在这里：我的8字谜代码没有时间优化的求解器。