Den successiva kortaste sökvägen (SSP) -algoritmen är en kraftfull teknik för att lösa problemet med minsta kostnadsflödesflödesflödesflödet. Här är en uppdelning av processen som är involverad i att implementera den:
1. Problemdefinition:
* nätverk: Du arbetar med en riktad graf (nätverk) representerad av:
* noder (vertikaler): `V` (t.ex. fabriker, lager, städer)
* bågar (kanter): `E` (t.ex. vägar, rörledningar, kommunikationslänkar)
* kapacitet: Varje båge `(u, v)` i `e` har en kapacitet` c (u, v) `som representerar det maximala flödet som kan passera genom det.
* Kostnader: Varje båge `(u, v)` i `e` har en kostnad` kostnad (u, v) `som representerar kostnaden per flödesenhet genom den bågen.
* Utbud/efterfrågan: Varje nod `v` i` v` har en tillförsel `b (v)`.
* Om `B (V)> 0`, är Node` V` en * källa * med en leverans av `B (V)` enheter.
* Om `B (V) <0`, är Node` V` en * sjunka * med en efterfrågan på `-b (V)` enheter.
* Om `B (V) =0`, är Node` V` en omlastningsnod.
* Mål: Hitta flödesuppdraget som minimerar den totala kostnaden för att skicka flöde genom nätverket och samtidigt tillfredsställa utbud/efterfrågan begränsningar och kapacitetsbegränsningar.
2. Initialisering:
* restnätverk: Skapa ett kvarvarande nätverk `g_f` baserat på det ursprungliga nätverket` g`. Ursprungligen `g_f =g`. Detta nätverk håller reda på tillgänglig kapacitet. För varje båge `(u, v)` i `g` är restkapaciteten` c_f (u, v) =c (u, v) - f (u, v) `, där` f (u, v) `är det nuvarande flödet på den bågen. Ursprungligen `f (u, v) =0` för alla bågar.
* flöde: Initiera flödet `f (u, v) =0` för alla bågar i det ursprungliga nätverket.
* potentialer (priser): Initiera en potentiell funktion `pi (v)` för varje nod `v` i` v`. En vanlig utgångspunkt är `pi (v) =0` för alla` v`. Potentialerna är avgörande för att hantera negativa kostnadscykler.
3. Algoritmsteg:
Kärnan i den successiva kortaste sökvägsalgoritmen är en iterativ process:
a. Hitta en källa och en diskbänk: Välj en källnod `s` (där` b (s)> 0`) och en sjunknod `t` (där` b (t) <0`) i nätverket. Om det inte finns några sådana noder är algoritmen klar.
b. Kortaste vägberäkning: Hitta den kortaste vägen `p` från` s` till `t` i *restnätverket *` g_f` med *reducerade kostnader *. Den reducerade kostnaden för en båge `(u, v)` definieras som:
`` `
cost_reduced (u, v) =kostnad (u, v) + pi (u) - pi (v)
`` `
* Målet med att använda reducerade kostnader är att eliminera negativa kostnadscykler. Om potentialerna "pi" väljs så att "cost_reduced (u, v)> =0" för alla bågar, kan Dijkstras algoritm användas för att hitta den kortaste vägen.
* Om negativa kostnader kvarstår efter tillämpning av potentialer kan Bellman-Ford-algoritmen användas (men det är i allmänhet långsammare).
c. Augment Flow: Låt `delta` vara det minsta av:
* `B (s)` (den återstående leveransen vid källan `s`)
* `-b (t)` (den återstående efterfrågan på Sink `T`)
* Minsta restkapacitet längs den kortaste vägen `p`:` min {c_f (u, v) | (u, v) i p} `
Uppdatera flödet längs vägen `p` av` delta`:
* För varje båge `(u, v)` i `p`:
* `f (u, v) =f (u, v) + delta`
* Uppdatera restkapacitet:`c_f (u, v) =c (u, v) - f (u, v)`
* Om `(u, v)` finns i det ursprungliga nätverket, uppdatera dess omvända kant i det kvarvarande nätverket:skapa kanten `(v, u)` i 'g_f' om det inte finns med 'c_f (v, u) =f (u, v) `.
d. Uppdatera utbud och efterfrågan:
* `B (s) =b (s) - delta`
* `B (t) =b (t) + delta`
e. Uppdateringspotentialer (Bellman-Ford Variant): Detta är ett * avgörande * steg för att upprätthålla icke-negativa minskade kostnader och säkerställa korrekt beteende. Efter förstärkning av flödet måste du uppdatera potentialen. Ett vanligt tillvägagångssätt (som ofta används i samband med Dijkstra efter en första Bellman-Ford) är en Bellman-Ford-variant. Detta kan göras med hjälp av de kortaste vägavståndet från den tidigare iterationen, men tillämpas över alla hörn. Nyckeln är att se till att eventuella negativa kostnadscykler som införts genom flödesförstärkningen hanteras.
* Alternativ 1:Full Bellman-Ford (mindre effektiv): Kör tillbaka Bellman-Ford från en godtycklig nod `r` till alla andra noder i` g_f` med hjälp av de reducerade kostnaderna. Låt `d (v)` vara det kortaste avståndet från `r` till` v`. Uppdatera potentialen:`pi (v) =pi (v) - d (v)`. Detta garanterar `cost_reduced (u, v)> =0` för alla bågar efter uppdateringen, men är relativt långsam.
* Alternativ 2:Johnsons algoritm (effektiv): Kör Bellman-Ford en gång för att beräkna initiala potentialer. Använd därefter Dijkstras algoritm med hjälp av de reducerade kostnaderna. Efter varje förstärkning kan du kompensera potentialerna med Dijkstras resultat.
f. Upprepa: Gå tillbaka till steg (a) och upprepa processen tills alla leveranser och krav är uppfyllda (`b (v) =0` för alla noder` v`).
4. Uppsägning:
Algoritmen avslutas när alla leveranser och krav är uppfyllda. Det resulterande flödet `f (u, v)` för alla bågar `(u, v)` i det ursprungliga nätverket representerar minsta kostnadsflöde.
Nyckeldatastrukturer:
* Adjucy List/Matrix: För att representera nätverket `G` och det återstående nätverket` g_f`. Adjacenslistor är vanligtvis mer effektiva för glesa grafer.
* Flödesmatris: För att lagra det nuvarande flödet `f (u, v)` på varje båge.
* kapacitetsmatris: För att lagra den ursprungliga kapaciteten `c (u, v)` för varje båge.
* Restkapacitetsmatris: För att lagra den återstående kapaciteten `c_f (u, v)` i det restnätverket.
* Potential Array: För att lagra potentialerna `pi (v)` för varje nod.
* Prioritetskö (hög): Används i Dijkstras algoritm för effektiv kortaste vägberäkning.
Kodöverväganden (Python Exempel - Förenklad):
`` `python
importhög
def successive_shortest_path (graf, kapacitet, kostnad, leverans):
"" "
Implementerar den på varandra följande kortalgoritmen.
Args:
Diagram:En ordbok som representerar grafen som en adjacenslista.
Nycklar är noder, värden är listor över angränsande noder.
Kapacitet:En ordbok som representerar kapaciteten för varje kant (U, V).
Kostnad:En ordbok som representerar kostnaden för varje kant (U, V).
Leverans:En ordbok som representerar utbudet/efterfrågan för varje nod.
Positiva värden är utbud, negativa värden är efterfrågan.
Returnerar:
En ordbok som representerar flödet på varje kant, eller ingen om ingen genomförbar lösning.
"" "
flöde ={} # initialisera flödet till noll
för dig i graf:
för V i graf [u]:
flöde [(u, v)] =0
Potential ={nod:0 för nod i graf} # Initiera potentialer
Även om det är sant:
Källor =[nod för nod i tillförsel om leverans [nod]> 0]
Sänkor =[nod för nod i tillförsel om tillförsel [nod] <0]
Om inte källor eller inte sjunker:
Break # All utbud/efterfrågan nöjd
källa =källor [0]
Sänk =sänkor [0]
# Kortaste väg med Dijkstra med reducerade kostnader
dist, prev =dijkstra (graf, kapacitet, kostnad, potential, källa, handfat, flöde)
om dist [sjunka] ==float ('inf'):# ingen väg hittad, omöjlig
returnera ingen # eller hantera detta fall annorlunda
# Augment Flow
delta =min (leverans [källa], -supply [sjunka])
curr =sjunka
Medan Curr! =Källa:
prev_node =prev [curr]
delta =min (delta, kapacitet [(prev_node, curr)] - flöde [(prev_node, curr)])
curr =prev_node
curr =sjunka
Medan Curr! =Källa:
prev_node =prev [curr]
flöde [(prev_node, curr)] +=delta
if (curr, prev_node) i kapacitet:
flöde [(curr, prev_node)] -=Delta # bakåtflöde
annan:
flöde [(curr, prev_node)] =-delta # initialisera vid behov.
curr =prev_node
leverans [källa] -=delta
leverera [sjunka] +=delta
# Uppdatera potentialer med Dijkstras avstånd
För nod i graf:
Potential [Node] +=Dist [Node]
returflöde
def dijkstra (graf, kapacitet, kostnad, potential, källa, handfat, flöde):
"" "
Dijkstras algoritm med minskade kostnader.
"" "
dist ={nod:float ('inf') för nod i graf}
föregående ={nod:ingen för nod i graf}
dist [källa] =0
PQ =[(0, källa)] # Prioritetskö (avstånd, nod)
Medan PQ:
d, u =heapq.heappop (pq)
om d> dist [u]:# lat borttagning
fortsätta
för V i graf [u]:
# Tänk endast på kanter med restkapacitet> 0
om kapacitet [(u, v)] - flöde [(u, v)]> 0:
reducerad_cost =kostnad [(u, v)] + potential [u] - potential [v]
if dist [v]> dist [u] + reducerad_kost:
dist [v] =dist [u] + reducerad_kost
föregående [v] =u
Heapq.heAppusH (PQ, (Dist [V], V))
Return Dist, Prev
Exempel Användning:
graf ={
'S':['a', 'b'],
'A':['B', 'T'],
'B':['t'],
't':[]
}
kapacitet ={
('s', 'a'):10,
('S', 'B'):5,
('a', 'b'):4,
('a', 't'):8,
('B', 'T'):12
}
kostnad ={
('s', 'a'):2,
('S', 'B'):4,
('a', 'b'):1,
('a', 't'):7,
('b', 't'):5
}
leverans ={
'S':15,
'A':0,
'B':0,
't':-15
}
flöde =successiv_shortest_path (graf, kapacitet, kostnad, leverans)
Om flöde:
tryck ("Flow Assignment:", flöde)
# Beräkna den totala kostnaden
Total_cost =summa (flöde [(u, v)] * kostnad [(u, v)] för (u, v) i flöde)
utskrift ("Total kostnad:", total_cost)
annan:
utskrift ("Ingen genomförbar lösning hittades.")
`` `
Viktiga överväganden:
* Negativa kostnadscykler: SSP -algoritmen är utformad för att hantera negativa kostnadscykler. Den potentiella funktionen `pi (v)` är avgörande för detta. Om du inte uppdaterar potentialen korrekt kan algoritmen inte konvergera eller kan ge en felaktig lösning.
* Dijkstra's vs. Bellman-Ford:
* Om du * alltid * upprätthåller icke-negativa minskade kostnader är Dijkstras algoritm mycket snabbare för att hitta kortaste vägar. Detta är det ideala scenariot och uppnås vanligtvis med lämpliga potentiella uppdateringar.
* Om du inte kan garantera icke-negativa minskade kostnader måste du * använda Bellman-Ford, vilket är långsammare (O (V * E) tidskomplexitet). Det används ofta endast för den initiala potentiella beräkningen.
* restnätverk: Att upprätthålla det återstående nätverket korrekt är viktigt. Kom ihåg att skapa bakkanter när flödet skjuts längs en båge.
* Beräkningskomplexitet: Komplexiteten hos SSP -algoritmen beror på den kortaste sökalgoritmen som används och antalet iterationer. I värsta fall kan det vara pseudopolynom om kapaciteten är stor.
* Alternativa algoritmer: För storskaliga minimikostnadsflödesproblem är andra algoritmer som nätverk Simplex-algoritmen ofta mer effektiva.
Sammanfattningsvis är den successiva kortaste vägalgoritmen en kraftfull och konceptuellt tydlig metod för att lösa minimikostnadsflödesproblem. Att förstå rollerna för det återstående nätverket, reducerade kostnader och potentiell funktion är nyckeln till att implementera det korrekt. Välj lämplig kortaste sökvägsalgoritm (Dijkstra eller Bellman-Ford) baserat på om du kan garantera icke-negativa minskade kostnader. Kom ihåg att hantera uppdateringarna i utbudet och efterfrågan och också uppdatera potentialerna korrekt.
