寻路问题--如何找到一条从起点坐标到终点坐标的路径？-白红宇

一，寻路问题介绍

正如提到的从起点(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> <0,1> <1,1> <1,2> <2,2> <2,3> <2,4> <3,4> <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<Point> 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,Boolean>保存顶点Point是否至少存在一条路径可以到达终点。假设顶点<p1,true>，则表示顶点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]==011         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 condition38         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("<" + paths.get(i).x + "," + paths.get(i).y + ">"); System.out.print(" "); } }}

View Code

本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5705319.html，如需转载请自行联系原作者