Решение 8-Puzzle с использованием оптимизации DFS - PullRequest
Новая
       28

Решение 8-Puzzle с использованием оптимизации DFS

3 голосов
/ 09 февраля 2012

Я использую Java для решения проблемы 8-Puzzle с использованием DFS.

Вот что я придумал: 

    public static boolean found = false;

        public void solveDepthFirst(EightPuzzle currentState, int lastMove){

            if(currentState.goal()){
                System.out.println(currentState);
                found = true;//to stop DFS when a solution is found (even if not optimal)
                return;
            }

            for(int i=0;i<numMoves;++i){
                if(found) return;

                EightPuzzle e = currentState.move(i);//0 = up, 1 = down, 2 = left, 3= right

                if(!e.equals(currentState) && i != lastMove
                        && !visitedNodes.contains(e.toString())){
                    solveDepthFirst(e, i);  
                }           
                     if(!visitedNodes.contains(currentState.toString())){
                visitedNodes.add(currentState.toString());
                     }
            }
        }

! E.equals (currentState) проверяет, возможно ли перемещение.(если currentState.move (i) выходит за границы, move () возвращает то же состояние)

i! = lastMove гарантирует, что если при последнем перемещении вы двигались вправо, вы не двигаетесь влево сейчасэто не имеет смысла)

visitNodes - это HashSet посещенных узлов.

Недостаточно места в стеке.Когда я использую -xss10m для увеличения стекового пространства с 128k до 10m, алгоритм работает отлично.Однако я уверен, что есть масса других оптимизаций, которые можно сделать.

любые советы будут с благодарностью.

Ответы [ 2 ]

1 голос
/ 09 февраля 2012

Прежде всего вы можете сделать стек вместо рекурсивного вызова. Добавьте lastMove в класс EightPuzzle.

Вот что вы получаете: 

// Queue<EightPuzzle> queue = new PriorityQueue<EightPuzzle>();
Stack<EightPuzzle> stack = new Stack<EightPuzzle>();

public void solveDepthFirst() {

    while (true) {
        EightPuzzle currentState = stack.pop(); // queue.poll();
        if (currentState.goal()) {
            System.out.println(currentState);
            found = true;// to stop DFS when a solution is found (even if
                            // not
                            // optimal)
            return;
        }

        for (int i = 0; i < 4; ++i) {
            if (found)
                return;

            EightPuzzle e = currentState.move(i);// 0 = up, 1 = down, 2 =
                                                    // left,
                                                    // 3= right

            if (!e.equals(currentState) && i != currentState.getLastMove()
                    && !visitedNodes.contains(e)) {
                stack.push(e); // queue.add(e);
            }
            if (!visitedNodes.contains(currentState.toString())) {
                visitedNodes.add(currentState);
            }
        }
    }
}

Производительность значительно падает при использовании рекурсивных вызовов вместо итеративного проектирования.

После этого вы можете дополнительно оптимизировать (но это не будет настоящая DFS) с помощью PriorityQueue. Эвристика для использования может быть Манхэттенским расстоянием. Таким образом, решение, которое нужно найти первым, является ближайшим к цели. Это более эффективный, но не строгий DFS.

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/PriorityQueue.html

1 голос
/ 09 февраля 2012

Я думаю, что вы можете значительно ускорить свой поиск, отметив состояние посещения, прежде чем продолжить с рекурсивным вызовом. Кроме этого, для этой головоломки не слишком много оптимизаций: вам просто нужно попробовать все возможные ходы.

...