九宫图.java

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

/*
 * Created on 2005-4-8
 *
 * To change the template for this generated file go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */

/**
 * @author Administrator
 *
 * To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Generation - Code and Comments
 */

import java.util.*;

public class 九宫图 
{
	//以下定义了一组常量
	//解类型的常量
	public static final int 解类型_无解=0;
	public static final int 解类型_有解=1;
	public static final int 解类型_最佳解=2;
	
	九宫图结点	开始结点;
	九宫图结点	目标结点;
	九宫图结点  	当前结点=null;
	表			OPEN表=new 表();
	表			CLOSE表=new 表();
	表			扩展结点表=new 表();	
	int   		有界深度=0;
	boolean		搜索是否完成=false;
	int			解类型=九宫图.解类型_无解;
	Vector		解路径=new Vector();		
	

	九宫图()
	{
		this.开始结点=new 九宫图结点();
		this.目标结点=new 九宫图结点();
		this.开始结点.到预置状态();
		this.目标结点.到目标状态();		
	}
	
	九宫图(九宫图结点 start,九宫图结点 end)
	{
		this.开始结点=new 九宫图结点(start);
		this.目标结点=new 九宫图结点(end);			
	}
	
	public void 置当前结点(九宫图结点 node)
	{
		this.当前结点=node;
	}
	
	public 九宫图结点 取当前结点()
	{
		return this.当前结点;
	}
	
	public void 置开始结点(九宫图结点 node)
	{
		this.开始结点=new 九宫图结点(node);
	}
	
	public 九宫图结点 取开始结点()
	{
		return this.开始结点;
	}
	
	public void 置目标结点(九宫图结点 node)
	{
		this.目标结点=new 九宫图结点(node);
	}
	
	public 九宫图结点 取目标结点()
	{
		return this.目标结点;
	}
	
	public void 初始化()
	{		
		this.目标结点.到目标状态();
		this.CLOSE表.初始化();
		this.OPEN表.初始化();
		this.扩展结点表.初始化();
		this.当前结点=null;
		this.搜索是否完成=false;
		this.解类型=九宫图.解类型_无解;
		this.解路径.removeAllElements();		
	}
	
	//扩展node的所有子结点并放入扩展结点表中	
	private boolean 顺序扩展结点(九宫图结点 node)
	{
		boolean 	retv=false;
		
		九宫图结点 	n1=new 九宫图结点(node);
		九宫图结点 	n2=new 九宫图结点(node);
		九宫图结点 	n3=new 九宫图结点(node);
		九宫图结点 	n4=new 九宫图结点(node);
		
		this.扩展结点表.removeAllElements();
		
		if(n1._操作_空格上移()==true
			&&this.CLOSE表.结点是否在表中(n1)==false)
		{
			n1.修改返回指针(node);
			n1.置生成操作(九宫图结点.空格上移);
			n1.置结点深度(node.取结点深度()+1);
			this.扩展结点表.加入结点(n1);
			retv=true;
		}

		if(n2._操作_空格下移()==true
			&&this.CLOSE表.结点是否在表中(n2)==false)
		{
			n2.修改返回指针(node);
			n2.置生成操作(九宫图结点.空格下移);
			n2.置结点深度(node.取结点深度()+1);
			this.扩展结点表.加入结点(n2);
			retv=true;
		}
		
		if(n3._操作_空格左移()==true
			&&this.CLOSE表.结点是否在表中(n3)==false)
		{
			n3.修改返回指针(node);
			n3.置生成操作(九宫图结点.空格左移);
			n3.置结点深度(node.取结点深度()+1);
			this.扩展结点表.加入结点(n3);
			retv=true;
		}
		
		if(n4._操作_空格右移()==true
			&&this.CLOSE表.结点是否在表中(n4)==false)
		{
			n4.修改返回指针(node);
			n4.置生成操作(九宫图结点.空格右移);
			n4.置结点深度(node.取结点深度()+1);
			this.扩展结点表.加入结点(n4);
			retv=true;
		}		
		
		return retv;
	}
	
	//将扩展所得的结点排序，然后再放入扩展结点表中
	private boolean 排序扩展结点(九宫图结点 node)
	{
		boolean 	retv=false;
		
		九宫图结点 	n1=new 九宫图结点(node);
		九宫图结点 	n2=new 九宫图结点(node);
		九宫图结点 	n3=new 九宫图结点(node);
		九宫图结点 	n4=new 九宫图结点(node);
		
		this.扩展结点表.removeAllElements();
		
		if(n1._操作_空格上移()==true
			&&this.CLOSE表.结点是否在表中(n1)==false)
		{
			n1.修改返回指针(node);
			n1.置生成操作(九宫图结点.空格上移);
			n1.置结点深度(node.取结点深度()+1);
			n1.计算代价估计值();
			this.扩展结点表.排序加入结点(n1);
			retv=true;
		}

		if(n2._操作_空格下移()==true
			&&this.CLOSE表.结点是否在表中(n2)==false)
		{
			n2.修改返回指针(node);
			n2.置生成操作(九宫图结点.空格下移);
			n2.置结点深度(node.取结点深度()+1);
			n2.计算代价估计值();
			this.扩展结点表.排序加入结点(n2);
			retv=true;
		}
		
		if(n3._操作_空格左移()==true
			&&this.CLOSE表.结点是否在表中(n3)==false)
		{
			n3.修改返回指针(node);
			n3.置生成操作(九宫图结点.空格左移);
			n3.置结点深度(node.取结点深度()+1);
			n3.计算代价估计值();
			this.扩展结点表.排序加入结点(n3);
			retv=true;
		}
		
		if(n4._操作_空格右移()==true
			&&this.CLOSE表.结点是否在表中(n4)==false)
		{
			n4.修改返回指针(node);
			n4.置生成操作(九宫图结点.空格右移);
			n4.置结点深度(node.取结点深度()+1);
			n4.计算代价估计值();
			this.扩展结点表.排序加入结点(n4);
			retv=true;
		}		
		
		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 单步深度优先搜索()
	{
		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 单步有界深度优先搜索()
	{
		if(this.搜索是否完成==true||this.OPEN表.是否为空()==true)
		{
			this.搜索是否完成=true;
			return true;
		}				
		
		this.当前结点=(九宫图结点)this.OPEN表.取出结点();		
		this.CLOSE表.加入结点(this.当前结点);
		
		if(this.当前结点.equals(this.目标结点)==true)
		{