Java - 用节点迭代加深搜索

Question

我正在设计一个程序，它是用来搜索一个二维数组数组，这个数组表示一个到指定终点的路径的映射。我一直在使用有几个参数的节点，最显着的是相邻的北，南，东，西节点，每个节点代表地图中的一个正方形。我目前试图完成的搜索方法是迭代加深，但每次我尝试运行程序时，都会遇到堆栈溢出错误。这是反复深化的课程。

import java.util.*; 
import java.io.*; 
public class IDeepeningSearch { 
    private Node start; 
    private Node end; 
    private int[][] map; 
    private ArrayList<Node> solution; 

    //Build using file handler 
    public IDeepeningSearch(String file){ 
     FileHandler handle = new FileHandler(file); 

     //Create map 
     map = handle.getMap(); 

     //Start node coordinates and value 
     start = new Node(); 
     start.setRow(handle.getSRow()); 
     start.setCol(handle.getSCol()); 
     start.setValue(map[start.getRow()][start.getCol()]); 

     //End node coordinates 
     end = new Node(); 
     end.setRow(handle.getERow()); 
     end.setCol(handle.getECol()); 
     end.setValue(map[start.getRow()][start.getCol()]); 
    } 

    //Runs search 
    public void run(){ 
     int i = 0; 
     solution = new ArrayList<Node>(); 
     //Value of i indicates depth to be explored; will increment with each failure 
     while(solution.isEmpty()){ 
      search(start, i); 
      i++; 
     } 
     if(!solution.isEmpty()){ 
      System.out.println("It worked."); 
     } 
     System.out.println("If you're not seeing the other message then it failed."); 
    } 

    //Building tree 
    public void build(Node head){ 
     setNLeaf(head); 
     setSLeaf(head); 
     setELeaf(head); 
     setWLeaf(head); 
//  if(head.getNorth() != null){ 
//   build(head.getNorth()); 
//  } 
//  if(head.getSouth() != null){ 
//   build(head.getSouth()); 
//  } 
//  if(head.getEast() != null){ 
//   build(head.getEast()); 
//  } 
//  if(head.getWest() != null){ 
//   build(head.getWest()); 
//  } 
    } 

    //Performs search 
    public void search(Node head, int depth){ 
     if(head.getRow() == end.getRow() && head.getCol() == end.getCol()){ 
      solution.add(head); 
      return; 
     } 
     else{ 
      if(depth == 0){ 
       return; 
      } 
      build(head); 
      if(head.getNorth() != null){ 
       search(head.getNorth(), depth--); 
      } 
      if(head.getSouth() != null){ 
       search(head.getSouth(), depth--); 
      } 
      if(head.getEast() != null){ 
       search(head.getEast(), depth--); 
      } 
      if(head.getWest() != null){ 
       search(head.getWest(), depth--); 
      } 
     } 
    } 

    //Sets north leaf 
    public void setNLeaf(Node node){ 
     //Determines if parent is on edge of map and if desired space has 0 value 
     if(node.getRow() != 0 && map[node.getRow() - 1][node.getCol()] != 0){ 
      Node n = new Node(); 
      n.setRow(node.getRow() - 1); 
      n.setCol(node.getCol()); 
      n.setValue(map[n.getRow()][n.getCol()]); 
      n.setParent(node); 
      node.setNorth(n); 
     } 
    } 

    //Sets south leaf 
    public void setSLeaf(Node node){ 
     //Determines if parent is on edge of map and if desired space has 0 value 
     if(node.getRow() != (map.length - 1) && map[node.getRow() + 1][node.getCol()] != 0){ 
      Node n = new Node(); 
      n.setRow(node.getRow() + 1); 
      n.setCol(node.getCol()); 
      n.setValue(map[n.getRow()][n.getCol()]); 
      n.setParent(node); 
      node.setSouth(n); 
     } 
    } 

    //Sets east leaf 
    public void setELeaf(Node node){ 
     //Determines if parent is on edge of map and if desired space has 0 value 
     if(node.getRow() != (map[0].length - 1) && map[node.getRow()][node.getCol() + 1] != 0){ 
      Node n = new Node(); 
      n.setRow(node.getRow()); 
      n.setCol(node.getCol() + 1); 
      n.setValue(map[n.getRow()][n.getCol()]); 
      n.setParent(node); 
      node.setEast(n); 
     } 
    } 

    //Sets west leaf 
    public void setWLeaf(Node node){ 
     //Determines if parent is on edge of map and if desired space has 0 value 
     if(node.getCol() != 0 && map[node.getRow()][node.getCol() - 1] != 0){ 
      Node n = new Node(); 
      n.setRow(node.getRow()); 
      n.setCol(node.getCol() - 1); 
      n.setValue(map[n.getRow()][n.getCol()]); 
      n.setParent(node); 
      node.setWest(n); 
     } 
    } 
} 

我以为我正确地做了这件事，但我得到的错误一直都很稳定。这就是我所期待的。

Exception in thread "main" java.lang.StackOverflowError 
at Node.setSouth(Node.java:88) 
at IDeepeningSearch.setSLeaf(IDeepeningSearch.java:113) 
at IDeepeningSearch.build(IDeepeningSearch.java:48) 
at IDeepeningSearch.search(IDeepeningSearch.java:75) 
at IDeepeningSearch.search(IDeepeningSearch.java:77) 
at IDeepeningSearch.search(IDeepeningSearch.java:80) 
at IDeepeningSearch.search(IDeepeningSearch.java:77) 

重复倒数第二行和最后一行。我试着建立一个完整的树，但是要么给我另一个堆栈溢出错误或空指针异常。我不确定这里有什么问题，但如果我能解决这个问题，我相信我也可以完成我的广度优先搜索方法。

Answer 1

depth--评估为原始值depth。这意味着将depth的未修改版本传递给递归调用search()，因此您的代码永远不会接近基本情况。改为尝试depth-1。或者，如果需要改变局部变量深度的值，--depth。

例如，这将持续打印10，直到它达到堆栈溢出

public void foo(int x) { 
    if (x == 0) { 
     return; 
    } 
    System.out.println(x); 
    foo(x--); 
} 

foo(10); 

Answer 2

的StackOverflowError是因为search(node, depth--)有缺陷的递归调用的克里斯上升他的答案已经提到。尝试--depth来解决这个问题。

此代码中的内存管理也很差，这会浪费堆内存，因为多次调用GC（垃圾收集器）或导致OutOfMemeoryError！这个问题是在setXLeaf(Node n)方法可见（如setNLeaf(Node north)等），每一个你正在创建一个new Node，而这是可以做到只有当有必要用一个简单的检查时间：

if (node.getSouth() == null) { 
    Node n = new Node(); 
    n.setParent(node); 
    node.setSouth(n); 
} 
node.getSouth().setRow(node.getRow() + 1); 
node.getSouth().setCol(node.getCol()); 
node.getSouth().setValue(map[node.getRow() + 1][node.getCol()]); 

这样，您将避免创建新的对象是不必要的。这应该在所有setXLeaf(...)方法中解决。