"良い"隣人 - グラフの色付けを見つけるアルゴリズム？

Question

私は人のグループを持ち、それぞれに友人のリストと敵のリストを持っています。私はそれらを並べる（テーブル上のサークルなし）ので、敵は好まれないが、友人だけが隣にいるようにしたい。入力と

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

は、私はこの問題を解決するために、グラフの色を使用する必要があると思うが、私はどのようにわからない - 私は私が作るために友人（または敵）リストを残していると思いますより簡単にグラフにマップできます。

誰もこのような問題を解決する方法を知っていますか、私が正しい道にいるかどうか教えてください。

コードサンプルやオンライン例もいいだろう、私はプログラミング言語を気にしない、私は通常のRubyやJava、PythonやJavascriptをあなたの助けのための

おかげでたくさん使います！

Answer 1

コメントには既に言及していますが、この問題はセールスマン問題の解決に相当します。私はそれについて詳述したいと思います：

すべての人は頂点に相当し、エッジはお互いに座ることができる人を表す頂点の間にあります。今、可能な座席配置を見つけることは、グラフ内のハミルトニアン経路を見つけることと同じです。

この問題はNPCです。最も純粋な解決策は、すべての可能な並べ替えを試みて、実行時間がになることです。 O(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 

免責事項：私はPythonで、ここで、O(n^2*2^n)で実行され、コードにはかなりまっすぐ進むである、Held-Karpに言及したいと思います。