鸟语天空

妖怪与和尚过河问题

作者：追风剑情 发布于：2015-11-5 21:20 分类：Algorithms

      有三个妖怪和三个和尚要利用唯一一条小船过河，这条小船每次至少载一个人最多载两个人，无论是在河的两岸还是在船上，只要妖怪的数量大于和尚的数量，妖怪们就会将和尚吃掉。现在需要选择一种过河的安排，保证和尚和妖怪都能过河且和尚不能被妖怪吃掉。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MonkTest
{
    class Program
    {
        static void Main(string[] args)
        {
            new AcrossRiver().SearchState();

            Console.Read();
        }
    }
}



/// <summary>
/// 过河问题求解类
/// 思路: 把抽象问题转化成计算能处理的数学模型
/// 算法原理：利用状态树求解 (采用深度优先搜索)
/// 效率优化: 采用剪枝、去重
/// </summary>
public class AcrossRiver
{
    //过河动作枚举
    private enum ActionName
    {
        //一个妖怪过河
        ONE_MONSTER_GO,
        //两个妖怪过河
        TWO_MONSTER_GO,
        //一个和尚过河
        ONE_MONK_GO,
        //两个和尚过河
        TWO_MONK_GO,
        //一个妖怪和一个和尚过河
        ONE_MONSTER_ONE_MONK_GO,
        //一个妖怪返回
        ONE_MONSTER_BACK,
        //两个妖怪返回
        TWO_MONSTER_BACK,
        //一个和尚返回
        ONE_MONK_BACK,
        //两个和尚返回
        TWO_MONK_BACK,
        //一个妖怪和一个和尚返回
        ONE_MONSTER_ONE_MONK_BACK
    };

    //船的行使方向枚举
    private enum BoatLocation
    {
        REMOTE, //对岸
        LOCAL   //本岸
    }

    //过河动作数学模型
    private class ActionEffection
    {
        public ActionName act;
        public BoatLocation boat_to;//船移动的方向
        public int move_monster;//此次移动的妖怪数量
        public int move_monk;//此次移动的和尚数量

        public ActionEffection(ActionName act, BoatLocation boat_to, int move_monster, int move_monk)
        {
            this.act = act;
            this.boat_to = boat_to;
            this.move_monster = move_monster;
            this.move_monk = move_monk;
        }
    }

    private class ItemState
    {
        public int local_monster = 3;
        public int local_monk = 3;
        public int remote_monster = 0;
        public int remote_monk = 0;
        public BoatLocation boat = BoatLocation.LOCAL;
        public ActionName curAct;

        public const int MAX_MONSTER_COUNT = 3;
        public const int MAX_MONK_COUNT = 3;

        //此方法用于剪枝
        public bool CanTakeAction(ActionEffection ae)
        {
            if (boat == ae.boat_to)
                return false;

            int local_move_monster = local_monster + ae.move_monster;
            int local_move_monk = local_monk + ae.move_monk;
            int remote_move_monster = remote_monster - ae.move_monster;
            int remote_move_monk = remote_monk - ae.move_monk;
            //数量判断
            if (local_move_monster < 0 || local_move_monster > MAX_MONSTER_COUNT)
                return false;
            if (local_move_monk < 0 || local_move_monk > MAX_MONK_COUNT)
                return false;

            return true;
        }

        //判断当前状态是否为最终状态
        public bool IsFinalState()
        {
            if (remote_monster == MAX_MONSTER_COUNT && remote_monk == MAX_MONK_COUNT)
                return true;
            return false;
        }

        //判断是否为有效状态
        public bool IsValidState()
        {
            //如果妖怪数量>=和尚数量，则和尚会被吃掉。
            if ((local_monk > 0 && local_monster > local_monk) || (remote_monk > 0 && remote_monster > remote_monk))
                return false;
            return true;
        }

        public override string ToString()
        {
            string s = string.Format("{0}_{1}_{2}_{3}_{4}", boat, local_monster, local_monk, remote_monster, remote_monk);
            return s;
        }

        public ItemState Clone()
        {
            ItemState state = new ItemState();
            state.local_monster = local_monster;
            state.local_monk = local_monk;
            state.remote_monster = remote_monster;
            state.remote_monk = remote_monk;
            state.boat = boat;
            state.curAct = curAct;

            return state;
        }
    }

    //过河动作列表
    private ActionEffection[] actEffect = new ActionEffection[10];

    private StateStack states = new StateStack();

    private ItemState last_local_state = null;

    public AcrossRiver()
    {
        //初始化10种过河动作
        actEffect[0] = new ActionEffection(ActionName.ONE_MONSTER_GO,   BoatLocation.REMOTE, -1,  0);
        actEffect[1] = new ActionEffection(ActionName.TWO_MONSTER_GO,   BoatLocation.REMOTE, -2,  0);
        actEffect[2] = new ActionEffection(ActionName.ONE_MONK_GO,      BoatLocation.REMOTE,  0, -1);
        actEffect[3] = new ActionEffection(ActionName.TWO_MONK_GO,      BoatLocation.REMOTE,  0, -2);
        actEffect[4] = new ActionEffection(ActionName.ONE_MONSTER_ONE_MONK_GO, BoatLocation.REMOTE, -1, -1);
        actEffect[5] = new ActionEffection(ActionName.ONE_MONSTER_BACK, BoatLocation.LOCAL, 1, 0);
        actEffect[6] = new ActionEffection(ActionName.TWO_MONSTER_BACK, BoatLocation.LOCAL, 2, 0);
        actEffect[7] = new ActionEffection(ActionName.ONE_MONK_BACK,    BoatLocation.LOCAL, 0, 1);
        actEffect[8] = new ActionEffection(ActionName.TWO_MONK_BACK,    BoatLocation.LOCAL, 0, 2);
        actEffect[9] = new ActionEffection(ActionName.ONE_MONSTER_ONE_MONK_BACK, BoatLocation.LOCAL, 1, 1);

        //初始化栈
        states.Push(new ItemState());
    }

    public void SearchState()
    {
        ItemState current = states.Back();
        if (null == current)
            return;

        if (current.IsFinalState())
        {
            states.PrintStack();
            return;
        }
        
        //尝试用10种动作分别与当前状态组合
        for (int i = 0; i < actEffect.Length; i++)
        {
            SearchStateOnNewAction(current, actEffect[i]);
        }
    }

    private void SearchStateOnNewAction(ItemState current, ActionEffection ae)
    {
        ItemState nextState = MakeActionNewState(current, ae);
        
        if (null != nextState)
        {
            if (nextState.IsValidState() && !states.IsProcessedState(nextState))
            {
                states.Push(nextState);
                SearchState();
                states.Pop();
            }
        }
    }

    private ItemState MakeActionNewState(ItemState curState, ActionEffection ae)
    {
        ItemState newState = null;

        if (null == last_local_state)
        {
            last_local_state = curState;
        }

        if (curState.CanTakeAction(ae))
        {
            newState = curState.Clone();
            newState.local_monster += ae.move_monster;
            newState.local_monk += ae.move_monk;
            newState.remote_monster -= ae.move_monster;
            newState.remote_monk -= ae.move_monk;
            newState.boat = ae.boat_to;
            newState.curAct = ae.act;
        }

        return newState;
    }

    /// <summary>
    /// 状态栈
    /// </summary>
    private class StateStack
    {
        private List<ItemState> list = new List<ItemState>();
        private Dictionary<string, bool> dic = new Dictionary<string, bool>();
        private int way = 1;

        public ItemState Back()
        {
            ItemState state = null;
            if (list.Count > 0)
            {
                state = list[list.Count - 1];
            }
            return state;
        }

        public void Push(ItemState state)
        {
            string key = state.ToString();
            if (dic.ContainsKey(key))
                return;

            dic.Add(key, true);
            list.Add(state);
        }

        public void Pop()
        {
            if (list.Count > 0)
            {
                ItemState state = list[list.Count - 1];
                list.RemoveAt(list.Count - 1);
                dic.Remove(state.ToString());
            }
        }

        public void Clear()
        {
            list.Clear();
            dic.Clear();
            way = 1;
        }

        //判断是否为已搜索过的状态(即，去重)
        public bool IsProcessedState(ItemState state)
        {
            return dic.ContainsKey(state.ToString());
        }

        public void PrintStack()
        {
            Console.WriteLine("方案: {0}  ({1}步)", way++, list.Count);
            ItemState state = null;
            for (int i = 0; i < list.Count; i++)
            {
                state = list[i];
                Console.WriteLine("{0} ({1}, {2}, {3}, {4})", 
                    state.curAct, state.local_monster, state.local_monk, state.remote_monster, state.remote_monk);
            }
            Console.WriteLine("end");
        }
    }
}

运行效果:

标签: Algorithms