求助-线段连接最短连接路径问题
如图所示一平面上,存在若干条有向线段L1(s1,e1)、L2(s2,e2)、L3(s3,e3)…Ln(sn,en),线段的方向总是自下而上。其中,s、e,分别代表线段的起始点和终点的坐标,即所有线段两端点坐标已知。
要求:线段之间只能依次首尾相连,如图中红色的连接线段
问题:怎样求解出一个最优的连接顺序,使得所有线段间的连接线长度最短?
我做项目时想的一个模型,不知道能不能求解出来:'( n比较小时可以穷举,
n比较大时可以动态规划,比较简单的背包问题 Treenewbee 发表于 2023-2-28 15:13
n比较小时可以穷举,
n比较大时可以动态规划,比较简单的背包问题
大佬说的太简略了,不太懂呀,能否说明一下解题思路呀 所谓穷举,就是将n条线段间的连线存入一个n*n的数组,共n!种排列。设一个全局变量,逐个比较是否最小值即可 这好象比泛函的变分法还复杂.玩玩看. 连图论都没学过?:o 有的老师说,画成表,把所有的路径都填在里面。然后计算看哪个最短。 定义状态:设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]