九宫图.java

一个使用Java实现的人工智能的图搜索策略程序——酒九宫图问题 人工智能－图搜索策略－演示程序－使用说明 程序简介 在人工智能领域

			this.搜索是否完成=true;
			this.解类型=九宫图.解类型_有解;
			
			return true;			
		}
		
		if(this.有界深度!=this.当前结点.取结点深度())
		{
			this.顺序扩展结点(this.当前结点);
		}
		else
		{
			return false;
		}		
		
		九宫图结点 temp;
		while(this.扩展结点表.是否为空()==false)
		{
			temp=(九宫图结点)this.扩展结点表.取出结点();
			this.OPEN表.加入结点到表首(temp);
		}
		
		return false;
	}
	
	//对九宫图问题进行有界深度度优先搜索	
	public boolean 有界深度优先搜索()
	{
		boolean retv=false;
		
		this.OPEN表.加入结点(this.开始结点);
		
		while(this.OPEN表.是否为空()!=true)
		{
			this.当前结点=(九宫图结点)this.OPEN表.取出结点();			
			this.CLOSE表.加入结点(this.当前结点);
			
			if(this.当前结点.equals(this.目标结点)==true)
			{	
				retv=true;
				break;
			}
			
			if(this.有界深度!=this.当前结点.取结点深度())
			{
				this.顺序扩展结点(this.当前结点);
			}
			else
			{
				continue;
			}			
			
			九宫图结点 temp;
			while(this.扩展结点表.是否为空()==false)
			{
				temp=(九宫图结点)this.扩展结点表.取出结点();
				this.OPEN表.加入结点到表首(temp);
			}
		}

		this.搜索是否完成=true;
		
		if(retv==true)
		{			
			this.解类型=九宫图.解类型_有解;
		}
		else
		{			
			this.解类型=九宫图.解类型_无解;
		}
		
		return retv;
	}
	
	public boolean 单步最好优先搜索()
	{
		if(this.搜索是否完成==true||this.OPEN表.是否为空()==true)
		{
			return true;
		}
		
		this.当前结点=(九宫图结点)this.OPEN表.取出结点();			
		this.CLOSE表.加入结点(this.当前结点);
			
		if(this.当前结点.equals(this.目标结点)==true)
		{	
			this.搜索是否完成=true;
			this.解类型=九宫图.解类型_有解;
			
			return true;			
		}
			
		this.顺序扩展结点(this.当前结点);
		this.扩展结点表.计算结点代价估计值();
			
		九宫图结点 temp;
		while(this.扩展结点表.是否为空()==false)
		{
			temp=(九宫图结点)this.扩展结点表.取出结点();
			this.OPEN表.排序加入结点(temp);
		}
		
		return false;
	}
	
	public boolean 最好优先搜索()
	{
		boolean retv=false;
		
		this.OPEN表.加入结点(this.开始结点);
		
		while(this.OPEN表.是否为空()!=true)
		{
			this.当前结点=(九宫图结点)this.OPEN表.取出结点();			
			this.CLOSE表.加入结点(this.当前结点);
			
			if(this.当前结点.equals(this.目标结点)==true)
			{	
				retv=true;
				break;
			}
			
			this.顺序扩展结点(this.当前结点);
			this.扩展结点表.计算结点代价估计值();
			
			九宫图结点 temp;
			while(this.扩展结点表.是否为空()==false)
			{
				temp=(九宫图结点)this.扩展结点表.取出结点();
				this.OPEN表.排序加入结点(temp);								
			}
		}
		
		this.搜索是否完成=true;
		
		if(retv==true)
		{			
			this.解类型=九宫图.解类型_有解;
		}
		else
		{			
			this.解类型=九宫图.解类型_无解;
		}
		
		return retv;
	}
	
	public boolean 单步局部择优搜索()
	{
		if(this.搜索是否完成==true||this.OPEN表.是否为空()==true)
		{
			return true;
		}
		
		this.当前结点=(九宫图结点)this.OPEN表.取出结点();			
		this.CLOSE表.加入结点(this.当前结点);
			
		if(this.当前结点.equals(this.目标结点)==true)
		{	
			this.搜索是否完成=true;
			this.解类型=九宫图.解类型_有解;
			
			return true;			
		}
			
		this.排序扩展结点(this.当前结点);		
			
		九宫图结点 temp;
		while(this.扩展结点表.是否为空()==false)
		{
			temp=(九宫图结点)this.扩展结点表.取出结点();
			this.OPEN表.加入结点(temp);			
		}
		
		return false;
	}
	
	public boolean 局部择优搜索()
	{
		boolean retv=false;
		
		this.OPEN表.加入结点(this.开始结点);
		
		while(this.OPEN表.是否为空()!=true)
		{
			this.当前结点=(九宫图结点)this.OPEN表.取出结点();			
			this.CLOSE表.加入结点(this.当前结点);
			
			if(this.当前结点.equals(this.目标结点)==true)
			{	
				retv=true;
				break;
			}
			
			this.排序扩展结点(this.当前结点);		
			
			九宫图结点 temp;
			while(this.扩展结点表.是否为空()==false)
			{
				temp=(九宫图结点)this.扩展结点表.取出结点();
				this.OPEN表.加入结点(temp);							
			}
		}
		
		this.搜索是否完成=true;
		
		if(retv==true)
		{			
			this.解类型=九宫图.解类型_有解;
		}
		else
		{			
			this.解类型=九宫图.解类型_无解;
		}
		
		return retv;
	}
		
	
	public boolean 生成解路径()
	{
		九宫图结点 pnode=this.当前结点;
		
		if(this.搜索是否完成==false) return false;
		
		while(pnode!=null)
		{
			this.解路径.insertElementAt(pnode,0);
			pnode=pnode.取得返回指针();
		}
		
		return true;
	}		
	
	public String 取解路径文本()
	{
		九宫图结点 pnode;
		String   strtemp=new String();

		for(int i=0;i<this.解路径.size();i++)
		{
			pnode=(九宫图结点)this.解路径.elementAt(i);
			strtemp+=pnode+"\n\n";
		}
		
		return strtemp;
	}
	
	public String 取操作序列文本()
	{
		九宫图结点 	node;
		String  	strtemp=new String();
		
		for(int i=0;i<this.解路径.size();i++)
		{
			node=(九宫图结点)this.解路径.elementAt(i);
			switch(node.取生成操作())
			{
				case 九宫图结点.空格上移:
					strtemp+="空格上移\n";
					break;
				case 九宫图结点.空格下移:
					strtemp+="空格下移\n";
					break;
				case 九宫图结点.空格左移:
					strtemp+="空格左移\n";
					break;
				case 九宫图结点.空格右移:
					strtemp+="空格右移\n";
					break;
				default:
					break;
			}
		}
		
		return strtemp;
	}
	
	public double 计算搜索效率()
	{
		if(this.搜索是否完成==true)
		{
			return (double)this.解路径.size()
				/(this.CLOSE表.size()+this.OPEN表.size());
		}
		else
		{
			return 0;
		}
	}
	
	public String 取解信息文本()
	{
		String strtemp=new String();
		
		strtemp+="解路径：\n"+this.取解路径文本();			
		strtemp+="操作序列：\n"+this.取操作序列文本()+"\n";
				
		strtemp+="搜索过程中总共生成了"+(this.OPEN表.取结点个数()
			+this.CLOSE表.取结点个数())+"个结点\n";
		strtemp+="其中考察了"+this.CLOSE表.取结点个数()+"个结点\n";
		strtemp+="解路径的长度为"+this.解路径.size()+"个结点\n";
		strtemp+="搜索效率为："+this.计算搜索效率()+"\n";
		
		return strtemp;
	}
	
	public String toString()
	{
		String strtemp="九宫图搜索\n\n";
		
		strtemp+="开始结点：\n";
		strtemp+=this.开始结点+"\n\n";
		strtemp+="目标结点：\n";
		strtemp+=this.目标结点+"\n\n";
		
		if(this.搜索是否完成==false)
		{
			strtemp+="搜索还没有完成\n";
		}
		else
		{
			strtemp+="搜索已经完成\n";
			
			switch(this.解类型)
			{
				case 九宫图.解类型_无解:
				{
					strtemp+="没有找到解\n";					
					break;
				}
				case 九宫图.解类型_有解:
				{
					strtemp+="找到了解\n";					
					break;
				}
				case 九宫图.解类型_最佳解:
				{
					strtemp+="找到了最优解\n";					
					break;
				}
				default:
					break;
			}
			strtemp+=this.取解信息文本();
		}						
		
		return strtemp;
	}
	
	//以下是一个测试程序
	public static void main(String args[])
	{
		int[] start={8,2,8,3,1,6,4,7,0,5};
		int[] end={5,1,2,3,8,0,4,7,6,5};
		
		九宫图结点	开始结点=new 九宫图结点(start);
		九宫图结点 	目的结点=new 九宫图结点(end);
		九宫图 		测试九宫图=new 九宫图(开始结点,目的结点);
		
		测试九宫图.最好优先搜索();
		测试九宫图.生成解路径();		
		
		System.out.println(测试九宫图);
	}
}