1

反復的な深化 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;
}

開始状態 (失敗):

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* は探索されたノードのリストを保持していません。では、ソリューション空間全体をカバーしたかどうかをどのように確認できますか?

4

2 に答える 2

2

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

Java の文字列は次のように比較されequalsます: Java String.equals と ==

他にも問題がある可能性がありますが、コードを簡単にチェックした後に見つけた最も明白な問題は次の 2 つです。

于 2013-11-06T22:46:41.617 に答える
1

新しい flimit の計算方法に誤りがありました。それ以外の場合は、サクセサの 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());
    }
}
于 2013-11-07T05:49:43.767 に答える