tuo problema è caso più generale di K-Disjoint Path In directed planar graphs, con non fissato K. problema
K
percorsi disgiunti per grafi planari indirizzate è come questo:
proposta: un grafo planare orientato G = (V ; E) e k coppie (r ; s); ....; (r k; s k) di vertici di G;
trovare: k due a due vertici disgiunti percorsi diretti P ; ...; P k in G, dove P i va da r i di s i (i = 1; ....; k).
in K-disgiunto percorso è possibile disegnare arco da tutti s i a B, e inoltre: Arco da A a tutti i r in questo modo si crea grafo G' dal G.
Ora, se puoi risolvere il tuo problema in G 'in P puoi risolvere k percorso disgiunto in G, quindi P = NP.
Ma se si legge la carta collegata, si ha un'idea del grafico generale (risolvendo il percorso k-disgiunto con k fisso) e si può usare per avere una buona approssimazione.
Inoltre, esiste un algoritmo più complicato che risolve questo problema in P (per fixed k) nei grafici generali. ma in tutto non è facile (è di Seymour).
Quindi la scelta migliore attualmente è quella di utilizzare algoritmi di forza bruta.
Edit: Perché MaxWeight è indipendente alle dimensioni di ingresso (la dimensione del grafico) non influisce a questo problema, anche perché è NP-Hard per grafo non pesato non orientato, ancora si può semplicemente concludere che sia NP-Hard .
fonte
2012-01-17 11:54:48
Consentite ai percorsi che visitano lo stesso vertice più di una volta (a condizione che la lunghezza del percorso sia inferiore a MAX_WEIGHT)? – NPE
Possiamo supporre che non ci siano cicli a peso zero? – bdares
@aix: Sì, scusa ho dimenticato di dirlo. Puoi andare in loop quanto vuoi finché sono soddisfatti i criteri MAX_WEIGHT. – Babak