Algorytm znajdowania "dobrych" sąsiadów - kolorowanie wykresu?

Question

Mam grupę ludzi i dla każdego z nich listę przyjaciół i listę wrogów. Chcę je uszeregować (bez kółek, jak na stole), tak, aby preferowani nie byli wrogowie, a tylko przyjaciele są obok siebie.

Przykład z wejściem: https://gist.github.com/solars/53a132e34688cc5f396c

myślę, że trzeba użyć kolorowanie grafu, aby rozwiązać ten problem, ale nie jestem pewien, w jaki sposób - Myślę, że mam opuścić przyjaciół (lub wrogów) Lista zrobić łatwiej i odwzoruj na wykres.

Czy ktoś wie, jak rozwiązać takie problemy i może mi powiedzieć, czy jestem na dobrej drodze?

próbki kodu lub przykłady forum będzie również miły, nie przeszkadza mi język programowania, Zwykle używam Ruby, Java, Python, Javascript

dziękuję za pomoc!

Answer 1

Już wspomniano w komentarzach, że ten problem jest równoważny problemowi z komiwojażera. Chciałbym to rozwinąć:

Każda osoba jest odpowiednikiem wierzchołka, a krawędzie są pomiędzy wierzchołkami, co oznacza osoby, które mogą siedzieć obok siebie. Teraz znalezienie możliwego układu siedzeń jest równoznaczne ze znalezieniem ścieżki Hamiltona na wykresie.

Ten problem dotyczy NPC. Najbardziej naiwnym rozwiązaniem byłoby wypróbowanie wszystkich możliwych permutacji powodujących upływ czasu. Istnieje wiele dobrze znanych podejść, które działają lepiej niż O(n!) i są swobodnie dostępne w Internecie. Chciałbym wspomnieć Held-Karp, która biegnie w O(n^2*2^n) i jest dość prosta do kodu, tutaj w Pythonie:

#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 

Uwaga: Ten kod nie jest odpowiednio przetestowane, ale mam nadzieję, że można dostać sens tego.