Java Итеративный углубленный поиск застревает, когда предел = 6 - PullRequest
Новая
       84

Java Итеративный углубленный поиск застревает, когда предел = 6

0 голосов
/ 17 апреля 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>();
    boolean goal = false;
    for(int limit=0; !goal; limit++) {
        path = dfs(root,limit);
        if(!path.isEmpty())
            goal = true;
    }
    return path;
}

public List<Node> dfs(Node root, int limit) {
    List<Node> path = new LinkedList<Node>();
    PriorityQueue<Node> queue = new PriorityQueue<Node>(10000, new  Comparator<Node>() {
        public int compare(Node n1, Node n2) {
            int depth1 = n1.depth;
            int depth2 = n2.depth;
            if(depth1 > depth2)
                return 1;
            else if(depth1 < depth2)
                return -1;
            return Node.comparePuzzle(n1.puzzle, n2.puzzle);
        }
    });
    List<Node> expendList = new LinkedList<Node>();
    List<Node> expended = new LinkedList<Node>();
    queue.add(root); 
    boolean goal = false;
    while(!queue.isEmpty() && !goal) {
        Node temp = queue.poll();
        expended.add(temp);
        if(!temp.isGoal()) {
            temp.expend();
            for(int i=0; i<temp.children.size(); i++) {
                Node child = temp.children.get(i);
                child.setDepth(temp.getDepth() + 1);
                expendList.addAll(queue);
                if(!contains(expendList,child) && !contains(expended,child) && child.depth < limit)
                {
                    queue.add(child);
                }
            }
        } else {
            goal = true;
            pathTrace(path,temp);
        }
    }
    return path;
}

Состояние цели находится в глубине 9 дерева поиска, но моя функция застревает в пределе 6 и я не знаю почему. Когда цель находится на глубине 6 или менее, функция находит решение, но когда глубина превышает 6, функция выполняется много времени и застревает.

...