Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Definícia problému:
* sieť: Pracujete s riadeným grafom (sieťou), ktorý predstavuje:
* uzly (vrcholy): `V` (napr. Továrne, sklady, mestá)
* oblúky (hrany): `E` (napr. Cesty, potrubia, komunikačné spojenia)
* kapacity: Každý oblúk `(u, v)` in `e` má kapacitu` c (u, v) `predstavujúci maximálny tok, ktorý cez ňu môže prejsť.
* Náklady: Každý oblúk `(u, v)` in `e` má náklady„ náklady (u, v) „predstavujúce náklady na jednotku toku cez tento oblúk.
* ponuka/dopyt: Každý uzol `V` v` V` má napájanie `b (v)`.
* Ak `b (v)> 0`, uzol` v` je zdroj * s dodávkou `b (v)` jednotiek.
* Ak `b (v) <0`, uzol` v` je a * umývadlo * s požiadavkou `-b (v)` jednotiek.
* Ak `b (v) =0`, uzol` v` je prekladací uzol.
* Cieľ: Nájdite priradenie toku, ktorá minimalizuje celkové náklady na odosielanie toku cez sieť a zároveň spĺňa obmedzenia ponuky/dopytu a obmedzenia kapacity.
2. Inicializácia:
* Zostatková sieť: Vytvorte zvyškovú sieť `G_F` na základe pôvodnej siete` G`. Spočiatku `g_f =g`. Táto sieť sleduje dostupnú kapacitu. Pre každý oblúk `(u, v)` v `g` je zvyšková kapacita` c_f (u, v) =c (u, v) - f (u, v) `, kde` f (u, v) `je prúdom toku tohto oblúka. Spočiatku `f (u, v) =0` pre všetky oblúky.
* tok: Inicializujte prietok `f (u, v) =0` pre všetky oblúky v pôvodnej sieti.
* potenciály (ceny): Inicializujte potenciálnu funkciu `pi (v)` pre každý uzol `v` v` v`. Bežným východiskovým bodom je „pi (v) =0“ pre všetky `v`. Potenciály sú rozhodujúce pre manipuláciu s negatívnymi nákladovými cyklami.
3. Kroky algoritmu:
Jadrom postupného algoritmu najkratšej cesty je iteračný proces:
a. Nájdite zdroj a umývadlo: V sieti vyberte zdrojový uzol `S` (kde` b (s)> 0`) a uzol umývadla `t` (kde` b (t) <0`) v sieti. Ak takéto uzly neexistujú, algoritmus je kompletný.
b. najkratšia výpočet cesty: Nájdite najkratšiu cestu `p` z` S` do `T` v *zvyškovej sieti *` g_f` pomocou *znížených nákladov *. Znížené náklady na oblúk `(u, v)` sú definované ako:
`` `
COST_REDUED (u, v) =náklady (u, v) + pi (u) - pi (v)
`` `
* Cieľom použitia znížených nákladov je eliminovať negatívne nákladové cykly. Ak sú potenciály „pi` vybrané tak, aby„ náklady_reduced (u, v)> =0 “pre všetky oblúky, potom sa môže použiť algoritmus Dijkstra na nájdenie najkratšej cesty.
* Ak po použití potenciálu zostanú negatívne náklady, môže sa použiť algoritmus Bellman-Ford (ale vo všeobecnosti je pomalší).
c. tok rozšírenia: Nech `delta` je minimálne:
* `B (s)` (Zostávajúca dodávka pri zdroji `S`)
* `-B (t)` (Zostávajúci dopyt po umývadle `t`)
* Minimálna zvyšková kapacita pozdĺž najkratšej cesty `p`:` min {c_f (u, v) | (u, v) v p} `
Aktualizujte tok pozdĺž cesty `p` od` delta`:
* Pre každý oblúk `(u, v)` in `p`:
* `f (u, v) =f (u, v) + delta`
* Aktualizujte zvyškovú kapacitu:`C_F (u, v) =c (u, v) - f (u, v)`
* Ak `(u, v)` existuje v pôvodnej sieti, aktualizujte svoju reverznú hranu v zvyškovej sieti:Vytvorte hranu `(v, u)` in `g_f`, ak neexistuje s` c_f (v, u) =f (u, v) `.
d. Aktualizujte ponuku a dopyt:
* `b (s) =b (s) - delta`
* `b (t) =b (t) + delta`
e. Aktualizácia potenciálov (variant Bellman-Ford): Toto je * zásadný * krok na udržanie nezáporných znížených nákladov a zabezpečenie správneho správania. Po rozšírení toku musíte aktualizovať potenciály. Bežným prístupom (často používaným v spojení s Dijkstra po počiatočnom Bellman-Ford) je variant Bellman-Ford. To sa dá dosiahnuť pomocou najkratších vzdialeností cesty od predchádzajúcej iterácie, ale aplikované na všetky vrcholy. Kľúčom je zabezpečiť, aby sa riešili všetky záporné nákladové cykly zavedené zväčšením toku.
* Vlaž 1:Plný Bellman-Ford (menej efektívny): Znovu spustite Bellman-Ford z ľubovoľného uzla `r` do všetkých ostatných uzlov v` g_f` pomocou znížených nákladov. Nech `d (v)` je najkratšia vzdialenosť od `r` do` v`. Aktualizujte potenciály:`pi (v) =pi (v) - d (v)`. To zaručuje „COST_REDUED (u, v)> =0“ pre všetky oblúky po aktualizácii, ale je relatívne pomalý.
* Vlaž 2:Johnson's Algoritmus (efektívny): Raz spustite Bellman-Ford a vypočítajte počiatočné potenciály. Následne použite algoritmus Dijkstra pomocou znížených nákladov. Po každom rozšírení prehodnoťte potenciály pomocou výsledku Dijkstra.
f. Opakujte: Vráťte sa späť k kroku (a) a opakujte proces, kým nie sú splnené všetky zásoby a požiadavky (`b (v) =0` pre všetky uzly` v`).
4. Ukončenie:
Algoritmus sa ukončí, keď sú splnené všetky dodávky a požiadavky. Výsledný tok `f (u, v)` pre všetky oblúky `(u, v)` v pôvodnej sieti predstavuje minimálny tok nákladov.
Kľúčové dátové štruktúry:
* Zoznam/matica: Reprezentovať sieť „G` a zvyškovú sieť` G_F`. Zoznamy susedstva sú zvyčajne efektívnejšie pre riedke grafy.
* toková matica: Na uloženie prúdového toku `f (u, v)` na každom oblúku.
* Matica kapacity: Na uloženie pôvodných kapacít `C (u, v)` každého oblúka.
* Matica zvyškovej kapacity: Na ukladanie zvyškových kapacít `c_f (u, v)` v zvyškovej sieti.
* Potenciálne pole: Na uloženie potenciálov `pi (v)" pre každý uzol.
* prioritné fronty (halda): Používa sa v algoritme Dijkstra na efektívny výpočet najkratšej cesty.
Code Aspekty (príklad Python - zjednodušené):
`` `Python
import hale
defilieve_shortest_path (graf, kapacita, náklady, dodávka):
"" "
Implementuje postupný algoritmus najkratšej cesty.
ARG:
Graf:Slovník, ktorý predstavuje graf ako zoznam susedov.
Klávesy sú uzly, hodnoty sú zoznamy susedných uzlov.
Kapacita:Slovník predstavujúci kapacitu každej hrany (u, v).
Cena:Slovník predstavujúci náklady na každú hranu (u, v).
Dodávka:Slovník predstavujúci ponuku/dopyt z každého uzla.
Pozitívne hodnoty sú ponuky, záporné hodnoty sú dopyt.
Návraty:
Slovník predstavujúci tok na každej hrane alebo žiadny, ak nie je možné uskutočniteľné riešenie.
"" "
Flow ={} # Inicializujte tok na nulu
pre u v grafe:
pre V v grafe [u]:
prietok [(u, v)] =0
potenciál ={uzol:0 pre uzol v grafe} # Inicializujte potenciál
zatiaľ čo pravda:
Zdroje =[Uzol pre uzol v napájaní, ak napája [uzol]> 0]
Sins =[Uzol pre uzol v napájaní, ak napájanie [uzol] <0]
Ak nie sú zdroje alebo sa nepokúšajú:
Break # Všetky ponuky/dopyt splnené
Source =Zdroje [0]
Sink =umývadlá [0]
# Najkratšia cesta pomocou dijkstra so zníženými nákladmi
Dist, pred =dijkstra (graf, kapacita, náklady, potenciál, zdroj, umývadlo, tok)
Ak Dist [Sink] ==float ('inf'):# nenájdená cesta, nerealizovateľná
Vráťte žiadne # alebo zvládnuť tento prípad inak
# Tok rozšírenia
delta =min (napájanie [zdroj], -upply [umývadlo])
Curr =umývadlo
zatiaľ čo Curr! =Zdroj:
Prev_node =Prev [Curr]
delta =min (delta, kapacita [(Prev_node, curr)] - Flow [(predv_node, curr)])
Curr =pred_node
Curr =umývadlo
zatiaľ čo Curr! =Zdroj:
Prev_node =Prev [Curr]
Flow [(predv_node, curr)] +=delta
ak (curr, pred_node) v kapacite:
Flow [(Curr, pred_node)] -=Delta # spätný tok
inak:
Flow [(Curr, pred_node)] =-Delta # inicializujte, ak je to potrebné.
Curr =pred_node
dodávka [zdroj] -=delta
napájanie [umývadlo] +=delta
# Aktualizujte potenciály pomocou vzdialeností Dijkstra
pre uzol v grafe:
potenciál [uzol] +=dist [uzol]
spätný tok
def dijkstra (graf, kapacita, náklady, potenciál, zdroj, umývadlo, tok):
"" "
Algoritmus Dijkstra so zníženými nákladmi.
"" "
dist ={uzol:float ('inf') pre uzol v grafe}
pred ={uzol:žiadny pre uzol v grafe}
Dist [Source] =0
pq =[(0, zdroj)] # prioritný front (vzdialenosť, uzol)
zatiaľ čo PQ:
d, u =hepq.Heappop (pq)
Ak d> dist [u]:# lenivé vymazanie
pokračovať
pre V v grafe [u]:
# Zvážte iba hrany so zvyškovou kapacitou> 0
Ak je kapacita [(u, v)] - tok [(u, v)]> 0:
redukced_cost =náklady [(u, v)] + potenciál [u] - potenciál [v]
Ak DIST [v]> DIST [u] + redukced_cost:
Dist [v] =dist [u] + redukované_cost
Prev [v] =u
Hepq.Heappush (PQ, (Dist [V], V))
návrat dist, predv
graf ={
'S':['A', 'B'],
'a':['b', 't'],
'b':['t'],
't':[]
}
kapacita ={
('S', 'a'):10,
('S', 'B'):5,
('a', 'b'):4,
('a', 't'):8,
('b', 't'):12
}
Cena ={
('S', 'a'):2,
('S', 'B'):4,
('a', 'b'):1,
('a', 't'):7,
('b', 't'):5
}
dodávka ={
'S':15,
'a':0,
'b':0,
't':-15
}
Flow =následky_shortest_path (graf, kapacita, náklady, dodávka)
Ak tok:
tlač („Priradenie toku:“, tok)
# Vypočítajte celkové náklady
total_cost =súčet (prietok [(u, v)] * náklady [(u, v)] pre (u, v) v toku)
Tlač ("Celkové náklady:", total_cost)
inak:
Tlač („Nie je nájdené žiadne uskutočniteľné riešenie.“)
`` `
Dôležité úvahy:
* Cykly záporných nákladov: Algoritmus SSP je navrhnutý tak, aby zvládal negatívne nákladové cykly. Potenciálna funkcia `pi (v)` je pre to rozhodujúca. Ak neaktualizujete potenciály správne, algoritmus sa nesmie konvergovať alebo môže vytvárať nesprávne riešenie.
* Dijkstra vs. Bellman-ford:
* Ak * vždy * udržiavate nezáporné znížené náklady, algoritmus Dijkstra je oveľa rýchlejší na nájdenie najkratších ciest. Toto je ideálny scenár a zvyčajne sa dosahuje so správnymi potenciálnymi aktualizáciami.
* Ak nemôžete zaručiť nezáporné znížené náklady, musíte * používať Bellman-Ford, ktorý je pomalší (O (v * e) časová zložitosť). Často sa používa iba na počiatočný potenciálny výpočet.
* Zostatková sieť: Správne udržiavanie zvyškovej siete je nevyhnutné. Nezabudnite vytvoriť zadné hrany, keď je tok tlačený pozdĺž oblúka.
* Výpočtová zložitosť: Zložitosť algoritmu SSP závisí od najkratšieho použitého algoritmu cesty a počtu iterácií. V najhoršom prípade to môže byť pseudo-polynóm, ak sú kapacity veľké.
* Alternatívne algoritmy: V prípade rozsiahlych problémov s minimálnym tokom nákladov sú ďalšie algoritmy, ako je algoritmus siete Simplex, často efektívnejšie.
Stručne povedané, následný algoritmus najkratšej cesty je výkonná a koncepčne jasná metóda riešenia problémov s minimálnym tokom nákladov. Pochopenie úloh zvyškovej siete, znížené náklady a potenciálna funkcia je kľúčom k jej správnej implementácii. Vyberte príslušný algoritmus najkratšej cesty (Dijkstra alebo Bellman-Ford) na základe toho, či môžete zaručiť nezáporné znížené náklady. Nezabudnite spracovať aktualizácie ponuky a dopytu a tiež správne aktualizovať potenciály.