查找 "good" 个邻居的算法 - 图着色？

Question

我有一群人，每个人都有一个朋友列表和一个敌人列表。我想把它们排成一行（没有像 table 那样的圆圈），这样最好没有敌人，只有朋友彼此相邻。

输入示例：https://gist.github.com/solars/53a132e34688cc5f396c

我想我需要使用图表着色来解决这个问题，但我不确定如何 - 我想我必须省去朋友（或敌人）列表以使其更容易映射到图表。

有谁知道如何解决此类问题并告诉我我的方向是否正确？

代码示例或在线示例也很好，我不介意编程语言，我通常使用Ruby、Java、Python、Java脚本

非常感谢您的帮助！

Answer 1

评论里已经提到，这个问题等同于旅行商问题。我想详细说明一下：

每个人都相当于一个顶点，顶点之间的边代表可以坐在一起的人。现在，寻找可能的座位安排等同于在图中寻找哈密顿路径。

所以这个问题是NPC。最天真的解决方案是尝试所有可能的排列，导致 O(n!) 运行时间。有许多众所周知的方法比 O(n!) 表现更好，并且可以在网络上免费获得。我想提一下 Held-Karp，它在 O(n^2*2^n) 中运行并且非常直接地编写代码，在 python 中：

#graph[i] contains all possible neighbors of the i-th person
def 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

免责声明：此代码未经过适当测试，但我希望您能理解其中的要点。

查找 "good" 个邻居的算法 - 图着色？

Algorithm to find "good" neighbours - graph coloring?

python

algorithm

graph

graph-algorithm