mcstate.cs

c#实现的传教士野人过算法。这是一个框架

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

namespace AIShow
{
    class MCState:State
    {
        //操作算子
        private class opMeta
        {
            public int m;
            public int c;
            public bool isLegal()
            {
                if ((m == 0) && (c == 0)) return false;//没有人
                if ((m < c) && (m != 0)) return false;//传教士<野人，并且有传教士 
                if ((m + c) > 2) return false;
                return true;
            }
            public bool isEqual(opMeta op)
            {
                if (op == null) return false;
                if (m != op.m) return false;
                if (c != op.c) return false;
                return true;
            }
        }
        //记录到达这一步的操作算子
        private opMeta opMetaToCurrentState; 
        //合法的操作算子,因为是静态成员，做一次生成就可以了
        private static ArrayList opMetas;
        
        public int m;//传教士数量
        public int c;//野人数量
        public int b;//=1船在左岸,=0船在右岸
        public override bool isEqual(State s)
        {
            if (m != (s as MCState).m) return false;
            if (c != (s as MCState).c) return false;
            if (b != (s as MCState).b) return false;
            return true;
            
        }
        //生成操作算子;
        public static int produceOpMetas()
        {
            MCState.opMetas = new ArrayList();
            opMeta op ;
            for (int m = 0; m <= 2; m++)
                for (int c = 0; c <= 2; c++)
                {
                    op = new opMeta();
                    op.m = m;
                    op.c = c;
                    if (op.isLegal())
                        MCState.opMetas.Add(op);
                }
            return MCState.opMetas.Count;
            

        }
        public override ArrayList expandChild()
        {
            ArrayList child = new ArrayList();
            MCState s;
            foreach (opMeta op in MCState.opMetas)
            {
                //产生一个子状态
                //如果操作算子和当前这个状态的操作算子相同，则抛弃，以防止活塞运动
                if (op.isEqual(this.opMetaToCurrentState))
                    continue;
                s = new MCState();
                s.opMetaToCurrentState = op;
                if (b == 1)
                {
                    s.m = this.m - op.m;
                    s.c = this.c - op.c;
                    s.b = 0;

                }
                else
                {
                    s.m = this.m + op.m;
                    s.c = this.c + op.c;
                    s.b = 1;
 
                }
              
               
                //判断是否合法,这个应该放到产生合法的操作算子上去做(不过又好像不符合面向对象的规则 )
                
                if (s.isLegal() == false)
                    continue;

                               
                //合法则添加到child，否则抛弃
                child.Add(s);
 
            }
            return child;
        }
        public override bool isLegal()
        {
            if (m < 0) return false;
            if (c < 0) return false;
            //当前状态m<c,m!=0为不合法
            if ((m < c) && (m != 0)) return false;
            //对岸3-m<3-c,3-m!=0为不合法
            if (((3 - m )<( 3 - c)) && ((3 - m) != 0)) return false;

            return true;
        }
        public override string description
        {
            get
            {
                return m.ToString() + "," + c.ToString() + "," + b.ToString();
            }
            
        }
        public override string description2
        {
            get
            {
                if(opMetaToCurrentState==null)
                    return m.ToString() + "," + c.ToString() + "," + b.ToString()+"(--)" ;//开始节点

                return  m.ToString() + "," + c.ToString() + "," + b.ToString()+"("+opMetaToCurrentState.m+opMetaToCurrentState.c+")";
            }

        }
        
        
    }
}