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

Question

我用ida *表示8个拼图，我的朋友也用a *表示（同一距离的曼哈顿距离）。

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

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

这是我的搜索算法

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;
    }

这是我朋友的搜索算法

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的复杂性就在那里。