Impossible de déterminer si mon implémentation IDA * a un bug ou est tout simplement inefficace

Question

J'ai mis en œuvre la recherche itérative d'approfondissement A-star (pour le problème à 8 puzzle, mais je peux accepter d'autres problèmes) et je l'ai exécuté sur une entrée. Il a fonctionné sans succès pendant 2 heures. Pour les entrées plus simples qui sont proches du nœud d'objectif, cela fonctionne bien. D'autres l'ont fait fonctionner pour cette contribution. Je ne sais pas si ma mise en œuvre est tout simplement inefficace ou va dans une boucle infinie

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

Démarrer l'état (échoué):

1 2 3 
8 - 4
7 6 5

État d'objectif:

1 3 4 
8 6 2 
7 - 5

(Fonctionné pour 1 3 4 8 6 0 7 5 2) Je n'ai pas inclus Node.java car je suis presque sûr que cela fonctionne après avoir exécuté d'autres algorithmes de recherche comme le meilleur, DFS. Il est difficile de fournir un SCCE, donc je demande simplement de l'aide pour repérer tous les bugs évidents dans l'implémentation de l'IDA.

Edit: problème résolu, mais essayant toujours de trouver une condition de terminaison lorsque l'objectif n'est pas accessible. Ida * ne garde pas une liste de nœuds explorés, alors comment puis-je savoir si j'ai couvert l'espace de la solution?

Answer 1

Il y a eu une erreur dans la façon dont j'ai calculé le nouveau flimit. Cela n'a pas causé de problème dans les autres cas parce que le flimit du successeur était tel qu'il ne le faisait pas boucle à l'infini. La condition doit également f (nœud actuel) <= coupure. Et pas '<' comme je l'ai pris.

Version mise à jour:

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

Ton checkDup La fonction est très inefficace. Je recommande d'utiliser un HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlVotre fonction a un coût linéaire dans la taille de l'ensemble, tandis que le contains méthode de HashSet a un coût constant.

Les cordes en java sont comparées à equals: Java string.equals versus ==

Il peut y avoir d'autres problèmes, mais ce sont les deux plus évidents que j'ai repérés après une vérification rapide de votre code.