找到「好」鄰居的算法 - 圖着色？

Question

我有一羣人，每個人都有一個朋友名單和一個敵人名單。我想把它們排成一行（沒有像桌子上的圓圈），所以最好不要敵人，但只有朋友彼此相鄰。

實例與輸入：https://gist.github.com/solars/53a132e34688cc5f396c

我想我需要使用的圖形着色來解決這個問題，但我不知道如何 - 我想我得離開了朋友（或敵人）列表，以它更容易，並映射到一個圖形。

有誰知道如何解決這些問題，並可以告訴我，如果我在正確的道路上？

代碼樣本或網上的例子也將是不錯的，我不介意的編程語言，我平時使用Ruby，使用Java，Python，Java腳本

非常感謝您的幫助！

Answer 1

它已經在評論中提到，這個問題相當於旅行商問題。我想詳細說明一下：

每個人相當於一個頂點，而邊緣位於頂點之間，這些頂點代表了可以相互坐在一起的人。現在，找到可能的座位安排等同於在圖中找到哈密頓路徑。

所以這個問題是NPC。最天真的解決方案是嘗試所有可能的排列，導致運行時間爲O(n!)。有很多衆所周知的方法比O(n!)表現更好，並可以在網上免費獲得。我想提一提Held-Karp，它運行在O(n^2*2^n)，是非常簡單的代碼，在這裏蟒蛇：

#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 

聲明：此代碼是不正確的測試，但我希望你能得到它的要點。