求从第一列走到第n列的最短路径
博亿娱乐平台下载
博亿娱乐平台下载
当前位置 : 博亿娱乐平台下载 > 博亿娱乐平台

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

11 14 23
12 18 21
13 10 28
15 29 17
25

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

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

  • 3月30日提问
  • 2 评论
  • 邀请回答
  • 编辑

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


|11 - 14 | = 4?
|11 - 10 | = 1;


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

  • 3月30日回答
  • 1 评论
  • 编辑

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

  • 3月30日回答
  • 5 评论
  • 编辑

假如 三条路的长度为 x,y,z 假如单纯的通过foreach循环可能造成复杂度为fxy + fyz

所以如和去做才能减少复杂度
第一假如我x 走 y
假设我们为两条路xy进行排序小到大排序 我从 x 的最小值键值011开始走起,最近的可能是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
两种都是路径最短

  • 3月30日回答 · 3月30日更新
  • 评论
  • 编辑

此题如果穷举所有n1 n2 n3 ... (nk是每列的大小)条路径,n行n列的话复杂度就是Onn。下面借助有向图最短路径算法可将复杂度降为On4

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

$$On_1 n_2 + n_2 n_3 + \cdots + n_{n-1}n_n=On^3$$

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

$$n\ OE+V\log{V}=n\ On^3+n^2\log{n^2}=On^4$$

  • 最后需要选择n个结果中最好的一个,复杂度为On。

综上可知总复杂度为On4

  • 4月1日回答 · 4月3日更新
  • 评论
  • 编辑

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

  • 3 天前回答
  • 评论
  • 编辑

广告位

博亿娱乐平台下载