missionariesandcannibals.java

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

package AI;
import java.util.ArrayList;
import AI.*;
import java.io.*;
/*
 * 传教士和野人问题-状态空间及搜索的例子
 * 题目：三个修道士和三个野人过河，船一次最多只能载两个人，
 * 在任何时候修道士的人数不能少于野人人数，否则野人会吃掉修道士。
 * 找出六个人顺利过河的所有方案。 
 */
public class MissionariesAndCannibals
{
	public static void main(String args[]) throws Exception
	{
		//生成操作算子，并复制到状态类
		MCOperationMetas opMetas=new MCOperationMetas();
		opMetas.CreateOperationMetas();
		System.out.println("操作算子的个数"+opMetas.OperaionMetas.size());
		MCState stTreeHead=new MCState();//头节点
		//初始化起始状态
		stTreeHead.OperaionMetas=opMetas.OperaionMetas;
		stTreeHead.m=3;
		stTreeHead.c=3;
		stTreeHead.b=1;
		stTreeHead.CreateOperationMetas();
		//初始化状态图
		MCState stTreeCurrentNode=stTreeHead;//中间节点变量一开始等于起始节点
		MCState stTreeNextNode=stTreeHead;//指向下一个节点
		MCStateSet StateSet=new MCStateSet();
		StateSet.getTheState(stTreeHead);
		//System.out.println(stTreeNextNode.m+","+stTreeNextNode.c+","+stTreeNextNode.b);
		//进行深度优先生成状态图解题
		int p=0;//路径数量
		while(true)
		{
			//测试代码
			//产生下一个节点
			stTreeNextNode=stTreeCurrentNode.takeOperation();
			
			if(stTreeNextNode==null)
			{
				//如果当前节点是起始节点，则退出,否则回溯
				if(stTreeCurrentNode.isStartState())
				{
					System.out.println("game over total path:"+stTreeHead.weight);
					break;
				}
				stTreeCurrentNode=stTreeCurrentNode.PrevState ;
				System.out.println("回溯到"+stTreeCurrentNode.m+","+stTreeCurrentNode.c+","+stTreeCurrentNode.b);
					continue;
			}
			
			System.out.println(stTreeCurrentNode.m+","+stTreeCurrentNode.c+","+stTreeCurrentNode.b+"("+String.valueOf(stTreeNextNode.opMeta.m)+String.valueOf(stTreeNextNode.opMeta.c)+")->"+stTreeNextNode.m+","+stTreeNextNode.c+","+stTreeNextNode.b);
				
			//检验这个节点是否存在,并返回已经存在的节点
			stTreeNextNode=StateSet.getTheState(stTreeNextNode);
			//如果这个节点已经探索结束，则直接加权，然后回溯
			if(stTreeNextNode.opMetasUnused.size()==0)
			{
				System.out.println("路径+"+stTreeNextNode.weight);
				stTreeNextNode.AddWeight(stTreeNextNode.weight);
			}
			//System.in.read();//暂停
				//如果操作算子用完也无法找到子节点,则回溯，尝试下一个操作算子
				
				//找到目标节点则尝试下一个操作算子
				if(stTreeNextNode.isEndState())
				{
					p+=1;
					System.out.println("find path:"+p);
					//路径加权
					stTreeNextNode.AddWeight(1);
					stTreeCurrentNode.NextState.add(stTreeNextNode);
					continue;
					
				}
				if(stTreeNextNode.isLegalState())
				{
					//如果是合法节点，则添加到图中，并退出for循环，进行下一个节点的寻找.深度优先
					stTreeCurrentNode.NextState.add(stTreeNextNode);
					//stTreeNextNode.PrevState=stTreeCurrentNode;
					stTreeCurrentNode=stTreeNextNode;
					continue;
				}
					
		}
		
		

	}
}