寻路问题 |
您所在的位置：网站首页 › 经纬度大小怎么判断起点终点 › 寻路问题 |
寻路问题
|
一，寻路问题介绍 正如组合问题与动态规划的联系之应用提到的从起点(0,0)到终点(X,Y)一共有多少种走法。与之相似的另一个问题是如何找到从(0,0)到(X,Y)的路径？ 首先对问题建模。使用一个矩阵(二维数组)的下标 表示 各个点的坐标。矩阵元素只取 0 或者 1，0 表示此坐标是一个可达的正常顶点；而 1 则表示这是一个不可达的障碍顶点。比如 如下矩阵： {0,0,1,1,0} {1,0,0,0,0} {0,1,0,0,0} {0,0,1,1,0} {0,1,0,0,0} 从最右上角的顶点(坐标是（0，4）) 到左下的顶点（坐标是(4,0)）是 没有 路径的，因为路径不能穿过障碍顶点（4个） 而从最左上角的顶点(坐标是(0,0))到最右下的顶点(坐标是(4,4))是可达的。比如，如下就是顶点坐标就构成了一条可达的路径：
而本文讨论的是：如何 寻找一条从起点(0,0)到终点(X,Y)的可达路径？为了简便起见，每步只允许向右走，或者向下走。 在这里，默认(X,Y)是可达顶点，因为若(X,Y)是不可达顶点(坐标(x,y)处元素值为1)，就没有太大的讨论意义了。 此外，看到了上面的矩阵，是不是想到了图的邻接矩阵表示法？虽然二者的表达的意思有点不一样，但图的基本操作如判断一个顶点到另一个顶点的最短路径问题 与本文中的问题还是很相似的。
二，思路分析 提到寻路算法，不得不提到A*算法。由于对A*算法不是太了解，就不详细介绍了。但是A*算法肯定也是可以解决本文的寻路问题的。 在本文中，起点是(0,0)；终点是(X,Y)。 ①由于每步只能向右走或者向下走，对于(X,Y)而言，只有两种情况到达它。一种是从(X-1,Y)向右走一步到达；另一种是(X,Y-1)向下走一步到达。 这个分析，和组合问题与动态规划的联系之应用的分析一样。唯一的不同是，我们需要记录已经走过的顶点。 因此，类似地也有两种编程实现方式：递归方式和动态规划。 对于动态规划而言，其实就是把已经走过的顶点的“状态”保存起来，这里的顶点的“状态”表示的是：是否存在一条路径，能够从该顶点到达终点。 这也是为什么动态规划要比递归解运行得快 的本质原因。因为，递归求解该问题时，会有大量的重叠子问题。但是递归还是一 一地计算这些重叠的子问题，也就是说递归没有“记忆性”，对于同一个问题出现了若干次，递归解法是每出现一次，就计算一次。而动态规划则是只计算一次，并把计算的结果保存起来，后面再碰到该问题时，直接“查表”找出上次计算保存的结果即可。另外可参考：从 活动选择问题 看动态规划和贪心算法的区别与联系 首先来看递归解： 
1 //寻找起点(0,0)到终点(x,y)的一条路径
2 public boolean findPath(int x, int y, ArrayList paths)
3 {
4 Point p = new Point(x, y);
5 paths.add(p);//默认终点p的坐标对应的 数组值不是1
6
7 //base condition
8 if(x == 0 && y == 0)
9 return true;
10
11 boolean isSuccess = false;
12 if(y >= 1 && checkFree(x, y - 1))
13 isSuccess = findPath(x, y - 1, paths);
14 if(!isSuccess && x >= 1 && checkFree(x - 1, y))
15 isSuccess = findPath(x - 1, y, paths);
16
17 if(!isSuccess)
18 paths.remove(p);//O(N)
19 return isSuccess;
20 }
Point类封装了点的坐标(横坐标和纵坐标)，ArrayList paths 用来 保存走过的各个顶点的坐标，从而将整个路径记录下来。 第5行首先就把终点(x,y)添加到路径中去--这里默认了终点是可达的，即终点坐标的矩阵值为0 第8-9行是递归的基准条件。也就是说：到了起点(0,0)时，递归就结束了。 第12-13行是判断是否可以从(x,y-1)向下走一步到达(x,y)。if 条件中 y>=1，因为若 y < 1，说明已经不能再往下走了，再往下走，y坐标(纵坐标)就小于0了。 如果12-13行递归返回false，说明：最终未找到一条路径到达终点。故在第14-15行，变换寻找方向：判断是否可以从(x-1,y)到达(x,y) 第17行，表示：不存在路径使得：当前顶点p 到终点(X,Y)是可达的。因此，需要将 p 从ArrayList中删除。（理解递归）
再来看看动态规划的实现：
1 //另一种动态规划解决方案,它用HashMap缓存已经检查过的顶点是否可达终点
2 public boolean findPath_dp2(int x, int y, ArrayList paths, HashMap cache)
3 {
4 Point p = new Point(x, y);
5
6 //先查表.
7 if(cache.containsKey(p))
8 return cache.get(p);
9
10 paths.add(p);
11
12 if(x == 0 && y == 0)
13 return true;
14 boolean isSuccess = false;
15 if(x >= 1 && checkFree(x - 1, y))
16 isSuccess = findPath_dp2(x - 1, y, paths, cache);
17 if(!isSuccess && y >= 1 && checkFree(x, y - 1))
18 isSuccess = findPath_dp2(x, y - 1, paths, cache);
19
20 if(!isSuccess)
21 paths.remove(p);
22 cache.put(p, isSuccess);
23 return isSuccess;
24 }
①使用HashMap保存顶点Point是否至少存在一条路径可以到达终点。假设顶点，则表示顶点p1到终点(X,Y)是可达的。 ②这里的动态规划实现，也是方法的递归调用。但是，与上面的递归实现中的递归调用有本质不同。 这里在第7-8行，如果cache已经保存某个顶点，则直接返回结果。这就是动态规划中的“查表”。其它代码的实现与递归差不多。需要注意的是： 在第22行，不管isSuccess为true还是False，只要访问了顶点p，就把该顶点 p的结果保存起来。从而使得下一次碰到顶点p时，可直接查表。 比如说：要找到一条到达 (x,y)的路径，就要找出到它的相邻点(x-1,y) 和 (x,y-1)的路径。再看看与(x-1,y) 和 (x,y-1) 相邻的顶点坐标是： (x-2,y)、(x-1,y-1)、(x-1,y-1)、(x,y-2)。（x-1,y-1）出现了两次，这就是重叠子问题。 当第一次访问(x-1,y-1)时，计算出了该顶点是否可达(x,y)，当下次再访问 (x-1,y-1)时，动态规划就直接查表获得结果了，而递归实现则是又执行了一次递归调用。
另外，还有一种动态规划的实现方式。它不是用HashMap来保存已经访问过的顶点的结果，而是使用一个二维数组来保存某个顶点是否可达终点(x,y) 并根据状态方程： path(X,Y)=hasPath{path(X-1,Y) , path(X,Y-1)} 判断某顶点是否可到达(x,y)
1 public boolean findPath_DP(int x, int y, ArrayList paths){
2 //if dp[i][j]=true, exist at least one path from to (destination)
3 boolean[][] dp = new boolean[x+1][y+1];//"状态矩阵"保存 各点的可达情况
4 // //init
5 // for(int i = x - 1; i >= 0; i--){
6 // for(int j = y - 1; j >= 0; j--){
7 // dp[i][j] = false;
8 // }
9 // }
10 dp[x][y] = true;//init,初始时终点坐标肯定是可达的.因为 martix[x][y]==0
11
12 for(int i = x; i >= 0; i--){
13 for(int j = y; j >= 0; j--){
14 if(dp[i][j])//只有 从可达的点开始(初始时为终点)判断前面一个顶点是否可以到达本顶点
15 {
16 if(i >= 1 && checkFree(i-1, j))
17 dp[i-1][j] = true;
18 if(j >= 1 && checkFree(i, j-1))
19 dp[i][j-1] = true;
20 }
21 }
22 }
23
24 /*
25 * findPath recursively using dp "state martix"
26 * 它是通过查表 而不是 递归调用 判断 从某个顶点到终点是否可达
27 */
28 return getPath(x, y, dp, paths);
29 }
30 private boolean getPath(int x, int y, boolean[][] dp, ArrayList paths){
31 Point p = new Point(x, y);
32 paths.add(p);
33
34 if(dp[x][y] == false)//查表 判断 从是否可达终点
35 return false;
36
37 //base condition
38 if(x == 0 && y == 0)
39 return true;
40
41 boolean isSuccess = false;
42 if(x >= 1 && (dp[x - 1][y] == true))
43 isSuccess = getPath(x-1, y, dp, paths);
44 if(!isSuccess && y >= 1 && dp[x][y-1] == true)
45 isSuccess = getPath(x, y-1, dp, paths);
46 if(!isSuccess)
47 paths.remove(p);
48 return isSuccess;
49 }
①状态矩阵dp[][]对应每个顶点的坐标，第12行-22行检查每个顶点是否存在路径可以到达终点。 ②检查完后，在第28行，调用getPath()来找出一条从起点到达终点的路径。可以看出，getPath()寻找路径时，是直接“查表”判断出该顶点是否可达终点的(第34-35行) 而且可以看出，第12-22行的时间复杂度为O(N^2)，而递归调用的时间复杂度为O(2^N)
三，整个完整代码实现如下： 
import java.util.ArrayList;
import java.util.HashMap;
public class FinaPath {
private int[][] martix;
private class Point{
int x;//横坐标
int y;//纵坐标
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public FinaPath(int[][] martix) {
this.martix = martix;
}
//寻找起点(0,0)到终点(x,y)的一条路径
public boolean findPath(int x, int y, ArrayList paths)
{
Point p = new Point(x, y);
paths.add(p);//默认终点p的坐标对应的 数组值不是1
//base condition
if(x == 0 && y == 0)
return true;
boolean isSuccess = false;
if(y >= 1 && checkFree(x, y - 1))
isSuccess = findPath(x, y - 1, paths);
if(!isSuccess && x >= 1 && checkFree(x - 1, y))
isSuccess = findPath(x - 1, y, paths);
if(!isSuccess)
paths.remove(p);//O(N)
return isSuccess;
}
private boolean checkFree(int x, int y){
return martix[x][y] == 0;//0 表示有路
}
public boolean findPath_DP(int x, int y, ArrayList paths){
//if dp[i][j]=true, exist at least one path from to (destination)
boolean[][] dp = new boolean[x+1][y+1];//"状态矩阵"保存 各点的可达情况
// //init
// for(int i = x - 1; i >= 0; i--){
// for(int j = y - 1; j >= 0; j--){
// dp[i][j] = false;
// }
// }
dp[x][y] = true;//init
for(int i = x; i >= 0; i--){
for(int j = y; j >= 0; j--){
if(dp[i][j])//只有 从可达的点开始(初始时为终点)判断前面一个顶点是否可以到达本顶点
{
if(i >= 1 && checkFree(i-1, j))
dp[i-1][j] = true;
if(j >= 1 && checkFree(i, j-1))
dp[i][j-1] = true;
}
}
}
/*
* findPath recursively using dp "state martix"
* 它是通过查表 而不是 递归调用 判断 从某个顶点到终点是否可达
*/
return getPath(x, y, dp, paths);
}
private boolean getPath(int x, int y, boolean[][] dp, ArrayList paths){
Point p = new Point(x, y);
paths.add(p);
if(dp[x][y] == false)//查表 判断 从是否可达终点
return false;
//base condition
if(x == 0 && y == 0)
return true;
boolean isSuccess = false;
if(x >= 1 && (dp[x - 1][y] == true))
isSuccess = getPath(x-1, y, dp, paths);
if(!isSuccess && y >= 1 && dp[x][y-1] == true)
isSuccess = getPath(x, y-1, dp, paths);
if(!isSuccess)
paths.remove(p);
return isSuccess;
}
//另一种动态规划解决方案,它用HashMap缓存已经检查过的顶点
public boolean findPath_dp2(int x, int y, ArrayList paths, HashMap cache)
{
Point p = new Point(x, y);
//先查表.
if(cache.containsKey(p))
return cache.get(p);
paths.add(p);
if(x == 0 && y == 0)
return true;
boolean isSuccess = false;
if(x >= 1 && checkFree(x - 1, y))
isSuccess = findPath_dp2(x - 1, y, paths, cache);
if(!isSuccess && y >= 1 && checkFree(x, y - 1))
isSuccess = findPath_dp2(x, y - 1, paths, cache);
if(!isSuccess)
paths.remove(p);
cache.put(p, isSuccess);
return isSuccess;
}
//test
public static void main(String[] args) {
//0表示有路,1表示障碍
int[][] martix = {
{0,0,1,1,0},
{1,0,0,0,0},
{0,1,0,0,0},
{0,0,1,1,0},
{0,1,0,0,0}
};
FinaPath fp = new FinaPath(martix);
ArrayList paths = new ArrayList(martix.length + martix[0].length);
int endPivot_x = 4;
int endPivot_y = 4;
boolean hasPath = fp.findPath(endPivot_x, endPivot_y, paths);
if(hasPath)
printPath(paths);
else
System.out.println("recursive finds no path");
System.out.println();
ArrayList paths_dp = new ArrayList();
boolean hasPath_DP = fp.findPath_DP(endPivot_x, endPivot_y, paths_dp);
if(hasPath_DP)
printPath(paths_dp);
else
System.out.println("dp finds no path");
System.out.println();
ArrayList paths_dp2 = new ArrayList();
HashMap cache = new HashMap(endPivot_y + endPivot_x);
boolean hasPath_DP2 = fp.findPath_dp2(endPivot_x, endPivot_y, paths_dp2, cache);
if(hasPath_DP2)
printPath(paths_dp2);
else
System.out.println("dp2 finds no path");
}
private static void printPath(ArrayList paths){
for(int i = paths.size() - 1; i >= 0; i--)
{
System.out.print("");
System.out.print(" ");
}
}
}
View Code
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5705319.html，如需转载请自行联系原作者 |
【本文地址】