牧师与野人问题求解c#

以下是C#语言实现牧师与野人问题求解的代码和注释：

using System;
using System.Collections.Generic;

namespace MissionariesAndCannibals
{
    class Program
    {
        static void Main(string[] args)
        {
            // 初始化状态
            State initialState = new State(3, 3, true, 0, 0);
            // 初始化搜索树
            SearchTree searchTree = new SearchTree(initialState);
            // 进行搜索
            searchTree.BFS();
        }
    }

    // 表示状态的类
    class State
    {
        public int MissionariesLeft { get; set; } // 左岸传教士数量
        public int CannibalsLeft { get; set; } // 左岸野人数量
        public bool BoatPosition { get; set; } // 船的位置，true表示在左岸，false表示在右岸
        public int MissionariesRight { get; set; } // 右岸传教士数量
        public int CannibalsRight { get; set; } // 右岸野人数量

        // 构造函数
        public State(int missionariesLeft, int cannibalsLeft, bool boatPosition, int missionariesRight, int cannibalsRight)
        {
            MissionariesLeft = missionariesLeft;
            CannibalsLeft = cannibalsLeft;
            BoatPosition = boatPosition;
            MissionariesRight = missionariesRight;
            CannibalsRight = cannibalsRight;
        }

        // 判断状态是否合法
        public bool IsValid()
        {
            if (MissionariesLeft < 0 || CannibalsLeft < 0 || MissionariesRight < 0 || CannibalsRight < 0)
            {
                return false;            }
            if (MissionariesLeft > 3 || CannibalsLeft > 3 || MissionariesRight > 3 || CannibalsRight > 3)
            {
                return false;
            }
            if (CannibalsLeft > MissionariesLeft && MissionariesLeft > 0)
            {
                return false;
            }
            if (CannibalsRight > MissionariesRight && MissionariesRight > 0)
            {
                return false;
            }
            return true;
        }

        // 判断状态是否为目标状态
        public bool IsGoal()
        {
            return MissionariesLeft == 0 && CannibalsLeft == 0;
        }

        // 判断两个状态是否相等
        public override bool Equals(object obj)
        {
            State state = obj as State;
            if (state == null)
            {
                return false;
            }
            return MissionariesLeft == state.MissionariesLeft && CannibalsLeft == state.CannibalsLeft && BoatPosition == state.BoatPosition && MissionariesRight == state.MissionariesRight && CannibalsRight == state.CannibalsRight;
        }

        // 获取状态的哈希值
        public override int GetHashCode()
        {
            return MissionariesLeft * 10000 + CannibalsLeft * 1000 + (BoatPosition ? 100 : 0) + MissionariesRight * 10 + CannibalsRight;
        }

        // 获取状态的字符串表示
        public override string ToString()
        {
            return "MissionariesLeft: " + MissionariesLeft + ", CannibalsLeft: " + CannibalsLeft + ", BoatPosition: " + (BoatPosition ? "Left" : "Right") + ", MissionariesRight: " + MissionariesRight + ", CannibalsRight: " + CannibalsRight;
        }
    }

    // 表示搜索树的类
    class SearchTree
    {
        private State _initialState; // 初始状态
        private Queue<Node> _frontier; // 存放待扩展的节点的队列
        private HashSet<State> _exploredSet; // 存放已扩展过的状态的集合

        // 构造函数
        public SearchTree(State initialState)
        {
            _initialState = initialState;
            _frontier = new Queue<Node>();
            _frontier.Enqueue(new Node(_initialState, null));
            _exploredSet = new HashSet<State>();
        }

        // 广度优先搜索
        public void BFS()
        {
            while (_frontier.Count > 0)
            {
                Node node = _frontier.Dequeue();
                State state = node.State;
                if (state.IsGoal())
                {
                    // 找到了目标状态，输出路径
                    List<State> path = new List<State>();
                    while (node != null)
                    {
                        path.Insert(0, node.State);
                        node = node.Parent;
                    }
                    foreach (State s in path)
                    {
                        Console.WriteLine(s);
                    }
                    return;
                }
                _exploredSet.Add(state);
                List<State> successors = GetSuccessors(state);
                foreach (State successor in successors)
                {
                    if (!_exploredSet.Contains(successor))
                    {
                        _frontier.Enqueue(new Node(successor, node));
                    }
                }
            }
            Console.WriteLine("No solution found.");
        }

        // 获取一个状态的所有合法后继状态
        private List<State> GetSuccessors(State state)
        {
            List<State> successors = new List<State>();
            if (state.BoatPosition)
            {
                // 船在左岸
                for (int i = 0; i <= 2; i++)
                {
                    for (int j = 0; j <= 2; j++)
                    {
                        if (i + j >= 1 && i + j <= 2)
                        {
                            State successor = new State(state.MissionariesLeft - i, state.CannibalsLeft - j, false, state.MissionariesRight + i, state.CannibalsRight + j);
                            if (successor.IsValid())
                            {
                                successors.Add(successor);
                            }
                        }
                    }
                }
            }
            else
            {
                // 船在右岸
                for (int i = 0; i <= 2; i++)
                {
                    for (int j = 0; j <= 2; j++)
                    {
                        if (i + j >= 1 && i + j <= 2)
                        {
                            State successor = new State(state.MissionariesLeft + i, state.CannibalsLeft + j, true, state.MissionariesRight - i, state.CannibalsRight - j);
                            if (successor.IsValid())
                            {
                                successors.Add(successor);
                            }
                        }
                    }
                }
            }
            return successors;
        }
    }

    // 表示搜索树中的节点的类
    class Node
    {
        public State State { get; set; } // 节点对应的状态
        public Node Parent { get; set; } // 父节点

        // 构造函数
        public Node(State state, Node parent)
        {
            State = state;
            Parent = parent;
        }
    }
}