最短路径问题——分支限界法

In the N×M grid array, there is a start-cell, name A, and a end-cell, name B. The problem is finding the shortest routing scheme (i.e. the shortest path) from A to B. When wiring, it can only follow a straight line or a right angle, not a diagonal line. Black cells represent blocked squares that cannot be passed. Shown as the follow picture, in the 3×3 grid array, the length of shortest path from A to B is 6. A tow dimension array can represent the grid array, in which, ordinary cell is presented by 0, and black cell is represented by 1.

Input:

Input N and M at first line (no more than 100), next input N×M array, at last input A's row coordinate, A's column coordinate, B's row coordinate, B's column coordinate.

Output:

print out length of the shortest path from A to B. If no path from A to B, then print 0.

Input Example:

Here is a set of inputs. For example:

3 3
0 1 0
0 1 0
0 0 0
0 0 0 2

 

Output Example:

Here is a set of outputs. For example:

6

 

代码：

  1 package work7;
  2 
  3 import java.util.Scanner;
  4 
  5 /**
  6 *@author Noble4
  7 *@version 2020年12月5日 下午8:46:42
  8 *@package work7
  9 **/
 10 public class test2 {
 11     static int MAX_VALUE = 100;
 12     int row;int line;
 13     int[][] Figure;int[][] Tags;//记录到走过的点的步数
 14     //移动偏向(-1向左，1向右)
 15     int DIRECTION;
 16     //起点和终点的坐标
 17     int x1;int y1;int x2;int y2;
 18     
 19     
 20     
 21     public void Init() {
 22         Scanner sr = new Scanner(System.in);
 23         row = sr.nextInt();
 24         line = sr.nextInt();
 25         Figure = new int[row][line];
 26         for (int i = 0; i < row; i++) {
 27             for (int j = 0; j < line; j++) {
 28                 Figure[i][j] = sr.nextInt();
 29             }
 30         }        
 31         x1 = sr.nextInt();
 32         y1 = sr.nextInt();
 33         x2 = sr.nextInt();
 34         y2 = sr.nextInt();       
 35         Tags = new int[row][line];
 36         //初始化记录步数的数组
 37         for (int i = 0; i < row; i++) {
 38             for (int j = 0; j < line; j++) {
 39                 //MAX_VALUE代表没走过
 40                 Tags[i][j] = MAX_VALUE;
 41             }
 42         }
 43         //初始化移动偏向
 44         if(y1 < y2) {
 45             DIRECTION = 1;
 46         }else if(y1 > y2){
 47             DIRECTION = -1;
 48         }else {
 49             DIRECTION = 0;
 50         }
 51         Figure[x1][y1] = 1;
 52         Tags[x1][y1] = 0;
 53     }
 54     
 55     //单点向周围分支
 56     public void Branch(int x,int y,int D) {
 57         //限界
 58         if(Tags[x][y]>=D) {
 59             Tags[x][y] = D;
 60         }else {
 61             return;
 62         }
 63         //使用移动偏好
 64         if(y <= y1 && DIRECTION == 1) {
 65             //越界判断应该在前面不然后面的Figure[x+1][y] == 0可能报错
 66             if(!isBorder(x+1, y) && Figure[x+1][y] == 0) {
 67                 Branch(x+1,y,D+1);
 68             }
 69             if( !isBorder(x, y+1) && Figure[x][y+1] == 0) {
 70                 Branch(x,y+1,D+1);
 71             }
 72             if(!isBorder(x-1, y) && Figure[x-1][y] == 0) {
 73                 Branch(x-1,y,D+1);
 74             }            
 75         }else if(y >= y1 && DIRECTION == -1) {
 76             if(!isBorder(x-1, y) && Figure[x-1][y] == 0) {
 77                 Branch(x-1,y,D+1);
 78             }
 79             if(!isBorder(x+1, y) && Figure[x+1][y] == 0) {
 80                 Branch(x+1,y,D+1);
 81             }
 82             if(!isBorder(x, y-1) && Figure[x][y-1] == 0) {
 83                 Branch(x,y-1,D+1);
 84             }            
 85         }else {
 86             if(!isBorder(x+1, y) && Figure[x+1][y] == 0) {
 87                 Branch(x+1,y,D+1);
 88             }
 89             if(!isBorder(x-1, y) && Figure[x-1][y] == 0) {
 90                 Branch(x-1,y,D+1);
 91             }
 92             if(!isBorder(x, y+1) && Figure[x][y+1] == 0) {
 93                 Branch(x,y+1,D+1);
 94             }
 95             if(!isBorder(x, y-1) && Figure[x][y-1] == 0) {
 96                 Branch(x,y-1,D+1);
 97             }        
 98         }        
 99     }
100     
101     //判断是否超过边界
102     public boolean isBorder(int x,int y) {
103         if(x<0||y<0||x >= row||y >= line) {
104             return true;
105         }else {
106             return false;
107         }        
108     }
109     
110     public static void main(String[] args) {
111         test2 test2 = new test2();
112         test2.Init();
113         test2.Branch(test2.x1, test2.y1, 0);
114         System.out.println(test2.Tags[test2.x2][test2.y2]);
115         for (int[] ints : test2.Tags) {
116             for (int item : ints) {
117                 System.out.print(item + "   ");
118             }
119             System.out.println();
120         }
121     }
122 }

用例：

7 7
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 1 0
0 0 0 1 0 1 0
0 0 0 1 0 1 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 1 4 6

结果截图：

问题：

1. 尝试了移动偏好，使用中存在问题，某些特殊情况会得不到最优路径
2. 不能在找到最优路径后停止所有寻找

希望有朋友指点迷津！