java - A* 8 拼图运行时间太长

Question

如果这是一个很长的问题，我很抱歉，但我不确定我的 A* 8 拼图 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;
}

这是我的节点类:

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//这个矩阵可以从前面提到的起始状态矩阵到达

...感谢那些愿意提供帮助的人!...我很抱歉，如果它有点长，但我认为我应该发布我的代码而不是仅仅陈述我的代码的逻辑，因为我可能在实现过程中犯了错误我的逻辑...

Answer 1

曼哈顿距离会更快是有道理的，因为它是一种更好的启发式算法。 30 秒等待解决方案的时间有点长，尤其是对于 C++，但这并不是完全荒谬的。 >15 分钟是，虽然，即使是一个不太好的启发式。

如果我正确地解释了您的代码，checkerNode 循环会通过遍历整个路径来检查此状态是否已经存在于您当前正在探索的路径中。这是相当低效的(我认为是 O(log(n)ish))。如果您维护一个已经扩展的状态字典，则可以将其缩减为常数时间。

可能还有其他细微的低效问题，但我怀疑这会大大加快您的代码速度。

编辑解释字典:

字典是一种数据结构，可让您快速查找某个元素是否存在。

对于大多数数据结构，如果您想查找具有给定值的元素，则必须将该值与已存储在该结构中的每个元素进行比较(就像您将 checkerNode 与所有前导节点进行比较一样)。问题是，随着你在数据结构中存储的东西越来越多，这个过程需要的时间越来越长。字典不是这种情况，因为字典使用称为哈希表的东西立即转到给定元素(如果存在)的存储位置。然后，如果该元素存在，您就知道它在数据结构中，如果不存在，您就知道它不存在。

字典通常用于将给定的键映射到关联的值，但在这里我们并不真正关心该功能。我们只是想知道给定的键是否在字典中，所以我们可以将值设置为我们想要的任何值(通常我只存储 boolean 值“True”，或者如果您需要能够存储指向节点的指针重新找到它)。在 C++ 中，内置字典类是 std::map .

要在您的代码中使用它，您可以大致执行以下操作:

首先，初始化 map 对象

std::map<char,int> already_explored;

执行程序的开始，直到一个值刚刚分配给 currentNode。现在我们正在探索 currentNode，我们将它的状态添加到字典中。状态是键，“真”是值。

already_explored[currentNode.state] = True;

继续执行该程序，直到找到下一个状态(想知道它是否已经出现)。现在我们可以在字典中查找:

if (already_explored.count(subState) > 0){
    approve = 0;
}

如果按此顺序执行操作，您甚至不必担心检查具有相同状态的其他节点的 f(n) 值。 A* 到达的第一个保证是到达该状态的最快方式。走更长的路到达同一状态永远不会有任何好处。