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;
				}
					
		}
		
		

	}
}