Es kann nicht feststellen, ob meine IDA* -implementierung einen Fehler hat oder nur ineffizient ist

Question

Ich habe die iterativen Deveving A-Star-Suche implementiert (für das 8-Puzzle-Problem, kann aber andere Probleme akzeptieren) und führte sie bei einem Eingang durch. Es lief erfolglos für 2 Stunden. Für einfachere Eingaben, die nahe am Torknoten liegen, funktioniert es einwandfrei. Andere haben es für diesen Eingang zum Laufen gebracht. Ich bin mir nicht sicher, ob meine Implementierung nur ineffizient ist oder in eine unendliche Schleife geht

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

Status starten (fehlgeschlagen):

1 2 3 
8 - 4
7 6 5

Zielzustand:

1 3 4 
8 6 2 
7 - 5

(arbeitete für 1 3 4 8 6 0 7 5 2) Ich habe keinen Knoten.java aufgenommen, weil ich mir ziemlich sicher bin, dass es funktioniert, nachdem andere Suchalgorithmen wie Best-First, DFS ausgeführt wurden. Es ist schwierig, einen SCCE zu liefern, daher bitte ich nur um Hilfe beim Erkennen offensichtlicher Fehler in der IDA -Implementierung.

Bearbeiten: Lösendes Problem, aber immer noch versucht, eine Kündigungsbedingung herauszufinden, wenn das Ziel nicht erreichbar ist. IDA* behält keine Liste erkundeter Knoten. Wie kann ich also wissen, ob ich den gesamten Lösungsraum abgedeckt habe?

Answer 1

Es gab einen Fehler in der Art und Weise, wie ich den neuen Fell berechnete. Es verursachte in den anderen Fällen kein Problem, da die Dunkelheit des Nachfolgers so war, dass es nicht unendlich schleifen. Auch der Zustand sollte f (Stromknoten) <= Cutoff. und nicht '<' wie ich nahm.

Aktualisierte Version:

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

Dein checkDup Funktion ist sehr ineffizient. Ich empfehle eine Verwendung a HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlIhre Funktion hat eine Kosten linear in der Größe des Satzes, während die contains Methode von HashSet hat ständige Kosten.

Saiten in Java werden verglichen mit equals: Java String.equals versus ==

Es mag andere Probleme geben, aber dies sind die beiden offensichtlichsten, die ich nach einer kurzen Überprüfung Ihres Codes entdeckt habe.