mcstate.java

用java实现的传教士-野人过河问题算法

package AI;

import java.util.*;

/*
 * 状态类
 */
public class MCState
{
	public int weight;//权值 
	public int m,c,b;//m=传教士，c=野人，b=0无船，b=1有船
	public ArrayList<MCOperationMeta> OperaionMetas;//所有操作算子
	public MCState PrevState ;//上级节点,用于回溯
	public ArrayList<MCState> NextState ;//下级节点
	public MCOperationMeta opMeta;//到达这一步的操作算子
	public HashSet<MCOperationMeta> opMetasUnused;//当前节点还没有尝试的操作算子集合
	////生成操作算子 这个方法和上面的OperaionMetas字段，适合单独搞一个类，并且用属性的概念来做
	
	public MCState()
	{
		weight=0;
		NextState=new ArrayList<MCState>();
		opMetasUnused=new HashSet<MCOperationMeta>();
		
	}
	public void AddWeight(int w)
	{
		//找到成功路径则给可行的节点加权，权值加w;
		if(w==0)//=0可以不执行操作
			return;
		MCState s;
		s=this.PrevState;
		while(s!=null)
		{
			s.weight +=w;
			s=s.PrevState ;
		}
		
		
	}
	//状态相等判断
	public boolean equals(MCState s)
	{
		if(this.m!=s.m)return false;
		if(this.c!=s.c)return false;
		if(this.b!=s.b)return false;
		
		return true;
		
	}
	//生成可用的操作算子 
	public int CreateOperationMetas()
	{
	    if(this.OperaionMetas==null)
	    	return 0;
		for(int i=0;i<this.OperaionMetas.size();i++)
	    {
	    	opMetasUnused.add(this.OperaionMetas.get(i));
	    }
	  //到达这一点的操作算子不能再使用
	    opMetasUnused.remove(opMeta);
	  //无法完成的操作算子不能使用,3-m 3-c 为右岸状态 
	    MCOperationMeta op;
	    Iterator<MCOperationMeta> iter=opMetasUnused.iterator() ;
	    while(iter.hasNext())
    	{
	    	op=iter.next();
	    	if(b==1)//在左岸,操作算子不能大于m&c
	 	    {
	 	    	if((op.m>this.m)||(op.c>this.c))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    	}
	 	    	//并且移动后左岸的m>=c,或者m=0
	 	    	if(((this.m-op.m)!=0)&&((this.m-op.m)<(this.c-op.c)))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    	}
	 	    	//并且移动后右岸的m>=c,或者m=0
	 	    	if((3-this.m+op.m!=0)&&((3-this.m+op.m)<(3-this.c+op.c)))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    	}
	 	    	
	 	    }
	 	    else
	 	    {
	 	    	
	 	    	//在右岸,操作算子不能大于3-m&3-c
	 	    	if((3-this.m<op.m)||(3-this.c<op.c))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    		
	 	    	}
	 	    	//并且移动后左岸的m>=c,或者m=0
	 	    	if(((this.m+op.m)!=0)&&((this.m+op.m)<(this.c+op.c)))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    	}
	 	    	//并且移动后右岸的m>=c,或者m=0
	 	    	if((3-this.m-op.m!=0)&&((3-this.m-op.m)<(3-this.c-op.c)))
	 	    	{
	 	    		opMetasUnused.remove(op);
	 	    		iter=opMetasUnused.iterator();
	 	    	}
	 	    }
	    	 
    		
    	}
	   
	    
	    return opMetasUnused.size();
	}
	 
	//规则定义 
	public boolean isLegalState()
	{
		if((m<c)&&(m!=0)) return false;
		return true;
	}
	public boolean isStartState()
	{
		if(m==3&&c==3&&b==1)
			return true;
		else
			return false;
	}
	public boolean isEndState()
	{
		if(m==0&&c==0&&b==0)
			return true;
		else
			return false;
				
				
	}
	//进行操作，产生下一个状态点
	public MCState takeOperation()
	{
		
		//操作算子都用过了,则返回空;
		if(opMetasUnused.isEmpty())
			return null;
		MCState s;
		s=new MCState();
		//获得一个操作算子
		s.opMeta=opMetasUnused.iterator().next();
		//从当前状态的可用算子中移去这个算子
		opMetasUnused.remove(s.opMeta);
		//如果有船则开过去
		if(this.b==1)
		{
		s.m=this.m-s.opMeta.m ;
		s.c=this.c-s.opMeta.c;
		s.b=0;
		}
		else//没船则开过来
		{
			s.m=this.m+s.opMeta.m ;
			s.c=this.c+s.opMeta.c;
			s.b=1;
		}
		s.OperaionMetas=this.OperaionMetas ;
		s.CreateOperationMetas();
		s.PrevState=this;
		return s;
		
	}
}