3

您好我正在使用 java 创建一个 Solver 程序，该程序使用 HeapMinPQ 和节点的帮助来解决基于“8 拼图”格式的任何板。我已经通过“Board”数据类型创建了该数据类型，它使用二维数组来计算图块（“0”是空白区域）。在我的 SearchNodes 中，我有一个优先整数，它解释了“曼哈顿”值（我确信该方法可以正常工作）。问题是我一直在努力取得进展，虽然我的程序可以编译，但它只是卡在运行而没有给出适当的输出（所需的最少移动次数）。我想我很难理解所有这些，但这是我到目前为止要解决的代码......

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; 
 }

这是我来自“板”数据类型的“双胞胎”方法。

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(heap, twinHeap); 开始。公共 Solver(Board initial) 方法中的方法。任何帮助将不胜感激。

4

1 回答 1

0

这里有一些技巧来解决 8-puzzle 问题：

板级：

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

  2. 生成双板时，注意不要将数字与编号为 0 的空白瓷砖交换。生成随机双板时，最好先生成两个范围为 [0, n*n) 的随机值。然后将它们转移到行和列索引。

  3. 在生成棋盘的邻居时，不要忘记更新空白棋盘位置索引。

对于求解器类：

  1. 建议使用描述游戏节点的新私有内部类。在这个类中，我们可以记录棋盘、走法和上一个节点。并更新将在优先级队列中使用的 Hamming 和 Manhattan 方法，以将预期节点出列。

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

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

  4. 我的代码在这里： 我的 8-puzzle 代码未针对 Solver 进行时序优化。

于 2017-01-04T03:21:51.963 回答