sottografo connesso minimo contenente un dato insieme di nodi
-
09-10-2019 - |
Domanda
ho un pesato, grafo connesso. Voglio trovare un sottografo connesso che include sicuramente un certo insieme di nodi, e come alcuni extra possibili. Come può essere realizzato?
Nel caso in cui, io ribadire la questione usando un linguaggio più preciso. Sia G (V, E) sia una non ponderata, non orientato, grafo connesso. Sia N un sottoinsieme di V. Qual è il modo migliore per trovare il più piccolo sottografo connesso G '(V', E ') di G (V, E) in modo tale che N è un sottoinsieme di V'?
approssimazioni sono bene.
Soluzione
Non riesco a pensare a un algoritmo efficiente per trovare la soluzione ottimale, ma supponendo che il grafico di ingresso è denso, di seguito potrebbe funzionare abbastanza bene:
-
Convertire la vostra
G(V, E)
grafo di input a unG'(N, D)
grafo pesato, doveN
è il sottoinsieme di vertici che si vogliono coprire eD
viene distanze (lunghezze del percorso) tra i vertici corrispondente nel grafico originale. In questo modo "collasso" tutti i vertici non è necessario in bordi. -
Calcola il minimo spanning tree per
G'
. -
"espandere" il minimo albero di copertura secondo la seguente procedura: per ogni
d
bordo nella struttura di copertura minimo, prendere il percorso corrispondente graficoG
e aggiungere tutti i vertici (inclusi i punti finali) sul percorso al risultato setV'
e tutti i bordi del percorso delE'
set di risultati.
Questo algoritmo è facile da scattare fino a dare soluzioni non ottimali. caso di esempio: triangolo equilatero dove ci sono vertici agli angoli, in punti medi dei lati e nel mezzo del triangolo, e bordi lungo i lati e dagli angoli al centro del triangolo. Per coprire gli angoli è sufficiente scegliere il punto di mezzo singolo del triangolo, ma questo algoritmo potrebbe scegliere i lati. Tuttavia, se il grafico è denso, dovrebbe funzionare OK.
Altri suggerimenti
Questo è esattamente il noto Steiner Albero problema. Senza ulteriori dettagli su ciò che i vostri casi assomigliano, è difficile dare consigli su un algoritmo appropriato.
Le soluzioni più semplici sarà il seguente:
a) sulla base di MST:
- Inizialmente, tutti i nodi di V sono in V'
- costruire un minimo spanning tree del grafo G (V, E) - chiamare T.
- ciclo:. Per ogni foglia v in T che non è in N, v Eliminare dal V'
- ciclo di ripetizione fino a quando tutte le foglie in T sono in N.
b) un'altra soluzione è il seguente - in base a più breve albero percorsi
.
- scegliere qualsiasi nodo N, chiamano V, Sia V una radice di un albero T = {v}.
- Rimuovere v da N.
- ciclo: 1) selezionare il percorso più breve da qualsiasi nodo T e qualsiasi nodo N. minor percorso p: {v, ..., u} dove v è in T e U è in N. 2) ogni nodo p viene aggiunto V'. 3) ogni nodo p in N viene eliminato da N. --- ripetizione ciclo finché N è vuoto.
All'inizio dell'algoritmo: calcolare tutti i percorsi più brevi in ??G utilizzando qualsiasi algoritmo efficiente noto.
Personalmente, ho usato questo algoritmo in una delle mie carte, ma è più adatto per ambienti distribuiti. Sia N l'insieme dei nodi che abbiamo bisogno di interconnessione. Vogliamo costruire una minima di collegamento che domina set del grafo G, e vogliamo dare la priorità per i nodi in N. Diamo ogni nodo u un identificatore univoco id (u). Lasciamo w (u) = 0 se u è in N, altrimenti w (1). Creiamo coppia (w (u), id (u)) per ogni nodo u.
-
ogni nodo u costruisce un nodo di trasmissione multinsieme. Cioè, un insieme M (u) di neigbhors 1-hop tale che ciascun vicino 2-hop è un vicino ad almeno un nodo M (u). [Minimo M (u), migliore è la soluzione].
-
U è in V' se e solo se: u ha la coppia più piccolo (w (u), ID (u)) fra tutti i suoi vicini. oppure u è selezionato nel M (v), dove v è un vicino di casa 1-hop di u con il più piccolo (w (u), ID (u)).
- il trucco quando si esegue questo algoritmo in modo centralizzato è quello di essere efficace nel calcolo vicini 2-hop. La migliore ho potuto ottenere da O (n ^ 3) è O (n ^ 2,37) per la moltiplicazione di matrici.
-. Ho davvero voglia di sapere che cosa è la razione approssimazione di quest'ultima soluzione
Mi piace questo riferimento per l'euristica di albero di Steiner: Il problema dell'albero di Steiner, Hwang Frank; Richards Dana 1955- inverno Pawel 1952
Si potrebbe provare a fare quanto segue:
-
Creazione di un minimo vertici copertura per i nodi
N
desiderato. -
Chiudi questi, eventualmente non connessi, sub-grafici in "grandi" nodi. Cioè, per ogni sub-grafico, rimuoverlo dal grafico, e sostituirlo con un nuovo nodo. Chiamare questo insieme di nodi
N'
. -
Do un minimo vertici copertura dei nodi in
N'
. -
"Estrarre" i nodi
N'
.
Non è sicuro se sia o non ti dà un'approssimazione all'interno di alcuni specifici vincolati o giù di lì. Si potrebbe forse anche ingannare l'algoritmo di prendere alcune decisioni davvero stupide.