0

我正在尝试通过迭代深化搜索来解决 15 谜题（滑动谜题）。

这是我的初始状态：

1 2 12 13
5 6 7 8
9 3 4 0
11 14 15 10

这是我的目标状态：

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

我有一类节点来代表我的状态。这个类看起来像这样：

    public List<Node> children = new LinkedList<Node>(); 
    public Node parent; 
    public static final int size = 4;
    public int[][] puzzle = new int[size][size];
    public int depth = 0;

这是我的搜索功能：

public List<Node> ids(Node root) {
    List<Node> path = new LinkedList<Node>();
    boolean goal = false;
    for(int limit=0; !goal; limit++) {
        path = dfs(root,limit);
        if(!path.isEmpty())
            goal = true;
    }
    return path;
}

public List<Node> dfs(Node root, int limit) {
    List<Node> path = new LinkedList<Node>();
    PriorityQueue<Node> queue = new PriorityQueue<Node>(10000, new  Comparator<Node>() {
        public int compare(Node n1, Node n2) {
            int depth1 = n1.depth;
            int depth2 = n2.depth;
            if(depth1 > depth2)
                return 1;
            else if(depth1 < depth2)
                return -1;
            return Node.comparePuzzle(n1.puzzle, n2.puzzle);
        }
    });
    List<Node> expendList = new LinkedList<Node>();
    List<Node> expended = new LinkedList<Node>();
    queue.add(root); 
    boolean goal = false;
    while(!queue.isEmpty() && !goal) {
        Node temp = queue.poll();
        expended.add(temp);
        if(!temp.isGoal()) {
            temp.expend();
            for(int i=0; i<temp.children.size(); i++) {
                Node child = temp.children.get(i);
                child.setDepth(temp.getDepth() + 1);
                expendList.addAll(queue);
                if(!contains(expendList,child) && !contains(expended,child) && child.depth < limit)
                {
                    queue.add(child);
                }
            }
        } else {
            goal = true;
            pathTrace(path,temp);
        }
    }
    return path;
}

目标状态位于搜索树的深度 9，但我的函数卡在限制 6 中，我不知道为什么。当目标深度为 6 或更少时，函数会找到解决方案，但当深度大于 6 时，函数会运行很多时间并卡住。

4

0 回答 0