Algoritmo / approssimazione combinata set / distanza di Hamming indipendente

Question

Input: grafo G Resa: diversi insiemi indipendenti, in modo che l'appartenenza di un nodo a tutti i set indipendenti è unico. Un nodo ha quindi connesso ad alcun nodo nel suo insieme. Qui è un percorso di esempio.

Dal chiarimento è stato chiesto qui un'altra rephrasal:

Divisione di un dato grafo in serie in modo che

1. Posso dire un nodo da tutti gli altri per la sua appartenenza a gruppi per esempio se il nodo i è presente solo nel set Un altro nodo dovrebbe essere presente in un insieme unico

   se il nodo j è presente in serie A e B quindi nessun altro nodo dovrebbe essere presente in un set e B soltanto. se l'appartenenza dei nodi è codificata da uno schema di bit, allora queste sequenze di bit hanno distanza di Hamming almeno un

2. se due nodi sono adiacenti nel grafico, non dovrebbero essere presenti nello stesso insieme, quindi essere un insieme indipendente

Esempio: B ha nodi adiacenti D => A, A => D

Soluzione:

1. A B /
2. / B D

A ha bit reticolo 10 e al nodo adiacente nel suo insieme. B ha il bit del modello 11 e nessun nodo adiacente, D ha 01 Pertanto tutti i nodi hanno distanza di Hamming almeno 1 an no adiacente nodi => corretto

sbagliato, perché D e A sono collegate:

1. A D B
2. / D B

A ha bit reticolo 10 e D nel suo insieme, che sono adiacenti. B ha il bit del modello 11 e nessun nodo adiacente, D ha 11 come è B, quindi ci sono due errori in questa soluzione e quindi non viene accettata.

Naturalmente questo dovrebbe essere esteso a più Imposta come il numero di nodi negli aumenti grafico, in quanto è necessario almeno set log(n).

Ho già scritto una trasformazione in MAX-SAT, per usare un sat-solver per questo. ma il numero di clausole è solo quello grande. Un approccio più diretto sarebbe bello. Finora ho un'approssimazione, ma vorrei una soluzione esatta o almeno una migliore approssimazione.

Ho provato un approccio in cui ho usato uno sciame di particelle per ottimizzare da una soluzione arbitraria verso uno migliore. Tuttavia, il tempo di esecuzione è abbastanza terribile ed i risultati sono tutt'altro che grandi. Sto cercando un algoritmo dinamico o qualcosa del genere, ma non posso capire come dividere e conquistare questo problema.

Answer 1

Non è una risposta completa, e non so quanto sia utile sarà per voi. Ma ecco qui:

La distanza di Hamming mi sembra una falsa pista. La sua dichiarazione problema dice che deve essere di almeno 1 ma potrebbe essere 1000. Basta dire la codifica bit per le appartenenze set di ogni nodo è unico.

La sua dichiarazione problema non incantesimo fuori, ma la soluzione suggerisce di sopra di ogni nodo deve essere un membro di almeno 1 set. vale a dire. un bitrate di tutti 0 di non è consentito per appartenenze impostare qualsiasi nodo.

Ignorando nodi collegati per un istante, nodi disgiunti sono facili: basta numero sequenzialmente con una codifica bit non utilizzato. Salva quelli per ultimo.

Il tuo esempio precedente utilizza bordi diretto, ma ancora una volta, che mi colpisce come un diversivo. Se A non può essere nello stesso insieme D perché A => D, D non può essere nello stesso insieme di A prescindere dal fatto che D => A.

Lei parla di bisogno almeno di registro (N) set. Avrete anche alla maggior parte dei gruppi N. Un grafico completamente collegato (con (N ^ 2-N) / 2 bordi non orientati) richiederà N imposta ciascuno contenente un singolo nodo.

Infatti, se il grafico contiene un simplex completamente connessa di dimensioni M (M in 1..N-1) con M + 1 vertici e (M ^ 2 + M) / 2 bordi non orientati, si richiederà almeno M + 1 set.

Nel tuo esempio sopra, si dispone di uno di questi simplex (M = 1) con 2 vertici {A, D} e 1 bordo (non diretta) {(A, D)}.

Sembrerebbe che il problema si riduce a trovare il più grande simplessi pienamente collegati nel grafico. Detto in altro modo, hai un problema di routing: Quanti dimensioni avete bisogno di instradare i bordi in modo che nessuna croce? Non suona come un problema molto scalabile.

Il primo grande riscontrata simplex è facile. Ogni nodo vertice ottiene un nuovo insieme con il proprio bit.

I nodi disgiunti sono facili. Una volta che i nodi collegati sono trattati, semplicemente numero dei nodi disgiunti sequenzialmente saltare nessun bit modelli precedentemente usate. Dal vostro esempio di cui sopra, dal momento che A e D prendono 01 e 10, il successivo schema di bit disponibili per B è 11.

La parte difficile diventa allora come piegare i restanti simplex il più possibile nella gamma esistente prima di creare nuovi insiemi con nuovi bit. Quando pieghevole, si deve utilizzare 2 o più bit (fissa) per ciascun nodo, ei bit (fissa) non deve intersecano con i bit (set) per qualsiasi nodo adiacente.

Si consideri ciò che accade al tuo esempio di cui sopra, quando si aggiunge un altro nodo, C, l'esempio:

Se C collega direttamente ad entrambi A e D, quindi il problema iniziale diventa trovando il 2-simplex con 3 vertici {A, C, D} e 3 bordi {(A, C), (A, D), ( CD)}. Una volta A, C e D assumono i modelli di bit 001, 010 e 100, la sequenza di bit disponibili disponibilità per disgiunto B è 011.

Se, invece, C collega direttamente A o D, ma non entrambi, il grafico ha due 1-simplex. Supponendo troviamo la 1-simplex con vertici {A, D} prima dando loro le sequenze di bit 01 e 10, il problema diventa allora come piegare C in tale intervallo. Il modello unico bit con almeno 2 bit è 11, ma che interseca con qualsiasi nodo C si collega alla così dobbiamo creare un nuovo set e messo C in esso. A questo punto, la soluzione è simile a quello sopra.

Se C è disgiunto, sia B o C sarà possibile ottenere il modello di bit 11 e il restante uno avrà bisogno di un nuovo set e ottenere la sequenza di bit 100.

Supponiamo che connette C a B, ma non ad una o D. Anche in questo caso, il grafico ha due 1-simplex ma questa volta disgiunti. Supponiamo {A, D} è situato prima come sopra dando A e D le sequenze di bit 10 e 01. Si possono piegare B o C nella gamma esistente. La sequenza di bit disponibili solo nella gamma è 11 e sia B o C potrebbe ottenere il motivo come non è adiacente ad una o D. Dopo 11 viene utilizzato, non modelli di bit con 2 o più bit impostati non, e dovremo creare un nuovo set per il nodo rimanente dandogli la sequenza di bit 100.

Supponiamo C collega a tutti i 3 A, B e D. In questo caso, il grafico ha un 2-simplex con 3 vertexes {A, C, D} e 1 simplex con 2 vertici {B, C}. Procedendo come sopra, dopo l'elaborazione del grande simplex, A, C e D hanno modelli di bit 001, 010, 100. Ad piegatura B in questa gamma, i modelli di bit disponibili con 2 o più bit impostati sono: 011, 101, 110 e 111. Tutti questi, tranne 101 intersecano con C in modo B otterrebbe lo schema di bit 101.

La questione diventa allora:? Come efficacemente si possono trovare i più grandi simplessi completamente collegati

Se trovare il più grande simplex completamente connessa è troppo costoso , si potrebbe mettere un approssimativo limite superiore potenziale simplessi completamente collegati trovando minimi massimi in termini di connessioni:

1. Sweep attraverso i bordi aggiornamento del vertici con un conteggio del collegare bordi.

2. Per ogni nodo collegato, creare una matrice di Cn risiedono inizialmente nullo dove Cn è il conteggio dei bordi collegato al nodo n.

3. Sweep attraverso i bordi di nuovo, per i nodi collegati n1 e n2, incrementare il conteggio in n1 corrispondenti a CN2 e viceversa. Se Cn2> Cn1, aggiornare l'ultimo conteggio nell'array n1 e viceversa.

4. Sweep attraverso i nodi collegati nuovamente, calcolando un limite superiore la più grande simplex ciascun nodo potrebbe essere una parte di. Si potrebbe costruire una matrice di incasellare con una lista di vertici per ogni limite superiore come si fa scopare attraverso i nodi.

5. Il lavoro attraverso l'array incasellare dal più grande al più piccolo estrazione e nodi pieghevole in set unico.

Se i nodi sono in un set di N e le vostre bordi in un insieme E, la complessità sarà: O (| N | + | E | + O (punto 5))

Se i suffissi di approssimazione di cui sopra, la domanda diventa:? Come efficacemente si può piegare i nodi in gamme esistenti riportati i requisiti

Answer 2

Questa forse non è la risposta che si potrebbe aspettare, ma non riesco a trovare un posto per aggiungere un commento. Così ho tipo direttamente qui. Non riesco a comprendere appieno la tua domanda. O che ha bisogno di conoscenze specifiche da capire? Che cosa è questo insieme indipendente? Come so un nodo in un insieme indipendente da un grafo orientato avere un percorso bidirezionale a qualsiasi altro nodo in questa serie. È il tuo concetto stesso?

Se il problema è come quello che presumo, insiemi indipendenti possono essere trovati da questo algoritmo: 1. fanno ricerca in profondità sul grafo orientato, registra il tempo di albero radicato da questo nodo è attraversato. 2. poi invertire tutti gli spigoli di questo grafico 3. fare di nuovo la ricerca in profondità Frist sul grafico modificato. L'algorihtm è appunto spiegato da prenotare "introduzione alla alogrithm"