eightastar.java

九宫问题（八数码）的一个小软件

/*
 * EightAStar.java
 *
 * Created on February 13, 2006, 9:10 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package org.ray.ninegrid;

import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Vector;
import org.ray.ninegrid.AbstractEightAnalyse.Operation;
import org.ray.ninegrid.AbstractEightAnalyse.Status;

/**
 *
 * @author Ray#
 */
public class EightAStar extends AbstractEightAnalyse{
    private PriorityQueue<Status> queue;
    private Vector<Status> queuev;
    private Cmp cmp;
    /** Creates a new instance of EightAStar */
    private EightAStar() {
        super();
        hash.put(new Status(end,0),new Operation('0'));
        queue=new PriorityQueue<Status>(218,cmp);
        queuev=new Vector<Status>();
        cmp=new Cmp();
    }
 
    private static final EightAStar instance=new EightAStar();
    
    public static EightAStar getInstance(int[] st){
        instance.start=st;
        return instance;
    }
    
    protected void valid(int[] nextStatus, int nextLevel, char operation) {
        Status temp=new Status(nextStatus,nextLevel);
        if(!hash.containsKey(temp)){
            hash.put(temp,new Operation(operation));
            temp.manhattan(start);
            queue.offer(temp);
            queuev.add(temp);            
        }else if(queue.contains(temp)){
            Status t=queuev.get(queuev.indexOf(temp));
            t.level=t.level<temp.level?t.level:temp.level;
        }
    }
    
    public String search() {
        time=System.currentTimeMillis();
        Runtime.getRuntime().gc();
        mem=Runtime.getRuntime().freeMemory();
        Status a=new Status(start,0);
        if(!hash.containsKey(a)){
            if(queue.size()==0){
                Status t=new Status(end,0);
                hash.put(t,new Operation('0'));
                queue.offer(t);
                queuev.add(t);
            }
            Status cur;
            do{
                cur=queue.poll();
                queuev.remove(cur);
                expand(cur.value,cur.level);
            }while(!cur.equals(a));
        }
        mem=Math.abs(mem-Runtime.getRuntime().freeMemory());
        oplist=result();
        time=System.currentTimeMillis()-time;
        return oplist;
    }
    
    protected String result() {
        StringBuffer sb=new StringBuffer();
        Status st=new Status(start,0);
        Status ends=new Status(end,0);
        char op='1';
        while(!st.equals(ends)){
            op=opposite(hash.get(st).op);
            sb.append(op);
            st=new Status(move(st.value,op),0);
        }
        return sb.toString();
    }
    
    @Override
            public void clear(){
        hash.clear();
        queue.clear();
    }
    
    public void setScale(int g,int h){
        cmp.rg=g;
        cmp.rh=h;
    }
    
    public class Cmp implements Comparator<Status>{
        int rg,rh;
        
        public Cmp(){
            rg=1;
            rh=1;
        }
        
        public int compare(Status a,Status b){
            return rh*(a.man-b.man)+rg*(a.level-b.level);
        }
    }
}