Nit*_*arg 9 algorithm optimization
圆桌会议.并且有n个人,其中一些人是彼此的朋友.如果他是朋友,坐在桌子上的人可以与他附近的人互动.
我们必须找到一种算法来将n个人安排在桌面上,以便最大化整个交互.
Mar*_*ers 7
这个问题可以减少到旅行商问题.
将每个人视为图表中的节点.在朋友之间移动的成本是0,非朋友之间的移动成本是1.现在的任务是找到成本最低的哈密尔顿循环.这是NP难问题.
一个贪婪的算法是先让最少朋友的人,然后尝试将他的两个朋友放在他旁边(如果他有两个以上的朋友,选择他们自己最少朋友的那两个朋友).继续这样做,如果可能的话,将朋友放在朋友旁边,直到每个人都被安置.这不能保证找到最佳解决方案,但计算速度非常快.
归档时间：
13 年，10 月 前
查看次数：
365 次
最近记录：