Out-of-kilter algoritm

Den out-of-kilter-algoritmen är en algoritm som beräknar lösningen på minimikostnadsflödesproblemet i ett flödesnätverk . Den gavs ut 1961 av DR Fulkerson och beskrivs här. Analogen av steady state-flöde i ett nätverk av noder och bågar kan beskriva en mängd olika processer. Exempel inkluderar transportsystem och personaluppdrag. Bågar har i allmänhet kostnads- och kapacitetsparametrar. Ett återkommande problem är att försöka bestämma den lägsta kostnadsvägen mellan två punkter i ett kapaciterat nätverk. Tanken med algoritmen är att identifiera out-of-kilter-bågar och modifiera flödesnätverket tills alla bågar är in-kilter och ett lägsta kostnadsflöde har uppnåtts. Algoritmen kan användas för att minimera den totala kostnaden för ett begränsat flöde i ett orienterat nätverk.

Algoritm

Till att börja med tar algoritmen en enda cykel och en uppsättning nodnummer. Den söker sedan efter out-of-kilter bågar. Om ingen hittas är algoritmen komplett. Om flödet behöver ökas eller minskas för att få en båge i kilter, kommer algoritmen att leta efter en väg som ökar respektive minskar flödet. Om inga vägar hittas för att förbättra systemet finns det inget genomförbart flöde. Detta görs tills alla bågar är i kilter, vid vilken tidpunkt algoritmen är klar.

Antag att nätverket har n noder och m orienterade bågar. Vi skriver $j~(i,i^{1})$ om båge $j$ har initial nod $i$ och terminalnod $i ^{1}$ . Låt $x(j)$ vara flödet längs bågen $j$ (från nod $i$ till nod $i^{1}$ ). Definiera $c^{-}(j)$ och $c^{+}(j)$ som de nedre och övre kapacitetsgränserna för flödet i båge $j$ . Kapaciteterna kan vara antingen ändliga eller oändliga på några eller alla bågar för antingen de nedre eller övre gränserna. Problemet som är till hands att lösa är att minimera: $\sum _{j=1}^{m}d(j)x(j)$ ämne till:

$\sum _{j:j~(i,i^{1}) }x(j)-\summa _{j:j~(i^{1},i)}x(j)=0$ för varje $i=1,....,n$ (1)

, och:

$c^{-}(j)\leq x(j)\leq c^{+}(j)$ för varje $j=1,....,n$ (2)

Om ett givet flöde x uppfyller (1), så bevaras flödet vid varje nod och vi kallar flödet för en cirkulation. Om flödet x uppfyller (2) säger vi att det är genomförbart.

Komplexitet

Körning:

• Algoritmen avslutas inom $O(mU)$ iterationer
• Dominant beräkning är kortaste vägberäkning
• Total körtid är: $O(m^{2}U+mUn\log(n))$

externa länkar

• på YouTube (på spanska)