algorithm - 为什么 IDA* 比 A* 快，但为什么 IDA* 访问的节点比 A* 多？

Question

我将 ida* 用于 8 拼图，我的 friend 也使用了 a*(具有相同的曼哈顿距离 huristic)。

我计算了 20 个示例的算法和我 friend 的算法的平均值，我的算法的平均时间比我 friend 的算法快得多，但我访问的平均节点比我 friend 的多得多。

这怎么可能？有人可以向我解释我不明白的地方。

这是我的搜索算法

public Set<String> ida(Node startNode) {
        visitedNodes.clear();
        Node initNode = startNode;
        int fValueMin;
        /*fValueMin depth to run the program.
        IDA* method being called iteratively until the depth reaches*/
        for (fValueMin = initNode.getfValue(); fValueMin < 100; fValueMin++) {
            visitedNodes.clear();
            pathNodes.clear();
            // Depth First search 
            Node nextNode = dfs(startNode, fValueMin, visitedNodes);
            /*Verifying the returned is goal state or not. If it is goal the goal exit loop*/
            if (nextNode != null && nextNode.equals(CommonConstants.goalState)) {
                System.out.println("Goal state Found");
                System.out.println("Nodes Visited:" + visited);
                return pathNodes.keySet();
            }
            // System.out.println("Iteration:" + fValueMin);
        }
        System.out.println("Number of Nodes Visited:" + visited);
        return null;
    }

这是我 friend 的搜索算法

private ActionSequence AStar(){
        System.out.println("AStar Search Started"); 
        boolean find=false; 
        QNode current; 

        do{
            current=queue.removeFirst(); 
            if(queue.size%1==0){
                try{
                    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(FileDescriptor.out),"ASCII"), 32);

                    out.write("*********************************************************************************\n\n");
                    out.write("Queue: "+queue.size+"    Depth: "+(current.element.depth+1)+"   price: "+(current.price));
                    out.write(printState(current.element.state)); 
                    out.write("\n\n\n");

                    out.flush();
                    //out.close();
            }catch(IOException gg){}
            }

            if(problem.Goal_Test(current.element.state)){
                find=true; 
            }else{
                if(current.element.action!='d'){

                        PSTNode up_child=Expand(current.element,'u'); 
                        if(up_child.state[11]==1){
                            tree.addNodeUp(up_child,  current.element);
                            QNode up_child_qn= new QNode(up_child,null, null);
                            queue.addSort(up_child_qn);
                        }

                }

                if(current.element.action!='u'){

                        PSTNode down_child=Expand(current.element,'d');
                        if(down_child.state[11]==1){
                            tree.addNodeDown(down_child,  current.element);
                            QNode down_child_qn= new QNode(down_child,null, null);
                            queue.addSort(down_child_qn);
                        }

                }

                if(current.element.action!='r'){

                        PSTNode left_child=Expand(current.element,'l');
                        if(left_child.state[11]==1){
                            tree.addNodeLeft(left_child,  current.element);
                            QNode left_child_qn=new QNode(left_child,null, null);
                            queue.addSort(left_child_qn);
                        }

                }


                if(current.element.action!='l'){

                        PSTNode right_child=Expand(current.element,'r');
                        if(right_child.state[11]==1){
                            tree.addNodeRight(right_child,  current.element);
                            QNode right_child_qn= new QNode(right_child,null, null);
                            queue.addSort(right_child_qn);
                        }

                }
            }


        }while(!find); 
        System.out.println("*******************************founded*******************************************\n\n");             
            System.out.println("Queue: "+queue.size+"    Depth: "+(current.element.depth+1)); 
            System.out.println(printState(current.element.state)); 
            System.out.println("\n\n\n");

        return Path2Root(current.element); 
    }

Answer 1

IDA* 迭代地打开搜索边界，因此许多节点将被多次访问。而 A* 在 BFS 方面更多，取决于实现，很可能您只会访问搜索区域中的每个节点一次。这就是 IDA* 比 A* 访问更多节点的原因。在运行时间方面，A* 需要一些优先级队列来引导搜索，NLogN 复杂度就在那里。