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(...)方法中解決。