Algoritmo per trovare "buoni" vicini - colorazione del grafico?

Question

Ho un gruppo di persone e per ognuna di esse una lista di amici e una lista di nemici. Voglio allinearli (senza cerchio come su un tavolo) in modo che preferibile nessun nemico ma solo gli amici sono uno accanto all'altro.

Esempio con l'ingresso: https://gist.github.com/solars/53a132e34688cc5f396c

penso di aver bisogno di usare grafico colorazione per risolvere questo, ma non sono sicuro di come - penso di avere a lasciare fuori i tuoi amici (o nemici) lista di fare è più facile e mappa su un grafico.

Qualcuno sa come risolvere questi problemi e può dirmi se sono sulla strada giusta?

Esempi di codice o esempi online sarebbe anche bello, non mi dispiace il linguaggio di programmazione, io di solito uso Ruby, Java, Python, Javascript

grazie mille per il vostro aiuto!

Answer 1

È già menzionato nei commenti che questo problema è equivalente al problema del venditore ambulante. Mi piacerebbe approfondire:

Ogni persona è equivalente a un vertice e i bordi sono tra vertici che rappresentano le persone che possono sedersi l'una con l'altra. Ora, trovare una possibile disposizione dei posti è equivalente a trovare un percorso hamiltoniano nel grafico.

Quindi questo problema è NPC. La soluzione più ingenua sarebbe provare tutte le possibili permutazioni risultanti in un tempo di esecuzione O(n!). Ci sono molti approcci ben noti che funzionano meglio di O(n!) e sono liberamente disponibili sul web. Vorrei citare Held-Karp, che viene eseguito in O(n^2*2^n) ed è piuttosto semplice per il codice, qui in pitone:

#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 

Esonero di responsabilità: questo codice non è correttamente testato, ma spero si può ottenere l'essenza di esso.