求助一道路径的问题

abcd12344 发表于 2021-7-22 04:18
如果只返回一个路径的话，不应该是O(N^2)吗？因为每个点最多只走一遍。

不对哦，如果是O(N^2)，那我最开的方法就是对的，但是在最坏情况下，不管是BFS还是DFS都是需要穷举所有可能的路径，那就是所有数字的全排序，所以BFS和DFS最坏情况下就是Brute Force。

我们还可以从结点访问的次数来看，我们以DFS为例，你每backtrack一步，需要干嘛呢？需要把之前其他路径路过的结点全部重置成没有访问的状态，那么这样怎们可能每个结点之访问一次呢？所以从这点来看，也不可能是O(N^2)哒

thrillerの空 发表于 2021-7-21 21:19
不对哦，如果是O(N^2)，那我最开的方法就是对的，但是在最坏情况下，不管是BFS还是DFS都是需要穷举所有可 ...

只需要一条路径的话，是不需要重置访问状态的。因为当访问到一个节点后，如果这个节点是死路的话就不会再走了，如果是有效路径，就不会回来了。而当需要所有路径时，某一个可以走到终点的点可能有另一条路也经过它，所以我们才在backtrack里重置它的状态。

另外感谢你前面分享的两个算法，我都没见过，去研究研究。Dijkstra好像也是O(N^2)。。。

abcd12344 发表于 2021-7-22 11:31
只需要一条路径的话，是不需要重置访问状态的。因为当访问到一个节点后，如果这个节点是死路的话就不会再 ...

你的分析思路有点问题哦，无论是一条，还是穷举所有条，都是必须遍历所有的路径，只是一条只要我们找到一条就结束算法，穷举需要全遍历，但是一条下最坏还是得全遍历。比如，我们假象下面这个极端情况，也就是除了终点，其他点我们都可以访问：

以最中间那个1为例，你基本有好多种路径都会经过它，那至少你之前说的每个顶点只访问一次，是不对的哦。

至于Dijkstra，之前有点口误，它得时间复杂度应该是O(mlogn)，m为边数，n为顶点数，接近线性时间，而不是我之前说得O(n+m)，你说得O(N^2)也是对得，但是是naive implementation，如果你用heap去实现，就能得到O(mlogn)，之前有点记混了，不好意思呀。

我之前说得两个算法都是图论里面单一源最短路径问题，你有兴趣可以去看看哦，还是很经典得算法。

thrillerの空 发表于 2021-7-22 00:33
你的分析思路有点问题哦，无论是一条，还是穷举所有条，都是必须遍历所有的路径，只是一条只要我们找到一 ...

额，抱歉我可能是钻了牛角尖了。希望没有浪费你的时间。因为这个图没有正确答案，所以会遍历所有"点"，而不是所有路径。所以最坏情况下应该就是O(N^2), 就是所有点的个数。
比如这个图，它走的路径就是
(0  0)->(1  0)->(2  0)->(2  1)->(1  1)->(0  1)->(0  2)->(1  2)
我贴上代码你看看

1. import java.util.*;
   
2. 
   
3. public class FindPath {
   
4.     static List<Integer> curr;
   
5.     static List<List<Integer>> ans;
   
6.     public static void main(String[] args) {
   
7.         List<List<Integer>> r = findPath(new int[][]{{1, 1, 1},
   
8.                                                     {1, 1, 1},
   
9.                                                     {1, 1, 2}});
   
10.         for(List<Integer> l : r){
    
11.             System.out.println(l);
    
12.         }
    
13.     }
    
14. 
    
15.     public static List<List<Integer>> findPath(int[][] grid){
    
16.         curr = new ArrayList<>();
    
17.         ans = new ArrayList<>();
    
18.         curr.add(grid[0][0]);
    
19.         backtrack(grid, new HashSet<>(), 0, 0);
    
20.         return ans;
    
21.     }
    
22.     public static void backtrack(int[][] grid, Set<Integer> seen, int x, int y){
    
23. //         if you jsut need to return one path, update this line and the ans list
    
24.         System.out.print("(" + x + "  " + y + ")->");
    
25. //        if(ans != null) return;
    
26.         int m = grid.length;
    
27.         int n = grid[0].length;
    
28.         seen.add(x * m + y);
    
29.         if(x == m - 1 && y == n - 1) {
    
30.             ans.add(new ArrayList<>(curr));
    
31.             return;
    
32.         }
    
33.         int[][] Dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
34.         for(int[] dir: Dirs){
    
35.             int nextX = x + dir[0];
    
36.             int nextY = y + dir[1];
    
37.             if(nextX >= 0 && nextX < m && nextY >= 0 && nextY < n &&
    
38.                     !seen.contains(nextX * m + nextY) && grid[nextX][nextY] <= grid[x][y]){
    
39.                 curr.add(grid[nextX][nextY]);
    
40.                 backtrack(grid, seen, nextX, nextY);
    
41.                 curr.remove(curr.size() - 1);
    
42.             }
    
43.         }
    
44.     }
    
45. }
    

复制代码

abcd12344 发表于 2021-7-22 12:59
额，抱歉我可能是钻了牛角尖了。希望没有浪费你的时间。因为这个图没有正确答案，所以会遍历所有"点"，而 ...

没关系哦，我也不是大佬呢，也是转专业的选手呢。我写了一个较为严格的数学证明，可以至少说明这题的时间复杂度不是O(n^2)，而是O( 3^ (n * n) )，证明过程如下：

假设我们现在有一个connected的图，如下图所示，任意顶点可以到达其他任何一个顶点

从1开始，搜索所有可能的路径，如下图：

规定组合的公式写法：

那么所有可能经过的路径组合：

C_1_1 * C_3_1 * C_2_1 * C_1_1

那么现在假设我们有n个顶点，也是connected的图，那么所有经过的路径共有多少呢：

C_1_1 * C_n-1_1 * C_n-2_1 * C_n-3_1 * .... * C_n-(n-3)_1 * C_n-(n-4)_1 * C_n-(n-2)_1 * C_n-(n-1)_1

最后带入组合C的公式：

1 * (n-1) * (n-1) * (n-3) * ..... * 4 * 3 * 2 * 1

现在这个公式不是阶乘n!的定义么？

但对于有终点的题目，我们不需要最后顶点不为终点的路径，你可以减少路径的个数，但总的量级也不会少于之前的n!，比如刚才那个例子，终点为4，那么之前的路径图为：

那么，现在题目每个顶点最少只有3种选择（顶点和终点除外），上下左右，那么最后的时间复杂度有多少呢？

这也就是说你确定了i个顶点，i+1个顶点最少只有3个选项可选，但之前我们有n - i个选择，所以最后的公式可以简化为：

1 * 3 * 3 * 3 * ..... * 3 * 3 * 1

现在n*n个顶点，那时间复杂度至少为3 ^ (n * n)，和n^2完全不是一个量级的哦。

另外，有个小小的建议哦，对于时间复杂度这种分析，不能说某一种情况是这样，然后把代码拿出来证明哦，这种证明方式没有什么意义，要说明复杂度问题，最好的方式就是general case，general analysis，然后严谨的推理证明，所以你之前的那种说明方式，不太好哒，嘛，不过这当然是个人建议啦~

thrillerの空 发表于 2021-7-22 02:18
没关系哦，我也不是大佬呢，也是转专业的选手呢。我写了一个较为严格的数学证明，可以至少说明这题的时间 ...

哈哈，非常感谢。你真的太走心了

abcd12344 发表于 2021-7-22 14:27
哈哈，非常感谢。你真的太走心了

没事哒，一起学习一起进步哒

在bfs的时候，用一个n*n matrix 记录每个节点的上一个节点。然后从终点开始就找上一个节点，就能重构出一条路径。

thrillerの空 发表于 2021-07-21 21:33:47
你的分析思路有点问题哦，无论是一条，还是穷举所有条，都是必须遍历所有的路径，只是一条只要我们找到一条就结束算法，穷举需要全遍历，但是一条下最坏还是得全遍历。比如，我们假象下面这个极端情况，也就是除了终

没仔细看代码，但是最中间的1走过一次发现走不通就不用再走了呀

银河系搞钱指南 发表于 2021-7-22 19:34
没仔细看代码，但是最中间的1走过一次发现走不通就不用再走了呀

这个我在中间楼有比较严格的数学证明，你有兴趣可以看看哦：

https://www.1point3acres.com/bbs ... 29&pid=15779500

你说的不用再走了是当前的路径不走了，但是其他路径是要再重复访问的，这个和遍历这个图的BFS和DFS是不一样的，现在是穷举所有路径