小召哥 发表于 2023-2-28 14:35

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

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

小召哥 发表于 2023-2-28 14:48

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

Treenewbee 发表于 2023-2-28 15:13

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

小召哥 发表于 2023-2-28 15:37

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

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

Treenewbee 发表于 2023-2-28 15:52

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

xfhaoym 发表于 2023-3-12 19:00

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

Nicolas2050 发表于 2023-3-12 20:46

连图论都没学过？:o

xfhaoym 发表于 2023-3-13 08:13

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

Zhouyue 发表于 2023-7-6 13:31

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

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

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

最终结果：f为所求的最短距离。

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

页: [1]
查看完整版本: 求助-线段连接最短连接路径问题