迭代深化搜索Java實現

Question

我一直在嘗試在Java中實現迭代深化搜索。但是，出於某種原因，並非所有的孩子，對於每個節點都正在訪問，導致不正確的結果。這是我到目前爲止的代碼：

public int IDS(Node start, Node goal){ 
     int depth = 0; //set starting depth to 0 
     Node current=start; //current node is equal to start 
     int goalNode=0; //goalNode is originally set to 0 
     //List<Node> tempList=new ArrayList<Node>(); 

     while(goalNode==0){ //while goalNode is equal to 0 
      List<Node> visited=new ArrayList<Node>(); //create an array list of nodes 
      goalNode=DLS(current, goal, depth, visited); 
      depth++; //increment the depth 
     } 
     System.out.println("RESULT"); 
     return goalNode; 
    } 

    public int DLS(Node current, Node goal, int depth, List<Node> visited){ 
     if(depth>=0){ 
      if (current == goal){ //stop program 
       System.out.println("REACHED GOAL"); 
       return current.value; 
      }else{ 
       visited.add(current); //add the current node to visited list (in the beginning =start) 

       List<Node> temp = Adjacency_List.get(current.value); //get children of current node 

       for(Node node: temp){ //for each child 
        System.out.println("Current Node: "+current.value); 
        System.out.println(current.value + " - " + node.value); 
        if(node != null && !visited.contains(node)){ 
         //tempList.add(node); 
         return DLS(node, goal, depth-1, visited); 
        } 
       } 
      } 
     }else{ 
      return 0; 
     } 
     return 0; 
    } 

Answer 1

所以算法，你想實現的是Iterative deepening depth-first search

的DLS方法中的所有代碼的第一行的第一個使得尋找目標狀態的可能性在不可能的最小移動次數中。

您有：

if (depth >= 0) { 
      if (current == goal) { //stop program 
       System.out.println("REACHED GOAL"); 
       return -1; 
      } 

如果電流等於目標狀態，則有望深度將等於0。如果深度大於0但要繼續搜索相鄰節點。

此外，我不確定爲什麼你返回一個int，如果你返回Node對象會更有意義，如果它不等於目標返回null。

DLS：

public Node DLS(Node current, int depth) { 
     if (depth == 0 && current == goal) { 
      return current; 
     } 
     if (depth > 0) { 
      for (Node child : current.findNeighbours()) { 
       Node found = DLS(child, depth - 1); 
       if (found != null) { 
        return found; 
       } 
      } 
     } 
     return null; 
    } 

IDS的方法：

public Node IDS(Node root) { 
     // loops through until a goal node is found 
     for (int depth = 0; depth < Integer.MAX_VALUE; depth++) { 
      Node found = DLS(root, depth); 
      if (found != null) { 
       return found; 
      } 
     } 
     // this will never be reached as it 
     // loops forever until goal is found 
     return null; 
    } 

總體來說，你是不是太離譜的答案，我只要你將不得不更新findNeighbours（）到用於查找相鄰節點的代碼。我的例子使用一個局部變量作爲目標狀態，它是一個節點對象，當然，如果你願意的話，你可以將它作爲參數傳遞。

你可以看到，這是繼僞非常密切：

function IDDFS(root) 
    for depth from 0 to ∞ 
     found ← DLS(root, depth) 
     if found ≠ null 
      return found 

function DLS(node, depth) 
    if depth = 0 and node is a goal 
     return node 
    if depth > 0 
     foreach child of node 
      found ← DLS(child, depth−1) 
      if found ≠ null 
       return found 
    return null 

旁註：

我會建議將使用IDAstar algorithm

其中f(node) = g(node) + h(node)：

g(node)：移動到達的次數Ë當前節點從起始節點

h(node)：有多少移動的估計要達到的目標狀態