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

Question

我正在学习搜索算法，想解决传教士和食人族的问题，以便实践。然而，我的代码从来没有提供一个解决方案。起初，我认为这是因为我有反复出现的状态，导致无限循环，所以我添加了一个状态历史记录，以确保状态不会重复。然而，这仍然没有奏效。

下面是我写的代码。我使用向量来表示传教士，食人族和船的状态，如果节点的子节点通过检查，检查移动是否在(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);
    }
}

节点类

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)之间保持无限循环，并在2gb标记处获得OutOfMemoryException，所以我甚至不确定是否继续跟踪历史记录。

考虑到我上面提供的代码，为了在问题的上下文中正确地实现DFS，我应该采取哪些步骤?

Answer 1

你的算法很好。问题是你在curNode.State == new Vector3(0, 0, 0);行中使用了==算子。在c#中，默认情况下，==通过引用比较对象，因此此条件将始终返回false。使用node.State.Equals(new Vector3(0, 0, 0))或覆盖==操作符来使用Equals方法。