Costo minimo fortemente connesso digraph

Question

Ho un grafo orientato fortemente collegato (cioè non v'è un percorso da i a j e j per i per ogni coppia di nodi (i, j) nel grafico G). Vorrei trovare un grafico fortemente connesso da questo grafico in modo tale che la somma di tutti i bordi è il meno.

Per dirla diversamente, ho bisogno di sbarazzarsi di bordi in modo tale che dopo aver rimosso loro, il grafico verrà comunque fortemente collegato e di minor costo per la somma dei bordi.

Credo che sia un problema di difficile NP. Sto cercando una soluzione ottimale, non approssimazione, per un piccolo insieme di dati come 20 nodi.

Modifica

Una descrizione più generale: Dato un grap G (V, E) trovare un grafo G '(V, E') tale che se esiste un percorso da v1 a v2 in G che esiste un percorso tra v1 e v2 in G 'e somma di ciascuna ei in e' è il minimo possibile. per cui il suo simile alla ricerca di un grafico minimo pari, solo qui vogliamo minimizzare la somma dei pesi bordo piuttosto che somma dei bordi.

Modifica:

Il mio approccio finora: Ho pensato di risolverlo con TSP con più visite, ma non è corretto. Il mio obiettivo è quello di coprire ogni città, ma utilizzando un percorso di costo minimo. Quindi, è più come il coperchio set problema, credo, ma io non sono esattamente sicuro. Sto necessaria per coprire ogni città utilizzando percorsi cui costo complessivo è minimo, in modo da visitare i percorsi già visitato più volte non aggiungere al costo.

Answer 1

Il problema è noto come di copertura minimo forte sub (di) grafico (MSSS) o, più in generale, dei costi di copertura minimo sub (di) grafico e è NP-hard davvero . Vedi anche un altro libro: pagina 501 e pagina 480

Mi piacerebbe iniziare con la rimozione di tutti i bordi che non soddisfano la disuguaglianza triangolare - è possibile rimuovere bordo di un -> c se andare a -> b -> c è più conveniente. Questo mi ricorda TSP, ma non so se questo porta da nessuna parte.

La mia risposta precedente era di utilizzare la Chu-Liu / Edmonds algoritmo che risolve Arborescence problema; come Kazoom e ShreevatsaR sottolineato, questo non aiuta.

Answer 2

Vorrei provare questo in una sorta di programmazione dinamica del percorso.

0- messo il grafico in un elenco

1- Fate una lista di nuovi sottografi di ogni grafico nella lista precedente, in cui si rimuove un lato diverso per ciascuno dei nuovi sottografi

2- rimuovere i duplicati dal nuovo elenco

3- rimuovere tutti i grafici dalla nuova lista che non sono fortemente collegati

4- confrontare il miglior grafico dalla nuova lista con l'attuale migliore, se migliore, impostare nuova corrente migliore

5- se il nuovo elenco è vuoto, la corrente migliore è la soluzione, tuttavia, recurse / loop / goto 1

In Lisp, si potrebbe forse apparire così:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

Le definizioni di strongly-connected, list-subgraphs-1, digraph-equal, best e better sono lasciati come esercizio per il lettore.

Answer 3

Il problema è equivalente al problema descritto qui: http: // www .facebook.com / carriere / puzzles.php? puzzle_id = 1

Answer 4

alcune idee che mi hanno aiutato a risolvere il famoso puzzle facebull:

fase pre-elaborazione:

1. potatura: rimuovere tutti i bordi a-b se ci sono meno costosi o avente lo stesso costo percorso, ad esempio:. A-c-b

2. Grafico di decomposizione: è possibile risolvere sottoproblemi se il grafico ha punti di articolazione

3. Unisci vertici in un vertice virtuale se ci sono solo un bordo di uscita.

passo di calcolo:

1. Come soluzione approssimata utilizzando il TSP diretto con visite ripetute. Utilizzare Floyd Warshall e quindi risolvere Assegnazione problema O (N ^ 3) usando il metodo ungherese. Se abbiamo ottenuto una volta il ciclo - è diretta soluzione TSP, se non - uso ramo e TSP bound. Dopo di che abbiamo superiore valore associato -. Il ciclo dei costi minimi

2. soluzione esatta - ramo e approccio legato. Togliamo i vertici del ciclo più breve e proviamo costruire grafico fortemente connessa con meno costi, di limite superiore.

Questo è tutto gente. Se si desidera testare le vostre soluzioni - provarlo qui: http://codercharts.com/puzzle/caribbean-salesman

Answer 5

Suona come si desidera utilizzare il Dijkstra algoritmo

Answer 6

Sembra che ciò che si vuole in sostanza è una soluzione ottimale per i viaggi-venditore in cui è consentito per i nodi da visitare più di una volta.

Modifica:

Hmm. Potresti risolvere questo in sostanza l'iterazione di ciascun nodo i e poi fare un albero di copertura minimo di tutti i bordi di puntamento a che nodo i, unioned con un altro albero di copertura minimo di tutti i bordi di puntamento via da quel nodo?

Answer 7

A 2-approssimazione al minima fortemente collegato sottografo viene ottenuto tenendo unione di un minimo di ramificazione e minimal fuori ramificazione, sia radicata Allo stesso (ma arbitraria) vertice.

Un out-ramificazione , noto anche come arborescence , è un albero diretto con radice in un singolo vertice che attraversa tutti i vertici. An in-ramificazione è lo stesso con bordi inversa. Questi possono essere trovati da Edmonds' algoritmo in tempo O (VE) , e ci sono incrementi nella velocità a O (log e (V)) (si veda il wiki pagina ). C'è anche un aperta implementazione fonte .

Il riferimento iniziale per il risultato 2-approssimazione è la carta da JaJa e Frederickson , ma la carta non è liberamente accessibile.

C'è anche un'approssimazione 3/2 da Adrian Vetta (PDF) , ma più complicato di quanto sopra.