Why IDA* Is Faster Than A* But Why IDA* Visit More Nodes That A*?

Question

I used ida* for 8 puzzle and my friends used a* for it too ( with same manhattan distance huristic ).

I calculate average of my algorithm for 20 examples and my friend's algorithm , The time average for my algorithm was very faster than my friend's algorithm but mine average nodes that visited is alot more than my friend's.

How is that possible? Can someone explain me where i didn't understand.

This is my search algorithm

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

This is my friend's search algorithm

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* iteratively opens the search frontier, so many nodes will be visited more than once. Whereas A* is more on the BFS side, depending on the implementation, most likely you will visit each node in the searched area only once. That is why IDA* visits more nodes than A*. In terms of running time, A* needs some priority queue to steer the search, the NLogN complexity is right there.