java - 当limit=6时Java迭代加深搜索卡住
问题描述
我正在尝试通过迭代深化搜索来解决 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 时,函数会运行很多时间并卡住。
解决方案
推荐阅读
- azure-ad-b2c - Azure B2C,在 IDP 启动的自定义提供程序配置上未设置对象引用错误
- psycopg2 - 具有不同空数据类型的 psycopg2 Copy_From
- ios - 无法访问我的单元格内容中的变量
- python - How to functionally compose futures?
- nlog - 归档文件大小超过指定大小,archiveAboveSize 与 NLog
- sql - 仅当值存在时打印引号
- node.js - Firebase Promise 向用户返回 null,但在云功能测试中返回正常数据
- java - Integrating Cloudinary with Adobe AEM
- excel - 如何使用 VBA 突出显示散点图中的最后一个数据点
- r - R:使用 for 循环创建一个新的数据表,其中包含给定多列组合的最小和最大变量