私のIDA*の実装にバグがあるか、非効率的かを判断できません

Question

A-STAR検索を深める反復的なA-STAR検索（8パズルの問題については、他の問題を受け入れることができます）を実装し、入力で実行しました。 2時間失敗しました。ゴールノードに近いより単純な入力の場合、正常に動作します。他の人は、この入力のためにそれを機能させました。私の実装が非効率的であるか、無限のループに入っているのかはわかりません

PuzzLeSolver.java $ ida

    /** Accepts start node root and string identifying whihc heuristic to use
      * h1 is number of misplaced tiles and h2 is Manhattan distance
      */
    private Node ida(Node root, final String h) {
     PriorityQueue<DNode> frontier = new PriorityQueue<DNode>(10, new Comparator<DNode>(){
        @Override
        public int compare(DNode n1, DNode n2) {
            if(h == "h1") {
                if(n1.depth + h1(n1.node) > n2.depth + h1(n2.node)) return 1;
                if(n1.depth + h1(n1.node) < n2.depth + h1(n2.node)) return -1;
                return 0;
            }
            if(h == "h2") {
                if(n1.depth + h2(n1.node) > n2.depth + h2(n2.node)) return 1;
                if(n1.depth + h2(n1.node) < n2.depth + h2(n2.node)) return -1;
                return 0;
            }
            return 0;
        }});
    ArrayList<Node> explored = new ArrayList<Node>();
    Node soln = null;
    DNode start = new DNode(root, 1);
    frontier.add(start);
    int d = 0;
    int flimit = (h == "h1" ? h1(start.node) : h2(start.node));
    int min = flimit;
    while(true) {
        DNode dn = frontier.poll();
        if(dn == null) {
            frontier.add(start);
            d = 0;
            flimit = min;
            continue;
        }
        d = dn.depth;
        Node n = dn.node;
        //n.print();
        if(goalCheck(n)){
            return n;
        }
        for(int i = 0;i < ops.length;i++) {
            String op = ops[i];
            if(n.applicable(op)) {
                soln = n.applyOp(op);
                int h_cost;
                if(h == "h1") h_cost = h1(soln);
                else h_cost = h2(soln);
                if(!checkDup(explored,soln) && d + 1 + h_cost < flimit) {
                    frontier.add(new DNode(soln, d + 1));
                    DNode least = frontier.peek();
                    min = least.depth + (h == "h1" ? h1(least.node) : h2(least.node));
                }
            }
        }
        explored.add(n);
        max_list_size = Math.max(max_list_size, frontier.size() + explored.size());
    }
}

puzzLeSolver.java $ checkdup

    private boolean checkDup(ArrayList<Node> explored, Node soln) {
    boolean isDuplicate = false;
    for(Node n:explored) {
        boolean equal = true;
        for(int i = 0;i < soln.size; i++) {
            for(int j =0 ;j<soln.size;j++) {
                if(soln.state.get(i).get(j) != n.state.get(i).get(j)) {
                    equal = false; 
                }
            }
        }
        isDuplicate |= equal;
    }
    return isDuplicate;
}

START STATE（失敗）：

1 2 3 
8 - 4
7 6 5

目標状態：

1 3 4 
8 6 2 
7 - 5

（1 3 4 8 6 0 7 5 2）node.javaを含めていません。なぜなら、ベストファースト、DFSなどの他の検索アルゴリズムを実行した後に機能すると確信しているからです。 SCCEを提供することは困難なので、IDAの実装で明らかなバグを見つけるのを手伝ってくれるだけです。

編集：問題を解決しましたが、目標に到達できない場合に終了条件を把握しようとしています。 Ida*は、探索されたノードのリストを保持していないので、ソリューションスペース全体をカバーしているかどうかはどうすればわかりますか？

Answer 1

新しいFlimitを計算した方法に間違いがありました。他のケースでは問題を引き起こしませんでした。なぜなら、後継者の軽薄はそれが無限にループを引き起こさなかったほどであったからです。また、条件はf（現在のノード）<=カットオフです。そして、私が取ったように「<」ではありません。

更新版：

private Node ida(Node root, final String h) {
    PriorityQueue<DNode> frontier = new PriorityQueue<DNode>(10, new Comparator<DNode>(){
        @Override
        public int compare(DNode n1, DNode n2) {
            if(h == "h1") {
                if(n1.depth + h1(n1.node) > n2.depth + h1(n2.node)) return 1;
                if(n1.depth + h1(n1.node) < n2.depth + h1(n2.node)) return -1;
                return 0;
            }
            if(h == "h2") {
                if(n1.depth + h2(n1.node) > n2.depth + h2(n2.node)) return 1;
                if(n1.depth + h2(n1.node) < n2.depth + h2(n2.node)) return -1;
                return 0;
            }
            return 0;
        }});
    ArrayList<Node> explored = new ArrayList<Node>();
    Node soln = null;
    DNode start = new DNode(root, 1);
    frontier.add(start);
    int d = 0;
    int flimit = (h == "h1" ? h1(start.node) : h2(start.node));
    int min = flimit;
    while(true) {
        DNode dn = frontier.poll();
        if(dn == null) {
            explored.clear();
            frontier.add(start);
            d = 0;
            flimit = min;
            continue;
        }
        d = dn.depth;
        Node n = dn.node;
        //n.print();
        if(goalCheck(n)){
            return n;
        }
        min = Integer.MAX_VALUE;
        for(int i = 0;i < ops.length;i++) {
            String op = ops[i];
            if(n.applicable(op)) {
                soln = n.applyOp(op);
                int h_cost;
                if(h == "h1") h_cost = h1(soln);
                else h_cost = h2(soln);
                if(!checkDup(explored,soln))    {
                    if(d + 1 + h_cost <= flimit) {
                        frontier.add(new DNode(soln, d + 1));
                    }
                    else {
                        if(d + 1 + h_cost < min)min = d + 1 + h_cost; 
                    }
                }
            }
        }
        explored.add(n);
        max_list_size = Math.max(max_list_size, frontier.size() + explored.size());
    }
}

Answer 2

君の checkDup 機能は非常に非効率的です。使用することをお勧めします HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlあなたの関数にはセットのサイズがコスト線形があり、 contains の方法 HashSet 一定のコストがあります。

Javaの文字列はと比較されます equals: java string.equals versus ==

他の問題があるかもしれませんが、これらはあなたのコードを迅速にチェックした後に私が見つけた2つの最も明白なものです。