使用A *算法求解8拼图板(Board数据类型工作正常) [英] Using A* algorithm to solve 8-puzzle boards (Board data type works fine)

问题描述

我正在使用Java创建一个Solver程序，该程序使用HeapMinPQ和节点的帮助来解决基于"8拼图"格式的任何棋盘.我已经通过"Board"数据类型创建了该数据类型，该数据类型使用二维数组来解释图块("0"是空白).在我的SearchNodes中，我有一个优先级整数，该整数说明了曼哈顿"值(而且我确信该方法可以正常工作).问题是我一直在努力取得进展，尽管我的程序可以编译，但是它只是在没有给出适当输出(所需的最小移动量)的情况下卡住了运行.我想我很难解决所有这些问题，但这是到目前为止要解决的代码...

Hi I'm using java to create a Solver program that uses the assistance of HeapMinPQ and nodes in order to solve any board based on the "8 puzzle" format. I've already created by "Board" data type which uses a two-dimensional array to account for the tiles (and "0" is the blank space). Within my SearchNodes, I have a priority Integer that accounts for the "Manhattan" values (and I'm sure that method works fine). The problem is that I've been trying to make progress, and although my program compiles, it simply gets stuck running without giving the appropriate output (the minimum number of moves required). I guess I'm having difficulty wrapping my head around all of this but this is my code to solve so far...

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"方法.

And this is my "twin" method from the "board" data type.

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)方法中的方法.任何帮助将不胜感激.

There must be a deep miscalculation that I'm making here and I'm pretty sure it starts at the solve(heap, twinHeap); method within the public Solver(Board initial) method. Any help would be greatly appreciated.

推荐答案

以下是解决8谜题的一些技巧:

here are some tricks to solve 8-puzzle problem:

对于董事会班级:

1. 在实现Board类时，最好使用两个整数变量(例如rowIndex，colIndex)来跟踪空白(数字0)的位置.如果您将自定义的Position类作为Coursera的一项作业，可能会导致通过内存测试失败.

1. when implementing Board class, it's better to use two integer variables (eg. rowIndex, colIndex) to track where the blank(number 0) is. Using self-defined Position class may lead to failure of passing the memory test if you are doing so as an assignment from coursera.

要生成孪生板，请注意不要将数字与数字为0的空白图块交换.要生成随机孪生，最好首先生成两个范围为[0，n * n)的随机值.然后将它们传输到行和列索引.

For generating a twin board, pay attention not to swap a number with blank tile whose number is 0. for generating a randomized twin, it's better first to generate two random values range from [0, n*n). then transfer them to row and col index.

在生成板的邻居时，请不要忘记更新空白图块位置索引.

When generating neighbors of a board, don't forget to update the blank tile position index.

对于 Solver 类:

1. 建议使用新的私有内部类来描述游戏节点.在此类中，我们可以记录板，移动和上一个节点.并更新将在优先级队列中使用的Hamming和Manhattan方法来使所需节点出队.

1. a new private inner class describing a game node is recommended. In this class, we can record the board, moves, and previous node. and update the Hamming and Manhattan methods which will be used in a Priority Queue to Deque an expected node.

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

To avoid going into a long-time loop, before inserting a node to a Priority Queue, Do check whether it has already been in the Queue.

这是来自Coursera的一些有用的解释和建议: http://coursera.cs.princeton.edu/algs4/checklists/8puzzle. html

Here are some useful explanation and suggestions from coursera: http://coursera.cs.princeton.edu/algs4/checklists/8puzzle.html

我的代码在这里: 我的8拼图代码未针对规划求解进行时序优化.

这篇关于使用A *算法求解8拼图板(Board数据类型工作正常)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！