我有一群人,每个人都有一份朋友和敌人的名单。我想把他们排成一行(桌子上没有圆圈),这样就没有敌人,只有朋友在旁边。在
输入示例:https://gist.github.com/solars/53a132e34688cc5f396c
我想我需要使用图着色来解决这个问题,但我不确定如何-我想我必须省去朋友(或敌人)列表,以便更容易地映射到一个图。在
有没有人知道如何解决这些问题,并能告诉我是否走在正确的道路上?在
代码示例或在线示例也不错,我不介意编程语言,我通常使用Ruby、Java、Python、Javascript
非常感谢你的帮助!在
评论中已经提到,这个问题相当于旅行商问题。我想详细说明一下:
每个人都相当于一个顶点,每个顶点之间的边代表着可以坐在一起的人。现在,找到一个可能的座位安排就相当于在图中找到一条哈密顿路径。在
所以这个问题就是NPC。最天真的解决方案是尝试所有可能的排列,从而导致
O(n!)
运行时间。有许多众所周知的方法比O(n!)
性能更好,并且可以在web上免费获得。我想提一下Held-Karp,它运行在O(n^2*2^n)
中,非常直接地指向代码,在python中:免责声明:这段代码没有经过适当的测试,但我希望你能得到它的要点。在
相关问题 更多 >
编程相关推荐