Блог

Я изучал алгоритмы поиска и хотел решить проблему миссионеров и каннибалов, чтобы попрактиковаться. Однако мой код никогда не предоставляет решения. Сначала я подумал, что это потому, что у меня повторяющиеся состояния, вызывающие бесконечный цикл, поэтому я добавил историю состояний, чтобы убедиться, что состояния не повторяются. Однако это все еще не сработало.

Ниже приведен код, который я написал. Я использую векторы для представления состояний миссионеров, каннибалов и лодки, и дочерние элементы узлов добавляются, если они проходят проверку, которая проверяет, находится ли перемещение в пределах диапазона (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) amp;amp; (c == p.c) amp;amp; (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) и получаю исключение OutOfMemoryException на отметке в 2 гигабайта, поэтому я даже не уверен, что больше отслеживаю историю.

Какие шаги я должен предпринять, чтобы правильно реализовать DFS в контексте проблемы, учитывая приведенный выше код?

Ваш алгоритм в порядке. Проблема в том, что вы использовали == operator в curNode.State == new Vector3(0, 0, 0); строке. В C # по умолчанию == объекты сравниваются по ссылке, поэтому это условие всегда возвращает false . node.State.Equals(new Vector3(0, 0, 0)) == Для использования вашего метода используйте или переопределите operator Equals .

См. Рекомендации MSDN по пользовательскому сравнению в C #.