غير قادر على تحديد ما إذا كان تنفيذ IDA* يحتوي على خطأ أو غير فعال فقط

Question

لقد قمت بتطبيق البحث التكراري A-Star (لمشكلة 8-puzzle ، ولكن يمكن أن تقبل المشكلات الأخرى) وتشغيله على مدخلات. ركض دون جدوى لمدة 2 ساعة. للحصول على مدخلات أبسط قريبة من عقدة الهدف ، فهي تعمل بشكل جيد. لقد جعلها الآخرون يعملون في هذا المدخلات. لست متأكدًا مما إذا كان تنفيذي غير فعال أو يذهب إلى حلقة لا حصر لها

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

baszlesolver.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 لأنني متأكد تمامًا من أنها تعمل بعد تشغيل خوارزميات البحث الأخرى مثل الأفضل الأول ، DFS. من الصعب توفير SCCE ، لذلك أنا فقط أطلب المساعدة في اكتشاف أي أخطاء واضحة في تطبيق IDA.

تحرير: حل المشكلة ، ولكن لا تزال تحاول معرفة حالة الإنهاء عندما لا يمكن الوصول إلى الهدف. IDA* لا يحتفظ بقائمة من العقد التي تم استكشافها ، فكيف يمكنني معرفة ما إذا كنت قد غطيت مساحة الحل بالكامل؟

Answer 1

كان هناك خطأ في الطريقة التي حسبت بها 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 الوظيفة غير فعالة للغاية. أوصي باستخدام أ HashSet: http://docs.oracle.com/javase/7/docs/api/java/util/hashset.htmlوظيفتك لها تكلفة خطي في حجم المجموعة ، بينما contains طريقة HashSet له تكلفة ثابتة.

تتم مقارنة السلاسل في جافا مع equals: java string.equals مقابل ==

قد تكون هناك مشاكل أخرى ، ولكن هاتان أكثر المشكلات وضوحا التي رصدتها بعد فحص سريع للرمز الخاص بك.