Come posso trovare un modo per ridurre al minimo il numero di spigoli?

Question

Sto pensando un algoritmo per risolvere il problema di seguito:

Un dato grafo composta da vertici e spigoli.

Ci sono clienti N che desiderano viaggiare da un vertice a un altro vertice. E ogni requisito del cliente necessita di uno spigolo diretto per collegare due vertici.

Il problema è come trovare il numero minimo di spigoli per soddisfare tutte le esigenze dei clienti?

C'è un semplice esempio:

• clienti 1 vuole viaggiare da vertice A al vertice B.
• Il cliente 2 vuole spostarsi dal vertice b al vertice c.
• Il cliente 3 vuole spostarsi dal vertice al vertice c.

Il modo più semplice è quello di dare un vantaggio per l'ogni clienti:

• bordo 1: vertice a -> vertice b
• bordo 2: vertice b -> vertice c
• bordo 3 : vertice a -> vertice c

Ma in realtà servono solo 2 spigoli (ad es. spigolo 1 e spigolo 2) per soddisfare le tre esigenze del cliente.

Se il numero clienti è grande, come trovare i bordi minimi per soddisfare tutte le esigenze del cliente?

Esiste un algoritmo per risolvere questo problema?

Answer 1

È possibile modellare il problema come un programma intero misto. È possibile definire variabili binarie per "arco a-> b è utilizzato" e "cliente c usa arco a -> b" e annotare i requisiti come disuguaglianze lineari. Se il tuo grafico non è troppo grande, puoi risolvere tali modelli in tempi ragionevoli con un programma di risoluzione di un programma intero misto (CPLEX, GUROBI, ma esistono anche alternative gratuite sul web).

So che questa soluzione richiede un po 'di lavoro se non si ha familiarità con la programmazione lineare, ma garantisce di trovare le migliori soluzioni in tempi finiti e probabilmente si può risolvere per (dire) 1000 clienti e 1000 archi.

Answer 2

Se si dispone di N vertici, è sempre possibile costruire una soluzione con bordi N (diretti). Basta creare un ciclo diretto V_1 -> V_2 -> V_3 -> ... -> V_N -> V_1. Non puoi mai avere il percorso diretto da ogni vertice V_a a ogni altro V_b con meno spigoli (perché avresti un albero diretto che necessariamente contiene una foglia). La foglia è non raggiungibile (se il bordo va dalla foglia) o la foglia è un lavandino (non può connettersi a qualcos'altro) se il bordo è -> foglia.

Answer 3

Non è necessario utilizzare alcun nuovo algoritmo. È possibile utilizzare l'algoritmo BFS/DFS.

Find if there exists any path between source and destination. 
    if !true 
     add a direct edge between source and destination 
     count++; 
return count; 

Qui la parte chiave è invece del ciclo attraverso il grafico che dobbiamo scorrere attraverso i bordi appena aggiunti.

Answer 4

È possibile utilizzare la struttura dati impostata di Disjoint.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

while (num_edges--) 
    if root(vertex_a) != root(vertex_b) 
    count++ 
    union(vertex_a,vertex_B)