Den successive korteste sti (SSP) algoritme er en kraftfuld teknik til at løse minimumsomkostningsstrømningsproblemet i et netværk. Her er en oversigt over processen, der er involveret i implementering af den:

1. Problemdefinition:

* netværk: Du arbejder med en rettet graf (netværk) repræsenteret af:

* knudepunkter (vertices): `V` (f.eks. Fabrikker, lagre, byer)

* buer (kanter): `E` (f.eks. Veje, rørledninger, kommunikationslink)

* kapacitet: Hver bue `(u, v)` i `e 'har en kapacitet` c (u, v) `repræsenterer den maksimale strøm, der kan passere gennem den.

* Omkostninger: Hver bue `(u, v)` i `e 'har en omkostning` omkostning (u, v) `repræsenterer omkostningerne pr. Strømningsenhed gennem den bue.

* Forsyning/efterspørgsel: Hver knude `V` i` V` har en forsyning `B (V)`.

* Hvis `b (v)> 0`, er node` v` en * kilde * med en levering af `b (v)` enheder.

* Hvis `b (v) <0 ', er node` v` en * synk * med et krav om `-b (v)` enheder.

* Hvis `b (v) =0`, er knudepunkt` v` en omladningsknudepunkt.

* Mål: Find flowopgaven, der minimerer de samlede omkostninger ved at sende strømning gennem netværket, mens de opfylder begrænsninger for udbud/efterspørgsel og kapacitetsbegrænsninger.

2. Initialisering:

* resterende netværk: Opret et resterende netværk `g_f` baseret på det originale netværk` g '. Oprindeligt `g_f =g`. Dette netværk holder styr på den tilgængelige kapacitet. For hver bue `(u, v)` i `g` er den resterende kapacitet` c_f (u, v) =c (u, v) - f (u, v) `, hvor` f (u, v) `er den aktuelle strøm på den bue. Oprindeligt `f (u, v) =0 'for alle buer.

* flow: Initialiser flowet `f (u, v) =0` for alle buer i det originale netværk.

* potentialer (priser): Initialiser en potentiel funktion `pi (v)` for hver knude `v 'i` v'. Et almindeligt udgangspunkt er `pi (v) =0 'for alle' v '. Potentialerne er afgørende for håndtering af negative omkostningscyklusser.

3. Algoritme trin:

Kernen i den successive korteste sti -algoritme er en iterativ proces:

en. Find en kilde og en vask: Vælg en kildeknudepunkt `s` (hvor` b (s)> 0`) og en vaskeknudepunkt `t` (hvor` b (t) <0 ') i netværket. Hvis der ikke findes sådanne noder, er algoritmen komplet.

b. korteste sti beregning: Find den korteste sti `p` fra` s` til `t` i det *resterende netværk *` g_f` ved hjælp af de *reducerede omkostninger *. De reducerede omkostninger for en bue `(u, v)` defineres som:

`` `

Cost_reduced (u, v) =omkostninger (u, v) + pi (u) - pi (v)

`` `

* Målet med at bruge reducerede omkostninger er at eliminere negative omkostningscyklusser. Hvis potentialerne `pi` vælges således, at` cost_reduced (u, v)> =0` for alle buer, kan Dijkstra's algoritme bruges til at finde den korteste sti.

* Hvis der forbliver negative omkostninger efter anvendelse af potentialer, kan Bellman-Ford-algoritmen bruges (men det er generelt langsommere).

c. Augment Flow: Lad `Delta` være minimum af:

* `b (s)` (den resterende forsyning ved kilde `s`)

* `-b (t)` (den resterende efterspørgsel ved vask `t`)

* Den minimale restkapacitet langs den korteste sti `p`:` min {c_f (u, v) | (u, v) I p} `

Opdater strømmen langs stien `p` med` Delta`:

* For hver bue `(u, v)` i `p`:

* `f (u, v) =f (u, v) + Delta`

* Opdater restkapacitet:`C_F (u, v) =c (u, v) - f (u, v)`

* Hvis `(u, v)` findes i det originale netværk, skal du opdatere sin omvendte kant i det resterende netværk:Opret kanten `(v, u)` i `g_f`, hvis det ikke findes med` c_f (v, u) =f (u, v) `.

d. Opdater udbud og efterspørgsel:

* `b (s) =b (s) - Delta`

* `b (t) =b (t) + Delta`

e. Opdateringspotentialer (Bellman-Ford Variant): Dette er et * afgørende * trin for at opretholde ikke-negative reducerede omkostninger og sikre korrekt opførsel. Efter øget strømning skal du opdatere potentialerne. En almindelig tilgang (ofte brugt i forbindelse med Dijkstra efter en indledende Bellman-Ford) er en Bellman-Ford-variant. Dette kan gøres ved hjælp af den korteste stiafstand fra den foregående iteration, men påført på tværs af alle vertikater. Nøglen er at sikre, at eventuelle negative omkostningscyklusser, der introduceres ved strømningsforstørrelsen, håndteres.

* Valg 1:Full Bellman-Ford (mindre effektiv): RE-run Bellman-Ford fra en vilkårlig knude 'r` til alle andre noder i' G_F 'ved hjælp af de reducerede omkostninger. Lad `d (v)` være den korteste afstand fra `r` til` v`. Opdater potentialerne:`pi (v) =pi (v) - d (v)`. Dette garanterer `cost_reduced (u, v)> =0` for alle buer efter opdateringen, men er relativt langsom.

* Valg 2:Johnsons algoritme (effektiv): Kør Bellman-Ford en gang for at beregne de oprindelige potentialer. Brug derefter Dijkstras algoritme ved hjælp af de reducerede omkostninger. Efter hver forøgelse skal du omkomputer potentialerne ved hjælp af Dijkstras resultat.

f. Gentag: Gå tilbage til trin (a), og gentag processen, indtil alle forsyninger og krav er opfyldt (`b (v) =0` for alle noder` v`).

4. Opsigelse:

Algoritmen afsluttes, når alle forsyninger og krav er opfyldt. Den resulterende flow `f (u, v)` for alle buer `(u, v)` i det originale netværk repræsenterer den mindste omkostningsstrøm.

nøgledatakonstruktioner:

* Adjacency List/Matrix: At repræsentere netværket `g 'og det resterende netværk` g_f'. Adjacency -lister er typisk mere effektive til sparsomme grafer.

* flowmatrix: Sådan opbevares den aktuelle flow `f (u, v)` på hver bue.

* Kapacitetsmatrix: Sådan gemmer de originale kapaciteter `C (U, V)` for hver bue.

* Restkapacitetsmatrix: Sådan gemmer de resterende kapaciteter `C_F (U, V)` i det resterende netværk.

* Potentiel array: At gemme potentialerne `pi (v)` for hver knude.

* prioriteret kø (dynge): Brugt i Dijkstras algoritme til effektiv korteste sti beregning.

Kodeovervejelser (Python -eksempel - Forenklet):

`` `Python

Importer heapq

def Successive_shortest_path (graf, kapacitet, omkostninger, forsyning):

"" "

Implementerer den på hinanden følgende korteste sti -algoritme.

Args:

Graf:En ordbog, der repræsenterer grafen som en adjacency -liste.

Taster er noder, værdier er lister over nærliggende noder.

Kapacitet:En ordbog, der repræsenterer kapaciteten for hver kant (U, V).

Omkostninger:En ordbog, der repræsenterer omkostningerne ved hver kant (U, V).

Forsyning:En ordbog, der repræsenterer udbuddet/efterspørgslen for hver knude.

Positive værdier er udbud, negative værdier er efterspørgsel.

Returnerer:

En ordbog, der repræsenterer strømmen på hver kant, eller ingen, hvis ingen mulig løsning.

"" "

flow ={} # initialiser flow til nul

For dig i graf:

For V i graf [u]:

flow [(u, v)] =0

Potential ={Node:0 for knudepunkt i graf} # Initialiser potentialer

Mens sandt:

Kilder =[Node for Node in Supply If Supply [Node]> 0]

dræn =[knudepunkt for knudepunkt i forsyning, hvis levering [knude] <0]

Hvis ikke kilder eller ikke synker:

Break # All Supply/Demand tilfreds

Kilde =Kilder [0]

Sink =synke [0]

# Korteste sti ved hjælp af Dijkstra med reducerede omkostninger

dist, prev =dijkstra (graf, kapacitet, omkostninger, potentiale, kilde, vask, flow)

Hvis dist [Sink] ==float ('Inf'):# ingen sti fundet, umulig

returner ingen # eller håndtere denne sag forskelligt

# Augment Flow

Delta =min (forsyning [kilde], -supply [Sink])

Curr =Sink

Mens Curr! =Kilde:

prev_node =prev [curr]

Delta =min (delta, kapacitet [(prev_node, curr)] - flow [(prev_node, curr)])

curr =prev_node

Curr =Sink

Mens Curr! =Kilde:

prev_node =prev [curr]

flow [(prev_node, curr)] +=delta

if (curr, prev_node) i kapacitet:

flow [(curr, prev_node)] -=Delta # baglæns flow

andet:

flow [(curr, prev_node)] =-delta # initialisen om nødvendigt.

curr =prev_node

Forsyning [Kilde] -=Delta

Forsyning [Sink] +=Delta

# Opdater potentialer ved hjælp af Dijkstras afstande

For knude i graf:

Potentiale [Node] +=Dist [Node]

returstrøm

def dijkstra (graf, kapacitet, omkostninger, potentiale, kilde, vask, flow):

"" "

Dijkstra's algoritme med reducerede omkostninger.

"" "

dist ={node:float ('inf') til knudepunkt i graf}

prev ={node:ingen til knudepunkt i graf}

dist [kilde] =0

PQ =[(0, kilde)] # Prioritetskø (afstand, knude)

Mens PQ:

D, U =Heapq.HeAPPOP (PQ)

Hvis d> dist [u]:# doven sletning

fortsætte

For V i graf [u]:

# Overvej kun kanter med restkapacitet> 0

Hvis kapacitet [(u, v)] - flow [(u, v)]> 0:

reduceret_cost =omkostninger [(u, v)] + potentiale [u] - potentiale [v]

hvis dist [v]> dist [u] + reduceret_cost:

dist [v] =dist [u] + reduceret_cost

Forrige [v] =u

Heapq.heapush (PQ, (dist [v], v))

returner dist, prev

Eksempel Anvendelse:

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

}

omkostninger ={

('s', 'a'):2,

('S', 'B'):4,

('a', 'b'):1,

('a', 't'):7,

('B', 't'):5

}

forsyning ={

'S':15,

'A':0,

'B':0,

'T':-15

}

flow =successive_shortest_path (graf, kapacitet, omkostninger, forsyning)

Hvis flow:

Print ("Flowopgave:", Flow)

# Beregn de samlede omkostninger

total_cost =sum (flow [(u, v)] * omkostninger [(u, v)] for (u, v) i flow)

Print ("Samlede omkostninger:", Total_Cost)

andet:

Udskriv ("Ingen gennemførlig løsning fundet.")

`` `

Vigtige overvejelser:

* negative omkostningscyklusser: SSP -algoritmen er designet til at håndtere negative omkostningscyklusser. Den potentielle funktion `pi (v)` er kritisk for dette. Hvis du ikke opdaterer potentialerne korrekt, kan algoritmen muligvis ikke konvergere eller muligvis producere en forkert løsning.

* Dijkstra's vs. Bellman-Ford:

* Hvis du * altid * opretholder ikke-negative reducerede omkostninger, er Dijkstra's algoritme meget hurtigere til at finde korteste stier. Dette er det ideelle scenarie og opnås normalt med korrekte potentielle opdateringer.

* Hvis du ikke kan garantere ikke-negative reducerede omkostninger, skal du * bruge Bellman-Ford, som er langsommere (O (v * e) tidskompleksitet). Det bruges ofte kun til den indledende potentielle beregning.

* resterende netværk: Det er vigtigt at opretholde det resterende netværk. Husk at oprette rygkanter, når strømmen skubbes langs en bue.

* Beregningskompleksitet: Kompleksiteten af ​​SSP -algoritmen afhænger af den korteste sti -algoritme, der er anvendt og antallet af iterationer. I værste tilfælde kan det være pseudopolynom, hvis kapaciteten er store.

* alternative algoritmer: For storstilet minimumsomkostningsstrømningsproblemer er andre algoritmer som Network Simplex-algoritmen ofte mere effektive.

Sammenfattende er den successive korteste sti -algoritme en kraftig og konceptuelt klar metode til at løse minimumsomkostningsstrømningsproblemer. At forstå rollerne for det resterende netværk, reducerede omkostninger og potentiel funktion er nøglen til at implementere det korrekt. Vælg den passende korteste sti-algoritme (Dijkstra eller Bellman-Ford) baseret på, om du kan garantere ikke-negative reducerede omkostninger. Husk at håndtere opdateringerne i udbuddet og efterspørgslen og også opdatere potentialerne korrekt.