我有一群人,他们每个人都有朋友名单和敌人名单.我想把它们排成一行(桌子上没有圆圈),所以没有敌人,只有朋友彼此相邻.
输入示例:https://gist.github.com/solars/53a132e34688cc5f396c
我想我需要使用图形着色来解决这个问题,但我不确定如何 – 我想我必须省略朋友(或敌人)列表以使其更容易并映射到图表.
有谁知道如何解决这些问题,并告诉我,如果我走在正确的道路上?
代码示例或在线示例也不错,我不介意编程语言,我通常使用Ruby,Java,Python,JavaScript
非常感谢你的帮助!
最佳答案评论中已经提到,这个问题相当于旅行商问题.我想详细说明一下:每个人都相当于一个顶点,并且边缘位于顶点之间,这些顶点代表可以相互对接的人.现在,找到可能的座位安排相当于在图中找到哈密顿路径.
所以这个问题就是NPC.最天真的解决方案是尝试所有可能的排列,从而导致O(n!)运行时间.有许多众所周知的方法比O(n!)表现更好,并且可以在网上免费获得.我想提一下Held-Karp,它运行在O(n ^ 2 * 2 ^ n)并且非常直接代码,这里是python:
#graph[i] contains all possible neighbors of the i-th persondef held_karp(graph): n = len(graph)#number of persons #remember the set of already seated persons (as bitmask) and the last person in the line #thus a configuration consists of the set of seated persons and the last person in the line #start with every possible person: possible=set([(2**i,i) for i in xrange(n)]) #remember the predecessor configuration for every possible configuration: preds=dict([((2**i,i),(0,-1)) for i in xrange(n)]) #there are maximal n persons in the line - every iterations adds a person for _ in xrange(n-1): next_possible=set() #iterate through all possible configurations for seated,last in possible: for neighbor in graph[last]: bit_mask=2**neighbor if (bit_mask&seated)==0: #this possible neighbor is not yet seated! next_config=(seated|bit_mask,neighbor)#add neighbor to the bit mask of seated next_possible.add(next_config) preds[next_config]=(seated,last) possible=next_possible #Now reconstruct the line if not possible: return []#it is not possible for all to be seated line=[] config=possible.pop() #any configuration in possible has n person seated and is good enough! while config[1]!=-1: line.insert(0,config[1]) config=preds[config]#go a step back return line
免责声明:此代码未经过适当测试,但我希望您能得到它的要点. 总结
以上是内存溢出为你收集整理的python – 找到“好”邻居的算法 – 图着色?全部内容,希望文章能够帮你解决python – 找到“好”邻居的算法 – 图着色?所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)