No se puede determinar si mi implementación de IDA* tiene un error o es simplemente ineficiente

Question

Implementé la búsqueda iterativa de profundización A-Star (para el problema del 8 ropzones, pero puedo aceptar otros problemas) y la ejecuté en una entrada. Funcionó sin éxito durante 2 horas. Para entradas más simples que están cerca del nodo objetivo, funciona bien. Otros lo han hecho funcionar para esta entrada. No estoy seguro de si mi implementación es ineficiente o entra en un bucle 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;
}

Estado de inicio (fallido):

1 2 3 
8 - 4
7 6 5

Estado de gol:

1 3 4 
8 6 2 
7 - 5

(Funcionó para 1 3 4 8 6 0 7 5 2) No he incluido Node.java porque estoy bastante seguro de que funciona después de ejecutar otros algoritmos de búsqueda como Best-First, DFS. Es difícil proporcionar un SCCE, por lo que solo estoy pidiendo ayuda para detectar cualquier error obvio en la implementación de IDA.

Editar: problema resuelto, pero aún intenta encontrar una condición de terminación cuando el objetivo no es accesible. IDA* no mantiene una lista de nodos explorados, entonces, ¿cómo puedo saber si he cubierto todo el espacio de la solución?

Answer 1

Hubo un error en la forma en que calculé el nuevo flimit. No causó un problema en los otros casos porque el onza del sucesor era tal que no hacía que elojara infinitamente. Además, la condición debe F (nodo actual) <= Corte. Y no '<' como tomé.

Versión actualizada:

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

Su checkDup la función es muy ineficiente. Recomiendo usar un HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlSu función tiene un costo lineal en el tamaño del conjunto, mientras que el contains método de HashSet tiene un costo constante.

Las cadenas en Java se comparan con equals: Java string.equals vers ==

Puede haber otros problemas, pero estos son los dos más obvios que vi después de una verificación rápida de su código.