내 IDA* 구현에 버그가 있는지 확인할 수 없거나 비효율적입니다.

Question

나는 반복적 인 심화 A-star 검색 (8puzzle 문제에 대해서는 다른 문제를 받아 들일 수 있음)을 구현하고 입력에 대해 실행했습니다. 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는 Best-First, DFS와 같은 다른 검색 알고리즘을 실행 한 후 작동한다고 확신하기 때문에 Node.java를 포함하지 않았습니다. SCCE를 제공하는 것은 어렵 기 때문에 IDA 구현에서 명백한 버그를 발견하는 데 도움을 요청하고 있습니다.

편집 : 해결 된 문제이지만 목표에 도달 할 수 없을 때 종료 조건을 파악하려고합니다. IDA*는 탐색 된 노드 목록을 유지하지 않으므로 전체 솔루션 공간을 다루었다면 어떻게 알 수 있습니까?

Answer 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());
    }
}

Answer 2

당신의 checkDup 기능은 매우 비효율적입니다. 나는 a를 사용하는 것이 좋습니다 HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.html당신의 기능은 세트 크기의 비용 선형을 가지고 있으며 contains 의 방법 HashSet 일정한 비용이 있습니다.

자바의 줄은 비교됩니다 equals: Java String.equals 대 ==

다른 문제가있을 수 있지만,이 문제는 코드를 빠르게 확인한 후 내가 발견 한 가장 분명한 두 가지 문제입니다.