求助一道路径的问题

thrillerの空 发表于 2021-07-22 05:21:41
这个我在中间楼有比较严格的数学证明，你有兴趣可以看看哦：

https://www.1point3acres.com/bbs/forum.php?mod=redirect&goto=findpos

我有点不太明白，这道题只用返回一条路径，所以不需要穷举吧？走过的点就不需要重新走了。还有你说的Dijkstra比bfs/dfs快是为什么呢？Dijkstra是为了求有权重图最短路径，这个问题是怎么转换成有权重图的？我感觉这道题是直接转换成无权重有向图。另外有权重图包含了无权重图，所有无权重用bfs/dfs来遍历的图都可以用Dijkstra，只不过权重设为1，所以Dijkstra不应该比dfs/bfs更快吧？Dijkstra感觉是复杂一点的bfs，复杂一点的地方在于每走一步要多算一次距离最近的点，哪怕用heap每次往下一个点走的时候也是要比bfs多logE的时间

meimingzi2020 发表于 2021-7-22 22:32
我有点不太明白，这道题只用返回一条路径，所以不需要穷举吧？走过的点就不需要重新走了。还有你说的Dijks ...

1）我有点不太明白，这道题只用返回一条路径，所以不需要穷举吧？走过的点就不需要重新走了。
对于这点，你需要明确一下：返回一条路径不等于只搜索一条路径，它是返回穷举所有路径后的一条符合要求的路径；那什么情况走过的点就不需要重新走了呢？那就是你用BFS和DFS去遍历处所有的结点，那走过的点就不需要重新走了，但是这里不是。

----------------------------------------

2）还有你说的Dijkstra比bfs/dfs快是为什么呢？Dijkstra是为了求有权重图最短路径，这个问题是怎么转换成有权重图的？

这题可以转换成有权重的图的呀，只要把条件看成求最短权重的路径就行了，每个格子的数字就是权重。

----------------------------------------
3）我感觉这道题是直接转换成无权重有向图。另外有权重图包含了无权重图，所有无权重用bfs/dfs来遍历的图都可以用Dijkstra，只不过权重设为1，所以Dijkstra不应该比dfs/bfs更快吧？Dijkstra感觉是复杂一点的bfs，复杂一点的地方在于每走一步要多算一次距离最近的点，哪怕用heap每次往下一个点走的时候也是要比bfs多logE的时间



这里你问的效率问题，就是和1）是一样，如同我说的那样，BFS和DFS去求解最短路径就是再穷举所有路径的可能性，Brute force，效率是根本没法看的哦。而且Dijkstra可不算稍微复杂一点的BFS额，它虽然和BFS有点像，但它用到了Greedy，对于非负边，它用heap去实现的效率是非常高的，接近线性时间。

但是比较好的情况，这题BFS是快于Dijkstra的，比如每走一步，直接能走到终点，但是对于最坏情况，BFS还是得穷举所有可能得路径，所以最终的时间复杂很高，但Dijkstra为O(mlogn)

thrillerの空 发表于 2021-7-22 08:21
这个我在中间楼有比较严格的数学证明，你有兴趣可以看看哦：

https://www.1point3acres.com/bbs/forum ...

你这个图的的剪枝有点问题吧，你找到第一个4不就直接return了么？
这么想我不知道对不对：
如果起始点在SCC里，dfs一遍就能找到
如果不在SCC里，那么把他们各自所在的SCC当成node，以起点DFS这个DAG也是一遍dfs就能找到

或者如果你是在说BFS，那当我没说哈





补充内容 (2021-07-23 11:44 +08:00):
bfs也不对啊，bfs每个node的level记录一下，别忘回走就行了呀，然后用一个matrix记录一下parent，也不会全排列呀

银河系搞钱指南 发表于 2021-7-23 11:35
你这个图的的剪枝有点问题吧，你找到第一个4不就直接return了么？
这么想我不知道对不对：
如果 ...

1）你这个图的的剪枝有点问题吧，你找到第一个4不就直接return了么？

剪枝是对的哦，第一条我删除的是后面所有两个路径；

------------------------------------
2）这么想我不知道对不对：如果起始点在SCC里，dfs一遍就能找到，如果不在SCC里，那么把他们各自所在的SCC当成node，以起点DFS这个DAG也是一遍dfs就能找到。

对于这点，你需要明确一下：返回一条路径不等于只搜索一条路径，它是返回穷举所有路径后的一条符合要求的路径；那什么情况走过的点就不需要重新走了呢？那就是你用BFS和DFS去遍历图所有的结点，那走过的点就不需要重新走了，但是这里不是。

而且对于SCC和DAG和这题没有关系，它们两个要用的有向图，这里是无向图，不存在SCC和DAG，即使存在SCC，因为是无向图，所以整个图就是一个SCC，没有其他的了。

你可能理解错我画这个图的意思了，我这个图的有向是遍历穷举每个路径的顺序，和SCC和DAG没有关系。

------------------------------------
3）bfs也不对啊，bfs每个node的level记录一下，别忘回走就行了呀，然后用一个matrix记录一下parent，也不会全排列呀

这点我和之前的一起解释一下哦，我看楼里很多童鞋都认为这题只用走一条路径，有记录重复，所以不会穷举。但这样的认识是不对的，你们所说的方式是只遍历所有点和边一次才算这样的情况。你们记录的重复，只是一条路径的重复，当你们backtrack，就会重置之前往前走的所有结点状态，这点和遍历结点和边一次的情况非常不一样，所以最坏情况会发生穷举所有可能的路径。

我之前的数学证明就是说，对于一张connected图（任意顶点可到其他所有顶点），那么从某个起点出发，可能的路径就是：n! 条，这个证明过程我在上面有些。那么现在即使有终点（对于现在的问题），最多也就是对穷举搜索进行剪枝，但是不会asymptotically减少时间复杂度。

而且很多童鞋认为这题的时间复杂度是O(n^2)，这个也是不太对的哦。这个可以用排序来说明，其实排序算法本身也是一种DFS全排序的搜索（naive implementation，比如插排，选排或者冒泡），什么意思呢？给定n个元素，对于数组中的第i个格子，它的可能元素选择其实是确定的（假定元素全部unique），只是我们需要从n - (i-1) 个元素找到这样的元素，所以我们需要花费n - (i-1) 的时间去找到这样的元素，那么现在有n个格子，所有最后的时间复杂度就是：

n + (n-1) + (n-2) + ....... +  3 + 2 + 1 = O(n^2)；

但现在图路径的遍历就完全不一样了，对于这个场景，每个格子（也就是这个格子放什么结点）有多少种可能呢？有n - (i-1)选择，但是我们找到这样的顶点只用O(1)，因为边的访问是O(1)。但是这个格子的可能性，可以和前面格子的可能性发生组合，所以上面对于排序里面相加的关系，就变成了相乘的关系：

n * (n-1) * (n-2) * .......* 3 * 2 * 1 = O(n!);

而且你提到了剪枝，不知道你知不知道AI里面的alpha-beta pruning，这个东西其实就是DFS的剪枝操作，避免搜索完全不可能的路径，用来提升效率，和我刚才讲的图例非常相似（访问到终点，后续的路径就可以剪掉），那么应该讲过这个方法对时间复杂度的影响，如果branching factor是 b，搜索深度是d，那即使有alpha-beta pruning，最后的时间复杂度还是O(b ^ d)，因为剪枝只能提高实践的效率，但是不能提高理论效率，因为最坏情况还是得搜索domain里面的所有分支路径。又因为AI问题的domain非常的巨大，有时是天文数字级别的，所以即使不能提升理论效率，能大幅提升实践的效率。但这里我们都是讨论算法题，非AI的问题。

其实这个分析可以用到这道题，对于这题，branching facter最少是多少呢？四个角的格子选择最少，只有2个方向选择，深度是多少呢？现在有n*n个数，所以最后的时间复杂度是：Ω( 2 ^ (n*n))，我之前的分析用的branching facter是3，范围大了一点，但是带入公式还是：Ω( 3 ^ (n*n))，和我之前的分析是一样的哦。

通过排序和剪枝的例子，不知道你能理解我的意思么？巴拉巴啦写了很多哦

thrillerの空 发表于 2021-7-23 17:50
1）你这个图的的剪枝有点问题吧，你找到第一个4不就直接return了么？

如果有童鞋觉得我之前讲的太抽象，太理论，可以针对这题自己写一个，无论是BFS还是DFS，然后输入一个 1000*1000 的最坏情况案例，也就是我之前除了终点，其他点都是可以随便的走的，然后看看自己写的算法能不能结束哦。
为什么这样说呢？如果时间复杂度是O(n^2)，那这个案例需要至少计算多少次呢？ 1000*1000 = 10 ^ 6，也就一百万次，以现在普通PC的性能来说，问题不大，但如果是我说的O(2^(n*n))呢？现在要计算多少次呢？2 ^ (10^6)，这个数字有多大呢？大家应该知道int的最大值：2^31 - 1，是2147483647，也就是21亿次计算，这个量级，普通PC是hold不住了，那么对于2 ^ (10^6)呢？用int来丈量，2 ^ (10^6) / 2^31，大约32258个int的大小，估计给你个超算恐怕才行吧。而且这个O(2^(n*n))还是很保守的估计，因为只有四个位置只有2个选择，其他都是3个或4个，那就更大了。

讲道理，凡是需要把具体路径打出来的，都是dfs比较简单。然后如果需要知道最短路的情况，可以先用bfs跑一遍，知道最短路多长，然后再跑dfs的时候用那个结果剪枝

你如果硬要用bfs的话，就得存很多状态，比如走到xy的时候，之前都经历过哪些格子，然后还得去重之类的，很麻烦

剪枝问题：搜索到4的时候找到了答案，我们用一个flag来标记。然后返回到1，这个时候会进入3 和2对吗？但因为我们已经找到了，所以它不会进入3和2。
这里需要注意的是：
      当我们只需要一条路径时，我们不会再backtrack后清除seen的数据，seen是全局的，而且一直在不断变大。
      每次从backtrack返回以后就会回到上层backtrack的遍历方向的循环中，这时候会有检查flag和seen来判断是否进入后面的节点。
1000长度用bfs确实可以跑的，结果秒出。dfs因为太深了会溢出。

o彩蝶寻梦o 发表于 2021-7-23 08:14
讲道理，凡是需要把具体路径打出来的，都是dfs比较简单。然后如果需要知道最短路的情况，可以先用bfs跑一遍 ...

对的，bfs保存路径比较麻烦。需要一条还好走过的就不走了，需要所有路径的时候每个点都得判断是否在当前路径出现过。

thrillerの空 发表于 2021-7-23 05:50
1）你这个图的的剪枝有点问题吧，你找到第一个4不就直接return了么？

对，咱俩的分歧就在这，我的意思是你不用遍历每条路径，你只用遍历每条边，不用backtrack

我们以这个图为例
111
111
11X

首先BFS一遍，确认X是不是联通的，这个只要O(V+E)，这个没问题吧？

如果X不是联通的，直接return了

如果是联通的，无论用matrix记录parent还是再重新走一遍DFS也都是O(v+e)就够了

我觉得你说的问题是：你要用全排列来dfs证明X的连通性，不作任何优化的worst case是全排列，但是我们可以用一个matrix来记录每个点的搜索记录，类似dp
还是以上面的图为例，node的index为下
123
456
789

假设第一次DFS我们走的是12365874
4是死胡同，47依次退栈，在8的时候：
1. 如果9是联通的，直接return了
2. 如果9不联通，退栈到5，这个时候，5不用再去dfs到4了，因为4我们已经visited了
我们这样一路退栈到1,发现没找到9，直接就return false了，而不用1再去dfs（4）

我们想一个general的case：

我们在dfs的某一个node x上，x 有联通节点 y,z
我们从y退栈回来，发现z已经visited了，还需要去z么？不需要
因为在当前路径上：
1.如果终点在Z下游，在dfsZ的时候就找到了，不会退栈到x
2.如果终点在Z上游，那么我们根本就不可能dfs到Z

还是以上面走12365874的图为例，我们退栈到5的时候，4就不用再看了，因为4下游没有点，4上游有7，5和1,都不可能在这些点上
因为他们是早进栈的，如果他们是终点之前就退栈了，如果终点在他们别的下游分叉下，我们也没必要走环回去explore，直接退栈到相应的点，继续dfs就行

这道题有两个部分：1.证明连通性，2.找到一条路
1.连通性BFS，DFS，上面说了O(E+V)就够了
2.找到一条路，DFS，O(E+V)

我们的分歧主要在连通性上我感觉，BFS是不是O(V+E)就能解决连通性？因为是一层一层出去的，不会走回路
如果一个问题 BFS  O(V+E)能解决，DFS却要n！，这合理么？

银河系搞钱指南 发表于 2021-7-23 21:18
对，咱俩的分歧就在这，我的意思是你不用遍历每条路径，你只用遍历每条边，不用backtrack

我们以这个 ...

后面又想了想，你是正确的哦，这道题我想复杂了，它本质不是最短路径路径，而是从起点到终点是否又通路的问题，那这个问题，BFS和DFS一边遍历结点和边就能解决了，是我想太多了，哈哈哈，大型翻车现场哦。

但是你的解释，我看来有两个小问题哦：

1） 1.证明连通性，2.找到一条路

这两个问题是等价的，你找到了一条路，一定能得到连通性；你有了连通性，必然又一条路，所以不用分两步，可以一步到位；


2）你在解释里面用的上游，下游我实在没有看懂哦。我就用下面这个图例证明一下为什么这题不是穷举所有路径，而是一次遍历所有结点和边：

上图表示DFS，我们从(i-1,j)经过(i,j)，然后走到(i+1,j)，然后从(i+1,j) trackback到(i,j)，然后(i-1,j)是我们之前trackback经过的一个结点，图中所有标红结点表示这些结点都是visited，那么我们是否还需要从(i,j)再次访问(i-1,j)呢？我们就用反正法来证明：

也就说我们现在假设，我们之前经过了(i-1,j)，没有抵达终点，现在我们trackback到(i,j)，但是还存在一条路径从(i-1,j)经过，也可以到达终点。但我们这里会得到矛盾，因为只要有通路那DFS会搜索到，不存再经过某点，没有搜索到通路，但该点又存在通路的情况，这与DFS的性质是矛盾的，所以我们的原假设是错误的，我们不需要再次搜索(i-1,j)这点。

最后谢谢你能和我“杠”这么久哦，否则我都没有办法发现自己的错误哒。