【go】求从第一列走到第n列的最短路径

• Z时代
• 2024-01-10
• 分类：技术分享

如上表所示。求从第一列到第n列的路径" title="最短路径">最短路径，行数不定，列数不定。
这种情况下用什么算法比较好

可能说的不大清楚，例如有一条路径：第一列的11，第二列的10，第三列的28
那么这条路径的长度为(|10-11|)+(|28-10|)

回答

最短路径的算法网上可以查到很多，可惜几乎都是针对点到点的。
题主这次的问题，是N点到M点之间的最短路径，没法直接套用。
我有一个想法，可以把这题转变一下，如图，原有的点之间的距离，可以通过abs(value1 - value2)来确定。（图中为了示意，只标示了部分距离，没有全部标示）
然后，在开始出添加一个辅助点B,B到达第一行的所有点的距离都是0
同样的，在最后添加一个辅助点E，最后一行的所有点到E的距离都是0
题目就转变为求B到E的最短路径，这样就可以套用点到点的最短路径的算法了。

第一列到第n列的最短路径（两列之间的距离为差值的绝对值，例如11与14的最短距离为4，11与10的最短距离为1）

|(11 - 14 )| = 4？
|(11 - 10 | = 1;

楼主真的很抱歉不知道您在说什么。。 算第一列到第N列到最短路径？？ 不能直接算嘛

相临两列之间的最短路径加起来不就是1-n的最短路径之一吗，贪婪算法？

假如 三条路的长度为 x,y,z 假如单纯的通过foreach循环可能造成复杂度为f(xy) + f(yz)

所以如和去做才能减少复杂度
第一假如我x 走 y
假设我们为两条路xy进行排序(小到大排序) 我从 x 的最小值(键值0)11开始走起,最近的可能是y的最小值10(键值0)做判断,假设y的值大于x的话,那么x10到y的最小路径就只有y0.假如比x10要小,那么我们继续往y的下一个键值判断y[1],直到找到比x10要大的数(假设为y[y3]),从中判断到底是y[y3]小,还是yy3-1.从中找到最小路径,假设找到0时候可以直接跳出循环

或者换一种思维,把所有的列的数据放到一个二维数轴,以第一列的数据作为原点,路线向两边扩散,只要哪个最短的线能连接所有列的数据,那么那路径应该是最短的

做好二位数轴之后,一眼看就知道
15,18,17
15,14,17
两种都是路径最短

此题如果穷举所有n₁ n₂ n₃ ... （n_k是每列的大小）条路径，n行n列的话复杂度就是O(nⁿ)。下面借助有向图最短路径算法可将复杂度降为O(n⁴)。

• 把给定矩阵中每个元素的位置作为节点，相邻两列节点之间的“距离”作为边的权重，构建有向图。这一步的复杂度为

$$O(n_1 n_2 + n_2 n_3 + \cdots + n_{n-1}n_n)=O(n^3)$$

• 问题转化为求解有向图的最短路径。Dijkstra算法可计算单节点源到其它所有节点的最短路径，复杂度为O(E + V log V)，其中E和V分别是图的边数和节点数。在本问题中，E=O(n³)，V=O(n²)。我们需要计算以第一列所有节点为源的到最后一列所有节点的最短路径。这一步的复杂度就是：

$$n\ O(E+V\log{V})=n\ O(n^3+n^2\log{n^2})=O(n^4)$$

• 最后需要选择n个结果中最好的一个，复杂度为O(n)。

综上可知总复杂度为O(n⁴)。

我觉得你要是不考虑时间负责都的情况下，直接暴力枚举是可以的，否则的可以考虑用动态规划的思路去做

以上是 【go】求从第一列走到第n列的最短路径 的全部内容， 来源链接： utcz.com/a/106989.html