使用DFS优化解决8-Puzzle

我正在使用Java解决使用DFS的8-Puzzle问题。使用DFS优化解决8-Puzzle

这是我想出了：

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确保如果在上一步移动中，您向右移动，则不会左移现在（因为它不会不做出反应）

visitedNodes是访问节点的HashSet。

这将耗尽堆栈空间。当我使用-xss10m将堆栈空间从128k增加到10m时，该算法可以正常工作。不过，我相信还有很多其他的优化可以做到。

任何提示将不胜感激。

来源

2012-02-09 Jonny

首先你可以做一个堆栈而不是递归调用。将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); 
      } 
     } 
    } 
}

性能显著下降。

之后，您可以通过使用PriorityQueue进一步优化（但它不会是真正的DFS）。启发式使用可以是曼哈顿距离。这样，首先搜索的解决方案与目标最接近。这是更高效但不严格的DFS。

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

来源

2012-02-09 02:05:53

我认为你可以通过在进行递归调用之前标记访问状态来加速你的搜索。除此之外，这个难题并没有太多的优化：你只需要尝试所有可能的动作。

来源

2012-02-09 01:35:24 dasblinkenlight

使用DFS优化解决8-Puzzle

回答

相关问题