circuit.java

用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装载问题.作业最优处理问韪.

/*
 * Circuit.java
 *
 * Created on 2006年4月14日, 下午3:02
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

package test;
import java.lang.Math.*;
/**
 *
 * @author michael
 */
public  class Circuit{

    /** Creates a new instance of Circuit */
    int fixRow,fixCol;
    private  static int [][]grid;       //方格阵列
    private  static int size=0;                //方格阵列大小
    private  static MyQueue q;            //扩展结点队列
    private  static Position start,end;    //起点，终点
    private  static Position []path;         //最短路
    private  static int pathLen;            //最短线路长度
    public Circuit() {
        start=new Position(); 
        end=new Position(); 
    }
    public void  setSize(int value){this.size=value;;}
    public void  setStartPosition(int row,int col){start.col=col;start.row=row;}
    public void  setEndPosition(int row,int col){end.col=col;end.row=row;}
    public int getStartPosRow(){return start.row;}
    public int getStartPosCol(){return start.col;}
    public int getEndPosRow(){return end.row;}
    public int getEndPosCol(){return end.col;}
    public Position[] getPath(){return path;}
    public Position getEndPosition(){
        Position p=new Position();
        p.col=end.col;
        p.row=end.row;
        return p;
    }
    public int[][] getGrid(){return grid;}
    public void initBoard(){        //初始化电路板
        grid=new int[size+2][size+2];
        //设方格阵列“围啬”
        for(int i=0;i<=size+1;i++){
            grid[0][i]=grid[size+1][i]=1;
            grid[i][0]=grid[i][size+1]=1;
        }
        int k = (int)(size*(size/3));
        for (int i=0;i<k;i++){        //产生随机不可用路径
            fixRow=(int)(Math.random()*(size+1));
            fixCol=(int)(Math.random()*(size+1));
            System.out.print(fixRow);
            if (((start.col!=fixCol) && (start.row!=fixRow)) || ((end.col!=fixCol) && (end.row!=fixRow)))
                 grid[fixRow][fixCol]=1;
        }
    }
    public boolean findPath(){
            if ((start.row==end.row) && (start.col==end.col)){  
                pathLen=0;
                return true;
            }
            //初始化相对位移
            Position[] offset = new Position[4];
            offset[0]= new Position(0,1);
            offset[1] = new Position(1,0);
            offset[2] = new Position(0,-1);
            offset[3] = new Position(-1,0);

            Position here = new Position(start.row,start.col);
            grid[start.row][start.col]=2;   //起始位置的距离
            int numOfNbrs=4;
            
            //标记可达位置
            MyQueue q = new MyQueue();
            Position nbr = new Position(0,0);
            do
            {//标记可达相邻方格
                for (int i=0;i<numOfNbrs;i++){
                    nbr.row=here.row+offset[i].row;
                    nbr.col=here.col+offset[i].col;
                        if (nbr.row==end.row && end.col==nbr.col ) System.out.println(grid[here.col][here.row]+"**");                    
                    if (grid[nbr.row][nbr.col]==0){// 读方格未标记
                        grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;

                        if ((nbr.row==end.row)&&(nbr.col==end.col)) break;//完成     
                        else q.enQueue(new Position(nbr.row,nbr.col), grid[nbr.row][nbr.col]); 
                    
                    }
                }
                if ((nbr.row==end.row) && (nbr.col==end.col)) break;     //完成 
                if (q.isEmpty()) return false;                         //无解
                else here = (Position)q.deQueue();                            //取下一个扩展结点
             }while(true);
            
            /**构造最矮布线路线
            pathLen=grid[end.row][end.col]-2; 
            if (pathLen>0) path = new Position[pathLen];
            //从目标位置 end 开始向起始位置回溯
            here = end; 
            for (int j = pathLen-1;j>=0;j--){
                path[j] = here;
                //找前驱位置
                for (int i=0;i<numOfNbrs;i++){
                    nbr.row=here.row+offset[i].row;
                    nbr.col=here.col+offset[i].col;
                    if(grid[nbr.row][nbr.col]==j+2) break;
                }
                here = new Position(nbr.row,nbr.col); //向前移动
                            }**/
            return true;
        }
    public int getSize(){
        return this.size;
    }
    public void PrintGrid(){
        for (int i=0;i<size+2;i++){
            for (int j=0;j<size+2;j++) System.out.print(grid[i][j]);
            System.out.println();
        }
    }
        private static class Position{
            private int row,col;
            public Position(int r,int c){
                row=r;
                col=c;
            }
            public Position(){
            }
        }
}