|
|
发表于 2020-8-2 15:45:01
|
显示全部楼层
算法的讨论相当多，如果楼主对这个算法感兴趣，可以尝试google一下：邮递员问题，淬火问题，遗传算法，启发式算法等，基本都是这个算法的讨论
其基本思路：
判断路径最短的一个显著标志是，必然不存在两个交叉的连线。
算法：
使用Dijkstra来生成最初的节点，之后，随机提取两个线段，交换顶点，比如，线段ab、cd，交换之后变为ad、bc，然后计算两个线段的总和是否有缩短。提取的次数决定最后的理想度。
交换次数达到一个临界值之后，结果不能再优化。
这个算法存在一个比较大的缺陷，在这样的连线图中，必然存在一个线段从图的一边一直连接到另外一边。即，永远得不到最优解。
改进算法：
需求：概率论和数理统计。
对上述交换算法的改进，在交换过程中，不是严格的判定是否缩短，而是允许在交换过程中，出现一定程度的总和增加的情况出现，增加比例可以计算。然后，算法中要求记录几步的交换过程，并，在几步之后，始终没有减少的情况下进行回退。反复叠代使用，直到达到没有任何两个连线之间存在交叉，达到最优解结果。
所有相关数学模型因为篇幅原因未曾列出，只是表述一个大概思路，相信应该可以让你的面试官满意了！ |
|
