Impossibile determinare se la mia implementazione IDA* ha un bug o è semplicemente inefficiente

Question

Ho implementato l'approfondimento della ricerca A-Star iterativa (per il problema a 8 puzzle, ma posso accettare altri problemi) e ho eseguito un input. Ha funzionato senza successo per 2 ore. Per input più semplici che sono vicini al nodo obiettivo funziona bene. Altri hanno fatto funzionare per questo input. Non sono sicuro che la mia implementazione sia semplicemente inefficiente o va in un ciclo infinito

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 (fallito):

1 2 3 
8 - 4
7 6 5

Obiettivo Stato:

1 3 4 
8 6 2 
7 - 5

(Ho lavorato per 1 3 4 8 6 0 7 5 2) Non ho incluso nodo.java perché sono abbastanza sicuro che funzioni dopo aver eseguito altri algoritmi di ricerca come Best-First, DFS. È difficile fornire un SCCE, quindi sto solo chiedendo aiuto per individuare eventuali bug ovvi nell'implementazione dell'IDA.

EDIT: problema risolto, ma ancora cercando di capire una condizione di terminazione quando l'obiettivo non è raggiungibile. Ida* non tiene un elenco di nodi esplorati, quindi come posso sapere se ho coperto l'intero spazio della soluzione?

Answer 1

C'è stato un errore nel modo in cui ho calcolato il nuovo flimit. Non ha causato un problema negli altri casi perché il flusso del successore era tale che non lo ha fatto in giro a loop infinitamente. Anche la condizione dovrebbe f (nodo corrente) <= cutoff. e non '<' come ho preso.

Versione aggiornata:

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

Tuo checkDup La funzione è molto inefficiente. Consiglio di usare un file HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlLa tua funzione ha un costo lineare nelle dimensioni del set, mentre il contains metodo di HashSet ha un costo costante.

Le stringhe in Java vengono confrontate con equals: Java string.equals contro ==

Potrebbero esserci altri problemi, ma questi sono i due più ovvi che ho notato dopo un rapido controllo del tuo codice.