Come creare set distinti da altri set?

Ecco un suggerimento. Vedo che puoi risolvere questo in 2 passaggi. come segue:

Parte 1 - Identifica coppie idonee

In primo luogo, potremmo identificare, in base alle regole dei requisiti, coppie di dipendenti che potrebbero viaggiare insieme in un unico viaggio utilizzando la matrice sottostante in base al caso dichiarato: {(1,2), (2,3), (3, 4)}

Le celle con x (così come le celle diagonali) rappresentano le istanze in cui 2 dipendenti possono viaggiare insieme perché hanno lavorato insieme.

Inoltre, è implicito che travelTogether (i, j) = travelTogether (j, i) (le celle blu sono dedotte dall'input) e che

travelTogether (i, i)="x" (che significa No o falso).

Le celle non contrassegnate indicano "sì" o vero, cioè la coppia travelTogether (i, j) può viaggiare insieme nello stesso viaggio. Ad esempio, il dipendente 1 può viaggiare con 3 e / o 4. Tuttavia, Employee 3 può viaggiare solo con 1.

Parte2.Identificaicandidatiperviaggio

-Sono2viaggi.

-Seicoppiechedevonoviaggiareinsieme(ononviaggiareaffatto)comeEmployee3.

-Nonhaiunacapacitàmassimaperviaggio.

Perognidipendente,determinailnumerodicompagnidiviaggiodisponibili.

Ordinandoidipendentisulnumerodicompagnidiviaggiodisponibiliotteniamo:

Quindi ciascuno dei dipendenti 2 e 3 può scegliere 1 compagno di viaggio. Partendo dal 2 (selezione arbitraria), si piazza 2 con il suo solo possibile compagno 4. Questo lascia 3 e 1 per viaggiare insieme. Potresti quindi avere 1 viaggio da includere (2,4) e un altro da (3,1).

Potresti scrivere una ricerca completa standard per risolvere il problema in modo primitivo ma affidabile. Assegna semplicemente un dipendente (in modo arbitrario) a trip 1, quindi assegna il dipendente successivo a 1 o 2, ecc., Back-tracking ogni volta che non puoi collocare il prossimo dipendente in uno dei due viaggi e termina se tutti i dipendenti sono assegnati.

La domanda più interessante è se la ricerca può essere resa più efficiente. In questo caso, dato che i colleghi passati non possono viaggiare insieme, puoi immediatamente assegnare a tutti i tuoi collaboratori tutti tutti quelli che piazzi in viaggio 1 a 2 - e poi puoi assegnare tutti i loro colleghi di lavoro per inciampare 1, per lo stesso motivo, e così via fino a quando il vincolo 2 non ti dà alcuna nuova informazione. Se si verifica una violazione del vincolo durante questo processo, il problema è irrisolvibile. Questo non troverà una soluzione più veloce della soluzione ingenua, ma può provare l' assenza di una soluzione molto più velocemente, poiché non è necessario tornare indietro attraverso l'intero spazio della soluzione. Un'ottimizzazione aggiuntiva potrebbe essere quella di collocare prima i dipendenti con il maggior numero di collaboratori, poiché ciò esclude più parti dello spazio della soluzione rispetto al collocamento di un lavoratore solitario.

Questo problema può essere ridotto a un problema grafico bipartito .

Grafici bipartito

Se i vertici di un grafico possono essere divisi in due gruppi, ad esempio

• non esiste uno spigolo tra due vertici nello stesso gruppo
• (per ogni nodo, c'è un bordo che lo collega a un vertice dell'altro gruppo)

Riassunto

Notiamo che

• le persone verranno suddivise in due gruppi
• solo le persone in diversi gruppi condividono una sorta di relazione l'una con l'altra

Sapendo che un grafico (non orientato) è semplicemente una visualizzazione di una relazione (simmetrica) e una partizione dei suoi oggetti (cioè persone) in due gruppi, e tutti gli spigoli connettono i vertici di gruppi diversi, possiamo vedere che questo in infatti si qualifica come un grafico bipartito, se tale partizionamento è effettivamente possibile.

Concludiamo che dobbiamo solo determinare, se si tratta di un grafico bipartito (rilassato). Rilassato, perché nella definizione corretta, ogni vertice deve avere almeno un bordo, ma il problema non specifica se questo è il caso. Questo è il motivo per cui (2) è tra parentesi.

Rilevamento di un grafico bipartito

Questo può essere fatto con una BTH (breadth-first-search) di un algoritmo DFS (depth-first-search).

• Possiamo posizionare il primo vertice nel gruppo # 1. (Non importa quale)
• Fatto ciò, è chiaro che tutti i suoi vicini devono essere inseriti nel gruppo n. 2, poiché i vicini sono quelli che hanno lavorato con la prima persona. Pertanto, potrebbero non essere nel gruppo # 1.
• Allo stesso modo, mettiamo tutti i vicini dei vicini nel gruppo # 1
• Continuando allo stesso modo, assegniamo i nodi ai due diversi gruppi.

Tuttavia, nel caso in cui non sia possibile formare un grafico bipartito, dobbiamo dover inciampare su un nodo quando proviamo ad assegnarlo al gruppo X, che era già assegnato ad un gruppo, ma non gruppo X. In tal caso, è impossibile formare due gruppi di dipendenti in cui nessuno ha mai lavorato prima.

Modifica DFS / BFS

Dopo aver scoperto un nodo adiacente, lo posizioniamo nel gruppo opposto del nodo attivo al momento, se non ne è stato ancora assegnato uno.

Se è già stato assegnato allo stesso nodo, sappiamo che è impossibile formare un grafico bipartito.

Altrimenti, è già stato inserito in una regola conforme al gruppo (1) di un grafico bipartito.

Gestione della regola (2)

Nel caso in cui la regola (2) non sia effettiva, ovvero il grafico ha più di componenti collegati , DFS / BFS terminerà prima di aver assegnato tutti i nodi a un gruppo.

In tal caso, l'algoritmo viene semplicemente eseguito nuovamente su un nodo non ancora assegnato, fino a quando non viene lasciato alcun nodo.

Ottenere tutte le soluzioni

Nel caso in cui la regola (2) non sia in vigore, esistono più di due sole soluzioni. Per un grafico con componenti c collegati, (cioè l'algoritmo DFS / BFS è stato eseguito c volte), ci sono 2 ^c soluzioni.

Per questo, dobbiamo distinguere tra i due gruppi creati da ogni invocazione dell'algoritmo BFS / DFS: g _{c , 1} e g _{c , 2} per eseguire c .

Dopo aver eseguito l'algoritmo c volte, distribuiamo le coppie c a due gruppi, in cui i dipendenti vengono separati, liberamente.