如果这是一个很长的问题，我很抱歉，但我不确定我的 A* 8 puzzle java 代码是否有效...我发现我的代码对于简单的输入运行得很好(易于平均情况)，但是我不知道它在最坏的情况下是否有效......
我尝试修改我的代码以使用每个节点的曼哈顿距离作为我的启发式函数，并且我的代码即使在最坏的情况下也能工作，但它需要太长时间......并且当我使用“错位瓷砖的数量”时作为我的启发式函数，与使用曼哈顿距离相比，我的代码需要更长的时间来运行简单到平均的情况。即使在 15 分钟后，它也不会为最坏的情况提供解决方案...
注意:在最坏的情况下，8 个难题可以通过不超过 31 步解决...
...这是我的代码的主要功能:
List<Node> nodeList = new ArrayList<Node>();
nodeList.add(startNode); //"Node startNode" contains the root node of the tree that will be produced
Node currentNode = null;
while (1 == 1) {
//THIS SECTION FINDS THE LEAF NODE WITH THE LEAST f(n)
currentNode = null;
for (Node pickNode : nodeList) {
if (pickNode.isLeaf == true) {
if (currentNode == null)
currentNode = pickNode;
else if (pickNode.fn < currentNode.fn){
currentNode = pickNode;
}
}
}
/*-----------------------------------------------------------*/
//BREAK THE LOOP WHEN THE SOLUTION IS FOUND
if (Arrays.deepEquals(currentNode.state, goalState))
break;
/*-----------------------------------------------------------*/
else {
int xcheck = currentNode.zeroX;
int ycheck = currentNode.zeroY;
int switcher;
int approve = 1;
/*-----------------------------------------------------------*/
//THE FOLLOWING LINES DETERMINES WHICH CHILDREN CAN BE PRODUCED BY A NODE
if ((ycheck - 1) >= 0) {
int subState[][] = new int [3][];
subState[0] = currentNode.state[0].clone();
subState[1] = currentNode.state[1].clone();
subState[2] = currentNode.state[2].clone();
switcher = subState[ycheck-1][xcheck];
subState[ycheck-1][xcheck] = 0;
subState[ycheck][xcheck] = switcher;
Node checkerNode = new Node();
checkerNode = currentNode;
while (checkerNode != null) {
if (Arrays.deepEquals(subState, checkerNode.state)) {
approve = 0;
break;
}
checkerNode = checkerNode.parentNode;
}
if (approve != 0) {
Node childNode = new Node();
childNode.state = subState;
childNode.totalPath = currentNode.totalPath + "*" + "up";
childNode.gn = currentNode.gn + 1;
childNode.hn = computeHn(childNode.state, goalState);
childNode.fn = childNode.gn + childNode.hn;
childNode.isLeaf = true;
childNode.parentNode = currentNode;
childNode.zeroX = xcheck;
childNode.zeroY = ycheck-1;
nodeList.add(childNode);
}
}
approve = 1;
/*-----------------------------------------------------------*/
if ((ycheck + 1) <= 2) {
//same logic with: if (ycheck-1 >= 0)
}
approve = 1;
/*-----------------------------------------------------------*/
if ((xcheck + 1) <= 2) {
//same logic with: if (ycheck-1 >= 0)
}
approve = 1;
/*-----------------------------------------------------------*/
if ((xcheck - 1) >= 0) {
//same logic with: if (ycheck-1 >= 0)
}
approve = 1;
}
currentNode.isLeaf = false;
}
这是计算我的启发式的函数(错位的瓷砖数量而不是曼哈顿距离):
public static int computeHn (int checkStateH[][], int goalStateH[][]) {
int total = 0;
int rowC = 0;
int columnC = 0;
rowC = 0;
while (rowC < 3) {
columnC = 0;
while (columnC < 3) {
if (goalStateH[rowC][columnC] != checkStateH[rowC][columnC]) {
total++;
}
columnC++;
}
rowC++;
}
return total;
}
这是我的 Node 类:
public class Node {
int state[][]; //contains the matrix configuration of the node
String totalPath; //contains the path on how to get to this node from the root node
int gn; //contains the number of moves made to get to this node from the root node
int hn; //contains the heuristic (number of misplaced tiles per node)
int fn; // fn = gn + hn
boolean isLeaf; //states whether a node is a leaf or not. used so that I can know whether a node could still be expanded or not
Node parentNode; //points to the node's parent node
int zeroX; //the x position of the zero tile
int zeroY; //the y position of the zero tile
}
这是给定的矩阵，或“开始状态”矩阵(在最坏的情况下，至少可以通过 31 次移动来回答):
- 8 0 6
- 5 4 7
- 2 3 1
...它应该达到这个最终状态:
- 0 1 2
- 3 4 5
- 6 7 8
...再次，当我使用“曼哈顿距离”作为我的启发函数时，我的代码可以工作，但需要 30 秒才能为此类输入生成答案...但是当我使用“错放的瓷砖数量”时“作为我的启发式函数，即使在 15 分钟后它也不会产生解决方案，但当我使用此矩阵时会给出答案:
- 5 8 6
- 2 7 1
- 3 0 4//这个矩阵可以从前面提到的起始状态矩阵到达
...感谢那些愿意提供帮助的人!...如果它有点长，我很抱歉，但我认为我应该发布我的代码，而不是仅仅说明我的代码的逻辑，因为我可能在实现时犯了错误我的逻辑...
最佳答案
曼哈顿距离更快是有道理的，因为它是一个更好的启发式方法。 30 秒等待解决方案的时间有点长，尤其是对于 C++ 来说，但这并不是完全荒谬的。不过，即使对于一个不太好的启发法来说，15 分钟也是如此。
如果我正确解释了您的代码，则 checkerNode 循环将通过遍历整个路径来检查您当前正在探索的路径中是否已存在此状态。这是相当低效的(我认为 O(log(n)ish))。如果您维护一个已扩展状态的字典，则可以将其缩短为常数时间。
可能还有其他微妙的低效率问题，但我怀疑这会大大加快您的代码速度。
编辑解释字典:
字典是一种数据结构，可让您快速查找元素是否存在。
对于大多数数据结构，如果要查找具有给定值的元素，则必须将该值与结构中已存储的每个元素进行比较(就像将 checkerNode 与所有前驱节点进行比较一样)。问题是，当你在数据结构中存储越来越多的东西时，这个过程需要的时间越来越长。字典的情况并非如此，因为字典使用称为哈希表的东西立即转到给定元素(如果存在)的存储位置。然后，如果该元素存在，您就知道它在数据结构中，如果不存在，您就知道它不在数据结构中。
字典通常用于将给定键映射到关联值，但在这里我们并不真正关心该功能。我们只想知道给定的键是否在字典中，因此我们可以将值设置为我们想要的任何值(通常我只存储 boolean 值“True”，或者如果需要的话，存储指向节点的指针以便再次找到它)。在C++中，内置字典类是 std::map .
要在代码中使用它，您可以大致执行以下操作:
首先，初始化 map 对象
std::map<char,int> already_explored;
执行程序开始，直到刚刚为currentNode 赋值为止。现在我们正在探索 currentNode，我们将它的状态添加到字典中。状态是键，“True”是值。
already_explored[currentNode.state] = True;
继续执行程序，直到找到下一个状态(想知道它是否已经被看到)。现在我们可以在字典中查找:
if (already_explored.count(subState) > 0){
approve = 0;
}
如果您按此顺序执行操作，您甚至不必担心检查具有相同状态的其他节点的 f(n) 值。 A* 达到的第一个肯定是达到该状态的最快方法。走更长的路到达同一个状态永远不会有任何好处。
关于java - A* 8 谜题运行时间太长，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28600118/