深度优先搜索永远不会到达目标状态

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＃中的自定义比较。