九宫图.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)
        {