九宫图.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(测试九宫图);
    }
}