/本程序取自王晓东编著“算法分析与设计”第 211 页,例
//分支限界法解布线问题
import java.io.*;
class WireRouter
{
private static class Position
{
private int row; //方格所在的行
private int col; //方格所在的列
Position(int rr,int cc)
{
row=rr;
col=cc;
}
private static int [][] grid; //方格阵列
private static int size; //方格阵列大小
private static int pathLen; //最短路线长度
private static ArrayQueue q; //扩展结点队列
private static Position start, //起点
finish; //终点
private static Position [] path; //最短路
class ArrayQueue
{ private static final int defultSize=20;
private int size; //
private int front;
private int rear;
private Position[] listArray;
ArrayQueue(){setup(defultSize);}
ArrayQueue(int sz){setup(sz);} void setup(int sz)
{size=sz+1;front=rear=0;listArray=new Position[sz+1];}
public void clear()
{front=rear=0;}
public void Assert_notFalse(boolean p,String q)
{if(!p)System.out.println((String)q);} public void put(Position it)
{
Assert_notFalse(((rear+1)% size)!=front,"Queue is full");
rear=(rear+1)%size;
listArray[rear]=it;
}
public Position remove()
{
Assert_notFalse(! isEmpty(),"Queue is empty ");
front=(front+1)%size;
return listArray[front];
}
public Position firstValue()
{
Assert_notFalse(! isEmpty(),"Queue is empty ");
return listArray[(front+1)%size];
}
public boolean isEmpty()
{ return front==rear;}
public void put(int k,int g)
{
Position itg=new Position(k,g);
put(itg);
}
}
private static void inputData()
{
InputStreamReader keyboard=new InputStreamReader();
System.out.println("Enter grid size");
size=keyboard.readInteger();
System.out.println("Enter the start position");
start=new Position(keyboard.readInteger(),keyboard.readInteger());
System.out.println("Enter the finish position");
finish=new Position(keyboard.readInteger(),keyboard.readInteger());
grid=new int[size+2][size+2];
System.out.println("Enter the wiring grid in row-major order");
for(int i=1;i<=size;i++)
for(int j=1;j<=size;j++)
grid[i][j]=keyboard.readInteger();
}
private boolean findPath()
{ //计算从起始位置start到目标位置finish的最短布线路径
//找到最短布线路径则返回true ,否则返回false
if((start.row==finish.row)&&(start.col==finish.col))
{//start==finish
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); // 上 //设置方格阵列“围墙”
for(int i=0;i<=size+1;i++)
{
grid[0][i]=grid[size+1][i]=1; // 顶部和底部
grid[i][0]=grid[i][size+1]=1; // 左翼和右翼
}
Position here=new Position(start.row,start.col);
grid[start.row][start.col]=2; // 起始位置的距离
int numOfNbrs=4; // 相邻方格数
//标记可达方格位置
ArrayQueue q=new ArrayQueue();
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(grid[nbr.row][nbr.col]==0)
{//该方格未标记
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成
q.put(new Position(nbr.row,nbr.col));
}
}
//是否到达目标位置finish?
if((nbr.row==finish.row)&&(nbr.col==finish.col))break; //完成
//活结点队列是否为非空
if(q.isEmpty())return false; // 无解
here=(Position)q.remove(); // 取下一个扩展结点
}while(true);
//构造最短布线路径
pathLen=grid[finish.row][finish.col]-2;
System.out.println("最短线路长度 "+pathLen);
path=new Position[pathLen];
// 从目标位置finish开始向起始位置回溯
here=finish;
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 class Fac6_4
{
public static void main(String args[])
{
WireRouter abc=new WireRouter();
// int size1=7;
// int [][] grid1=new int[size][size];
// grid1={{0,0,1,0,0,0,0},{0,0,1,1,0,0,0},{0,0,0,0,1,0,0},{0,0,0,1,1,0,0},
// {1,0,0,0,1,0,0},{1,1,1,0,0,0,0},{1,1,1,0,0,0,0}};
}
}
本 程序有点错误,就是改不出来,请高手给看看,谢谢了。
//分支限界法解布线问题
import java.io.*;
class WireRouter
{
private static class Position
{
private int row; //方格所在的行
private int col; //方格所在的列
Position(int rr,int cc)
{
row=rr;
col=cc;
}
private static int [][] grid; //方格阵列
private static int size; //方格阵列大小
private static int pathLen; //最短路线长度
private static ArrayQueue q; //扩展结点队列
private static Position start, //起点
finish; //终点
private static Position [] path; //最短路
class ArrayQueue
{ private static final int defultSize=20;
private int size; //
private int front;
private int rear;
private Position[] listArray;
ArrayQueue(){setup(defultSize);}
ArrayQueue(int sz){setup(sz);} void setup(int sz)
{size=sz+1;front=rear=0;listArray=new Position[sz+1];}
public void clear()
{front=rear=0;}
public void Assert_notFalse(boolean p,String q)
{if(!p)System.out.println((String)q);} public void put(Position it)
{
Assert_notFalse(((rear+1)% size)!=front,"Queue is full");
rear=(rear+1)%size;
listArray[rear]=it;
}
public Position remove()
{
Assert_notFalse(! isEmpty(),"Queue is empty ");
front=(front+1)%size;
return listArray[front];
}
public Position firstValue()
{
Assert_notFalse(! isEmpty(),"Queue is empty ");
return listArray[(front+1)%size];
}
public boolean isEmpty()
{ return front==rear;}
public void put(int k,int g)
{
Position itg=new Position(k,g);
put(itg);
}
}
private static void inputData()
{
InputStreamReader keyboard=new InputStreamReader();
System.out.println("Enter grid size");
size=keyboard.readInteger();
System.out.println("Enter the start position");
start=new Position(keyboard.readInteger(),keyboard.readInteger());
System.out.println("Enter the finish position");
finish=new Position(keyboard.readInteger(),keyboard.readInteger());
grid=new int[size+2][size+2];
System.out.println("Enter the wiring grid in row-major order");
for(int i=1;i<=size;i++)
for(int j=1;j<=size;j++)
grid[i][j]=keyboard.readInteger();
}
private boolean findPath()
{ //计算从起始位置start到目标位置finish的最短布线路径
//找到最短布线路径则返回true ,否则返回false
if((start.row==finish.row)&&(start.col==finish.col))
{//start==finish
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); // 上 //设置方格阵列“围墙”
for(int i=0;i<=size+1;i++)
{
grid[0][i]=grid[size+1][i]=1; // 顶部和底部
grid[i][0]=grid[i][size+1]=1; // 左翼和右翼
}
Position here=new Position(start.row,start.col);
grid[start.row][start.col]=2; // 起始位置的距离
int numOfNbrs=4; // 相邻方格数
//标记可达方格位置
ArrayQueue q=new ArrayQueue();
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(grid[nbr.row][nbr.col]==0)
{//该方格未标记
grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;
if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//完成
q.put(new Position(nbr.row,nbr.col));
}
}
//是否到达目标位置finish?
if((nbr.row==finish.row)&&(nbr.col==finish.col))break; //完成
//活结点队列是否为非空
if(q.isEmpty())return false; // 无解
here=(Position)q.remove(); // 取下一个扩展结点
}while(true);
//构造最短布线路径
pathLen=grid[finish.row][finish.col]-2;
System.out.println("最短线路长度 "+pathLen);
path=new Position[pathLen];
// 从目标位置finish开始向起始位置回溯
here=finish;
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 class Fac6_4
{
public static void main(String args[])
{
WireRouter abc=new WireRouter();
// int size1=7;
// int [][] grid1=new int[size][size];
// grid1={{0,0,1,0,0,0,0},{0,0,1,1,0,0,0},{0,0,0,0,1,0,0},{0,0,0,1,1,0,0},
// {1,0,0,0,1,0,0},{1,1,1,0,0,0,0},{1,1,1,0,0,0,0}};
}
}
本 程序有点错误,就是改不出来,请高手给看看,谢谢了。
import java.util.Scanner;private static void inputData() {
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter grid size");
size = keyboard.nextInt();
System.out.println("Enter the start position");
start = new Position(keyboard.nextInt(), keyboard.nextInt());
System.out.println("Enter the finish position");
finish = new Position(keyboard.nextInt(), keyboard.nextInt());
grid = new int[size + 2][size + 2];
System.out.println("Enter the wiring grid in row-major order");
for (int i = 1; i <= size; i++)
for (int j = 1; j <= size; j++)
grid[i][j] = keyboard.nextInt();
}
改改inputstream 为 Scanner
能说点算法 哈