求助-线段连接最短连接路径问题

小召哥

如图所示一平面上，存在若干条有向线段L1(s1,e1)、L2(s2,e2)、L3(s3,e3)…Ln(sn,en)，线段的方向总是自下而上。
其中，s、e，分别代表线段的起始点和终点的坐标，即所有线段两端点坐标已知。
要求：线段之间只能依次首尾相连，如图中红色的连接线段
问题：怎样求解出一个最优的连接顺序，使得所有线段间的连接线长度最短？

小召哥

我做项目时想的一个模型，不知道能不能求解出来

Treenewbee

n比较小时可以穷举，
n比较大时可以动态规划，比较简单的背包问题

小召哥

Treenewbee 发表于 2023-2-28 15:13
n比较小时可以穷举，
n比较大时可以动态规划，比较简单的背包问题

大佬说的太简略了，不太懂呀，能否说明一下解题思路呀

Treenewbee

所谓穷举，就是将n条线段间的连线存入一个n*n的数组，共n！种排列。设一个全局变量，逐个比较是否最小值即可

xfhaoym

这好象比泛函的变分法还复杂．玩玩看．

Nicolas2050

连图论都没学过？

xfhaoym

有的老师说，画成表，把所有的路径都填在里面。然后计算看哪个最短。

Zhouyue

定义状态：设f[i][j]表示连接第i个线段到第j个线段的最短距离。

初始化状态：f[i][i+1] = 0，表示相邻两条线段之间的距离为0。

状态转移方程：枚举中间点k，f[i][j] = min{f[i][k] + f[k][j] + dis(i,j,k)}，其中dis(i,j,k)为连接线段i、j、k的长度。

最终结果：f[1][n]为所求的最短距离。

时间复杂度为O(n^3)。