1. Definizione del problema:
* Network: Stai lavorando con un grafico diretto (rete) rappresentato da:
* nodi (vertici): `V` (ad esempio fabbriche, magazzini, città)
* Arcs (Edges): `E` (ad es. Strade, condutture, collegamenti di comunicazione)
* Capacità: Ogni arco `(u, v)` in `e` ha una capacità` c (u, v) `che rappresenta il flusso massimo che può passare attraverso di esso.
* Costi: Ogni arco `(u, v)` in `e` ha un costo` costo (u, v) `che rappresenta il costo per unità di flusso attraverso quell'arco.
* Supplimi/domanda: Ogni nodo `V` in` V` ha una fornitura `b (v)`.
* Se `b (v)> 0`, il nodo` V` è una * sorgente * con una fornitura di unità `b (v)`.
* Se `b (v) <0`, il nodo` V` è un * lavello * con una richiesta di unità `-b (v)`.
* Se `b (v) =0`, il nodo` V` è un nodo di trasbordo.
* Obiettivo: Trova l'assegnazione del flusso che riduce al minimo il costo totale dell'invio del flusso attraverso la rete, soddisfacendo al contempo i vincoli di offerta/offerta e vincoli di capacità.
2. Inizializzazione:
* Rete residua: Crea una rete residua `g_f` basata sulla rete originale` g`. Inizialmente, `g_f =g`. Questa rete tiene traccia della capacità disponibile. Per ogni arco `(u, v)` In `g`, la capacità residua è` c_f (u, v) =c (u, v) - f (u, v) `, dove` f (u, v) `è il flusso di corrente su quell'arco. Inizialmente, `f (u, v) =0` per tutti gli archi.
* Flusso: Inizializza il flusso `f (u, v) =0` per tutti gli archi nella rete originale.
* Potenziali (prezzi): Inizializza una potenziale funzione `pi (v)` per ciascun nodo `V` in` V`. Un punto di partenza comune è `pi (v) =0` per tutti` V`. I potenziali sono cruciali per la gestione di cicli di costo negativi.
3. Passi di algoritmo:
Il nucleo dell'algoritmo di percorso più breve successivo è un processo iterativo:
UN. Trova una fonte e un lavandino: Seleziona un nodo di origine `s` (dove` b (s)> 0`) e un nodo di lavandino `t` (dove` b (t) <0`) nella rete. Se non esistono tali nodi, l'algoritmo è completo.
B. Calcolo del percorso più breve: Trova il percorso più breve `p` da` s` a `t` nella *rete residua *` g_f` usando i *costi ridotti *. Il costo ridotto per un arco `(u, v)` è definito come:
`` `
cost_redoced (u, v) =cost (u, v) + pi (u) - pi (v)
`` `
* L'obiettivo di utilizzare i costi ridotti è eliminare i cicli di costo negativi. Se i potenziali `pi` sono scelti in modo tale che` cost_redoced (u, v)> =0` per tutti gli archi, allora l'algoritmo di Dijkstra può essere usato per trovare il percorso più breve.
* Se rimangono costi negativi dopo aver applicato potenziali, è possibile utilizzare l'algoritmo di Bellman-Ford (ma è generalmente più lento).
C. Flusso di aumento: Sia Delta` il minimo di:
* `b (s)` (l'offerta rimanente alla sorgente `s`)
* `-b (t)` (la restante domanda a Sink `T`)
* La capacità residua minima lungo il percorso più breve `p`:` min {c_f (u, v) | (u, v) in p} `
Aggiorna il flusso lungo il percorso `p` di` Delta`:
* Per ogni arco `(u, v)` in `p`:
* `f (u, v) =f (u, v) + delta`
* Aggiorna capacità residua:`c_f (u, v) =c (u, v) - f (u, v)`
* Se `(u, v)` esiste nella rete originale, aggiorna il suo bordo inverso nella rete residua:crea il bordo `(v, u)` in `g_f` se non esiste con` c_f (v, u) =f (u, v) `.
D. Aggiorna domanda e domanda:
* `b (s) =b (s) - delta`
* `b (t) =b (t) + delta`
e. Aggiorna potenziali (variante Bellman-Ford): Questo è un passaggio * cruciale * per mantenere i costi ridotti non negativi e garantire un comportamento corretto. Dopo aver aumentato il flusso, è necessario aggiornare i potenziali. Un approccio comune (spesso usato insieme a Dijkstra dopo un Bellman-Ford iniziale) è una variante di Bellman-Ford. Questo può essere fatto usando le distanze del percorso più brevi dall'iterazione precedente, ma applicato su tutti i vertici. La chiave è assicurarsi che vengano gestiti tutti i cicli di costo negativi introdotti dall'aumento del flusso.
* Opzione 1:Full Bellman-Ford (meno efficiente): Rieponire Bellman-Ford da un nodo arbitrario `R` a tutti gli altri nodi in` G_f` usando i costi ridotti. Sia `d (v)` essere la distanza più breve da `r` a` V`. Aggiorna i potenziali:`pi (v) =pi (v) - d (v)`. Ciò garantisce `cost_redoced (u, v)> =0` per tutti gli archi dopo l'aggiornamento, ma è relativamente lento.
* Opzione 2:l'algoritmo di Johnson (efficiente): Esegui una volta Bellman-Ford per calcolare i potenziali iniziali. Successivamente, utilizzare l'algoritmo di Dijkstra utilizzando i costi ridotti. Dopo ogni aumento, ricomput i potenziali usando il risultato di Dijkstra.
F. Ripeti: Torna al passaggio (a) e ripeti il processo fino a quando tutte le forniture e le richieste non sono soddisfatte (`b (v) =0` per tutti i nodi` V`).
4. Terminazione:
L'algoritmo termina quando tutte le forniture e le richieste sono soddisfatte. Il flusso risultante `f (u, v)` per tutti gli archi `(u, v)` nella rete originale rappresenta il flusso di costo minimo.
Strutture di dati chiave:
* Elenco di adiacenza/Matrix: Per rappresentare la rete `g` e la rete residua` g_f`. Gli elenchi di adiacenza sono in genere più efficienti per i grafici sparsi.
* Matrice di flusso: Per memorizzare il flusso di corrente `f (u, v)` su ciascun arco.
* Matrix di capacità: Per archiviare le capacità originali `c (u, v)` di ogni arco.
* Matrix di capacità residua: Per archiviare le capacità residue `c_f (u, v)` nella rete residua.
* Array potenziale: Per conservare i potenziali `pi (v)` per ogni nodo.
* coda prioritaria (heap): Utilizzato nell'algoritmo di Dijkstra per un efficiente calcolo del percorso più breve.
Considerazioni sul codice (esempio di Python - semplificato):
`` `Python
importare heapq
Def Successtive_Shortest_Path (grafico, capacità, costo, fornitura):
"" "
Implementa l'algoritmo del percorso più breve successivo.
Args:
Grafico:un dizionario che rappresenta il grafico come elenco di adiacenza.
Le chiavi sono nodi, i valori sono elenchi di nodi vicini.
Capacità:un dizionario che rappresenta la capacità di ciascun bordo (u, v).
Costo:un dizionario che rappresenta il costo di ogni bordo (u, v).
Offerta:un dizionario che rappresenta l'offerta/domanda di ciascun nodo.
I valori positivi sono l'offerta, i valori negativi sono richiesti.
Ritorni:
Un dizionario che rappresenta il flusso su ciascun bordo o nessuno se nessuna soluzione fattibile.
"" "
flusso ={} # Inizializza flusso su zero
per te in grafico:
per v in grafico [u]:
flusso [(u, v)] =0
potenziale ={nodo:0 per nodo nel grafico} # Inizializza i potenziali
mentre è vero:
fonti =[nodo per nodo in alimentazione se l'alimentazione [nodo]> 0]
Sinks =[nodo per nodo in alimentazione se l'alimentazione [nodo] <0]
Se non fonti o non affonda:
Break # tutta la domanda/domanda soddisfatta
Source =Sources [0]
Sink =Sinks [0]
# Percorso più breve usando dijkstra con costi ridotti
dist, prev =dijkstra (grafico, capacità, costo, potenziale, fonte, lavandino, flusso)
se dist [Sink] ==float ('inf'):# nessun percorso trovato, impossibile
restituire nessuno # o gestire questo caso in modo diverso
# Flusso di aumento
Delta =min (Supply [Source], -Supply [Sink])
Curr =Sink
WHY Curr! =Fonte:
prev_node =prev [Curr]
Delta =min (Delta, Capacità [(prev_node, Curr)] - flusso [(prev_node, curr)])
Curr =prev_node
Curr =Sink
WHY Curr! =Fonte:
prev_node =prev [Curr]
flusso [(prev_node, curr)] +=delta
if (Curr, prev_node) in capacità:
Flow [(Curr, prev_node)] -=Delta # Flow all'indietro
altro:
Flow [(Curr, prev_node)] =-Delta # Inizializza se necessario.
Curr =prev_node
Supply [Source] -=Delta
Supply [Sink] +=Delta
# Aggiorna i potenziali utilizzando le distanze di Dijkstra
per il nodo nel grafico:
potenziale [nodo] +=dist [nodo]
Flusso di ritorno
def dijkstra (grafico, capacità, costo, potenziale, fonte, lavandino, flusso):
"" "
L'algoritmo di Dijkstra con costi ridotti.
"" "
dist ={nodo:float ('inf') per nodo nel grafico}
prev ={nodo:nessuno per nodo nel grafico}
dist [sorgente] =0
pq =[(0, sorgente)] # coda prioritaria (distanza, nodo)
Mentre PQ:
d, u =heapq.HeAppop (PQ)
if d> dist [u]:# eliminazione pigra
continuare
per v in grafico [u]:
# Considera solo i bordi con capacità residua> 0
se capacità [(u, v)] - flusso [(u, v)]> 0:
ridotto_cost =costo [(u, v)] + potenziale [u] - potenziale [v]
se dist [v]> dist [u] + ridotto_cost:
dist [v] =dist [u] + ridotto_cost
prev [v] =u
heapq.HeAppush (pq, (dist [v], v))
restituire dist, prev
grafico ={
's':['a', 'b'],
'a':['b', 't'],
'b':['t'],
'T':[]
}
capacità ={
('s', 'a'):10,
('s', 'b'):5,
('a', 'b'):4,
('a', 't'):8,
('b', 't'):12
}
cost ={
('s', 'a'):2,
('s', 'b'):4,
('a', 'b'):1,
('a', 't'):7,
('b', 't'):5
}
Supply ={
's':15,
'A':0,
'b':0,
'T':-15
}
Flow =successive_shortest_path (grafico, capacità, costo, fornitura)
Se flusso:
Stampa ("Assegnazione del flusso:", flusso)
# Calcola il costo totale
total_cost =sum (flusso [(u, v)] * costo [(u, v)] per (u, v) nel flusso)
Print ("Costo totale:", Total_Cost)
altro:
Stampa ("Nessuna soluzione fattibile trovata.")
`` `
Considerazioni importanti:
* Cicli di costo negativo: L'algoritmo SSP è progettato per gestire cicli di costo negativi. La potenziale funzione `pi (v)` è fondamentale per questo. Se non si aggiorna correttamente i potenziali, l'algoritmo potrebbe non convergere o produrre una soluzione errata.
* Dijkstra's vs. Bellman-Ford:
* Se * * sempre * mantieni i costi ridotti non negativi, l'algoritmo di Dijkstra è molto più veloce per trovare percorsi più brevi. Questo è lo scenario ideale e di solito si ottiene con potenziali aggiornamenti adeguati.
* Se non è possibile garantire costi ridotti non negativi, è * necessario * usare Bellman-Ford, che è più lenta (o (V * e) complessità del tempo). È spesso usato solo per il potenziale calcolo iniziale.
* Rete residua: Mantenere correttamente la rete residua è essenziale. Ricorda di creare bordi posteriori quando il flusso viene spinto lungo un arco.
* Complessità computazionale: La complessità dell'algoritmo SSP dipende dall'algoritmo del percorso più breve utilizzato e dal numero di iterazioni. Nel peggiore dei casi, può essere pseudo-polinomiale se le capacità sono grandi.
* Algoritmi alternativi: Per i problemi di flusso minimo su larga scala, altri algoritmi come l'algoritmo di rete Simplex sono spesso più efficienti.
In sintesi, l'algoritmo di percorso più breve successivo è un metodo potente e concettualmente chiaro per risolvere i problemi di flusso di costi minimi. Comprendere i ruoli della rete residua, i costi ridotti e la potenziale funzione è la chiave per implementarlo correttamente. Scegli l'algoritmo del percorso più breve appropriato (Dijkstra o Bellman-Ford) in base al fatto che sia possibile garantire costi ridotti non negativi. Ricorda di gestire gli aggiornamenti della domanda e della domanda e anche di aggiornare correttamente i potenziali.
networking © www.354353.com