Algoritmo per reperire percorsi distinti da A a B in ponderati, diretto, grafico ciclico

Question

Supponiamo di avere un CICLICO grafico DIRETTO, PONDERATA e .

Supponiamo di essere interessati solo nei percorsi con un peso totale inferiore MAX_WEIGHT

Qual è la più appropriata (o qualsiasi) algoritmo per trovare il numero di percorsi distinti tra due nodi A e B che hanno un peso totale inferiore a MAX_WEIGHT?

P.S: Non sono i miei compiti. Solo un progetto personale e non commerciale.

Answer 1

Se il numero di nodi e MAX_WEIGHT non sono troppo grandi (e tutti i pesi sono numeri interi), è possibile utilizzare la programmazione dinamica

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes]; 

inizializzare a 0, tranne num_of_paths[0][start] = 1;.

for(w = 0; w < MAX_WEIGHT; ++w){ 
    for(n = 0; n < num_nodes; ++n){ 
     if (num_of_paths[w][n] > 0){ 
      /* for each child c of node n 
      * if w + weight(n->c) <= MAX_WEIGHT 
      * num_of_paths[w+weight(n->c)][c] += num_of_paths[w][n]; 
      */ 
     } 
    } 
} 

soluzione è la somma di num_of_paths[w][target], 0 <= w <= MAX_WEIGHT.

Answer 2

Semplice ricorsione. Ce l'hai in tempo esponenziale. Ovviamente, non sono consentiti cicli a peso zero.

funzione NOE (nodo N, limite di peso W)

1. n. di percorso è zero se tutti i fronti uscenti hanno peso> W

2. altrimenti no. di percorso è somma di numeri di percorso ottenuti per somma (noe (C1, W-W1), noe (C2, W-W2), ... noe (Cn, W-Wn)) dove C1 ... Cn sono i nodi connessi a N per cui W-Wi non è negativo, dove Wi è il peso del bordo di connessione, scritto nella tua lingua preferita.

Più soluzione eficient dovrebbe esistere, lungo le linee di algoritmo di Dijkstra, ma penso che questo è sufficiente per i compiti a casa.

Answer 3

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 .