深さ優先探索が目標到達状態に到達しない

Question

私は探索アルゴリズムを研究しており、練習するために問題を解決したいと考えました。しかし、私のコードは決して解決策を提供しません。最初は、私は繰り返し状態があり、無限ループを引き起こしたと考えていたので、州の歴史を追加して、状態が繰り返されていないことを確認しました。しかし、これはまだ機能していません。

以下は私が書いたコードです。私は、移動が範囲（0,0,0）と（3,3）の範囲内にあるかどうかをチェックする小切手を渡すと、宣教師、食堂、ボートの状態を表すベクトルを使用してノードの子が追加されます、1）。

私はコードをステップ実行しようとしましたが、ツリーがかなり大きいので、多くのことを追跡することしかできないので、自分のコードでフォルトを見るのは苦労します。

これはコンソールプログラムとしてVisual Studioで作成されました。

するVector3クラス

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; 
    } 
} 

私のコードは、 'NOソリューションが見つからない' ブロックを打つ保つ

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クラス。履歴を削除すると、状態（3,3,1）と（2,2,1）が無限にループし、2GBのマークでOutOfMemoryExceptionが発生するため、履歴の記録を残しておくことさえできません。

上記のコードで、問題のコンテキストでDFSを正しく実装するためには、どのような手順を取る必要がありますか？

Answer 1

あなたのアルゴリズムは問題ありません。問題は、curNode.State == new Vector3(0, 0, 0);行に==演算子を使用したことです。 C＃では、既定で==が参照によってオブジェクトを比較するため、この条件は常にfalseを返します。 node.State.Equals(new Vector3(0, 0, 0))を使用するか、==演算子をオーバーライドしてEqualsメソッドを使用してください。

MSDN Guidelinesを参照してください。