首页 > 其他分享 >22.9.19-25

22.9.19-25

时间:2022-09-24 16:44:19浏览次数:78  
标签:25 prim 19 py 问题 22.9 解法

关于54中指派飞机去组成通信链路的问题
1.最小生成树
通过查阅资料,得知(若简化问题为连线),则可以套用最小生成树问题的两种解法
参考如下博客运行prim解法,效果如同
https://blog.csdn.net/lnotime/article/details/82313355
image

对应文件:prim.py

2.最少圆包含平面点问题
把这个问题描述成用圆包含点的话更加合理,但是也更复杂,
image
查找了一下,发现这个问题可能是np hard的,但可以近似求解
参考:https://stackoverflow.com/questions/15882202/minimum-number-of-circles-with-radius-r-to-cover-n-points
在其中一个解法的基础上稍作修改并plt画图一下:
image

如果要应用于我们的问题,需要增加一个连接这些圆的步骤,具体这两个方法如何还需要看数据的分布和通信模型。

对应文件:CirclesCoverPoints_1.py

关于动态任务中匹配问题
简单了解了一下匈牙利算法km算法

标签:25,prim,19,py,问题,22.9,解法
From: https://www.cnblogs.com/mortal-berry/p/16725886.html

相关文章