深度優先搜索永遠不會到達目標狀態

Question

我正在學習搜索算法，並希望解決missionaries and cannibals問題以便練習。但是，我的代碼從未提供解決方案。起初，我認爲這是因爲我有復發狀態，導致無限循環，所以我添加了狀態歷史記錄以確保狀態不被重複。但是，這仍然沒有奏效。

下面是我寫的代碼。我使用矢量來表示傳教士，食人族和船的狀態以及節點的孩子，如果他們通過檢查移動是否在範圍（0,0,0）和（3,3 ，1）。

我試過了代碼，但由於樹相當大，我只能跟蹤很多事情，所以我很難看到代碼中的錯誤。

這是用Visual Studio編寫的控制檯程序。

的Vector3類

public class Vector3 
{ 
    public int m; 
    public int c; 
    public int b; 
    public Vector3(int M, int C, int B) 
    { 
     m = M; 
     c = C; 
     b = B; 
    } 
    public override bool Equals(System.Object obj) 
    { 
     if (obj == null) 
      return false; 

     Vector3 p = obj as Vector3; 
     if ((System.Object)p == null) 
      return false; 

     return (m == p.m) && (c == p.c) && (b == p.b); 
    } 
} 

Node類

public class Node 
{ 
    public Vector3 State; 
    public Node(Vector3 st) 
    { 
     State = st; 
    } 
} 

我的Program.cs

class Program 
{ 
    static void Main(string[] args) 
    { 
     Program p = new Program(); 
     p.DFS(new Node(new Vector3(3, 3, 1))); 
     Console.ReadKey(); 
    } 

    List<Vector3> History = new List<Vector3>(); 
    Vector3[] Operators = new Vector3[] 
    { 
     new Vector3(1,0,1), 
     new Vector3(2,0,1), 
     new Vector3(0,1,1), 
     new Vector3(0,2,1), 
     new Vector3(1,1,1), 
    }; 

    public bool TryMove(Vector3 current, Vector3 toApply, bool substract) 
    { 
     if (substract) 
     { 
      if (current.c - toApply.c < 0 || current.m - toApply.m < 0 || current.b - toApply.b < 0 || (current.c - toApply.c) > (current.m - toApply.m)) 
      { 
       return false; 
      } 
      else return true; 
     } 
     else 
     { 
      if (current.c + toApply.c > 3 || current.m + toApply.m > 3 || current.b + toApply.b > 1 || (current.c + toApply.c) > (current.m + toApply.m)) 
      { 
       return false; 
      } 
      else return true; 
     } 
    } 
    public void DFS(Node n) 
    { 
     Stack<Node> stack = new Stack<Node>(); 
     stack.Push(n); 
     while (stack.Count > 0) 
     { 

      Node curNode = stack.Pop(); 
      if (History.Contains(curNode.State)) 
      { 

      } 
      else 
      { 
       History.Add(curNode.State); 
       if (curNode.State == new Vector3(0, 0, 0)) 
       { 
        Console.WriteLine("Solution found."); 
        return; 
       } 
       else 
       { 
        if (curNode.State.b == 0) //Boat is across the river 
        { 
         for (int x = 0; x < 5; x++) 
         { 
          if (TryMove(curNode.State, Operators[x], false)) 
          { 
           stack.Push(new Node(new Vector3(curNode.State.m + Operators[x].m, curNode.State.c + Operators[x].c, curNode.State.b + Operators[x].b))); 
          } 
         } 
        } 
        else //Boat == 1 
        { 
         for (int x = 0; x < 5; x++) 
         { 
          if (TryMove(curNode.State, Operators[x], true)) 
          { 
           stack.Push(new Node(new Vector3(curNode.State.m - Operators[x].m, curNode.State.c - Operators[x].c, curNode.State.b - Operators[x].b))); 
          } 
         } 
        } 
       } 
      } 
     } 
     Console.WriteLine("No solution found."); 
     return; 
    } 
} 

我的代碼一直打到 '無解找到' 塊。當我刪除歷史記錄時，我在狀態（3,3,1）和（2,2,1）之間保持無限循環，並在2千兆字節的標記處得到OutOfMemoryException，所以我甚至不知道如何保持歷史記錄。

鑑於上面提供的代碼，我應該如何正確實施DFS問題？

Answer 1

你的算法很好。問題是你在curNode.State == new Vector3(0, 0, 0);行中使用==運算符。在C＃中，默認情況下，==通過引用來比較對象，因此此條件將始終返回false。使用node.State.Equals(new Vector3(0, 0, 0))或覆蓋==運營商使用您的Equals方法。

請參閱MSDN Guidelines關於C＃中的自定義比較。