Java решение 15 задач с итеративным углубленным поиском - PullRequest
Новая
       29

Java решение 15 задач с итеративным углубленным поиском

1 голос
/ 14 апреля 2020

Я пытаюсь решить 15-головоломку (скользящую мозаику) с помощью итеративного углубленного поиска. Это мое начальное состояние: 

1 2 12 13
5 6 7 8
9 3 4 0
11 14 15 10

И это мое целевое состояние: 

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

У меня есть класс узла для представления моего состояния. Этот класс выглядит следующим образом: 

    public List<Node> children = new LinkedList<Node>(); 
    public Node parent; 
    public static final int size = 4;
    public int[][] puzzle = new int[size][size];
    public int depth = 0;

И это моя функция идентификаторов (итеративный поиск с расширением): 

public List<Node> ids(Node root)
    {
        List<Node> path = new LinkedList<Node>(); //holds the path to the goal
        //priority by depth
        PriorityQueue<Node> queue = new PriorityQueue<Node>(20, new  Comparator<Node>() {
                    public int compare(Node n1, Node n2) {
                        int depth1 = n1.depth;
                        int depth2 = n2.depth;
                        return depth1-depth2;
                    }
                }); 
        List<Node> expendList = new LinkedList<Node>();
        List<Node> expended = new LinkedList<Node>();
        int limit = 0;
        boolean goal = false, flag = false;
        while(!goal)
        {
            queue.add(root);
            Node current = queue.poll();
            if(current.isGoal())
            {
                goal = true;
                //trace path to root node
                pathTrace(path, current);
            }
            expended.add(current); //expend the current node
            int depth = current.getDepth();
            if(depth < limit)
            {
                current.expend();
                for(int i=0; i<current.children.size(); i++)
                {
                    Node child = current.children.get(i);
                    if(child.isGoal())
                    {
                        goal = true;
                        pathTrace(path,child);
                    }
                    expendList.addAll(queue);
                    //if the children aren't already in the queue, add them to the queue
                    if(!contains(expendList,child) && !contains(expended,child))
                    {
                        child.setDepth(depth+1);
                        queue.add(child);
                    }
                }
            }
            else if(depth >= limit && !flag)
            {
                if(queue.isEmpty())
                {
                    limit++;
                    expended.clear();
                    expendList.clear();
                    flag = true;
                }
                else
                {
                    Node node = queue.poll();
                    if(node.isGoal())
                    {
                        goal = true;
                        flag = true;
                        //trace path to root node
                        pathTrace(path, node);
                    }
                }
            }
        }
        return path;
    }

Я не знаю почему, но функция застряла в то время l oop когда глубина = 1 и предел = 1. Я не понимаю, почему он не может достичь цели.

...