Algoritmus out-of-kilter - Out-of-kilter algorithm

The algoritmus mimo kilter je algoritmus který počítá řešení do problém toku minimálních nákladů v toková síť. To bylo vydáváno v roce 1961 autorem D. R. Fulkerson  ^[1] a je zde popsán.^[2] Analog toku ustáleného stavu v síti uzlů a oblouků může popisovat celou řadu procesů. Mezi příklady patří dopravní systémy a akce přiřazení personálu. Oblouky mají obecně parametry nákladů a kapacity. Opakující se problém se pokouší určit trasu s minimálními náklady mezi dvěma body v kapacitní síti. Myšlenkou algoritmu je identifikovat oblouky mimo kilter a modifikovat tokovou síť, dokud nejsou všechny oblouky in-kilter a nebude dosaženo minimálního toku nákladů. Algoritmus lze použít k minimalizaci celkových nákladů na omezený tok v orientované síti.

Algoritmus

Pro začátek algoritmus trvá jediný cyklus a sadu čísel uzlů. Poté hledá oblouky mimo kilter. Pokud žádný není nalezen, je algoritmus kompletní. Pokud je potřeba zvýšit nebo snížit tok, aby se oblouk dostal do kilteru, bude algoritmus hledat cestu, která tok zvýší nebo sníží. Pokud nejsou nalezeny žádné cesty ke zlepšení systému, pak neexistuje proveditelný tok. To se provádí, dokud nejsou všechny oblouky in-kilter, kdy je algoritmus dokončen.

Předpokládejme, že síť má n uzlů am oblouky orientované. Píšeme ${ displaystyle j ~ (i, i ^ {1})}$ pokud oblouk ${ displaystyle j}$ má počáteční uzel ${ displaystyle i}$ a koncový uzel ${ displaystyle i ^ {1}}$. Nechat ${ displaystyle x (j)}$ být tok podél oblouku ${ displaystyle j}$ (z uzlu ${ displaystyle i}$ do uzlu ${ displaystyle i ^ {1}}$). Definovat ${ displaystyle c ^ {-} (j)}$ a ${ displaystyle c ^ {+} (j)}$ být dolní a horní hranicí kapacity toku v oblouku ${ displaystyle j}$. Kapacity mohou být buď konečné, nebo nekonečné pro některé nebo všechny oblouky pro dolní nebo horní hranici. Problém, který je třeba vyřešit, je minimalizovat: ${ displaystyle sum _ {j = 1} ^ {m} d (j) x (j)}$ podléhá:

${ displaystyle sum _ {j: j ~ (i, i ^ {1})} x (j) - sum _ {j: j ~ (i ^ {1}, i)} x (j) = 0 }$ pro každého ${ displaystyle i = 1, ...., n}$ (1)

, a:

${ displaystyle c ^ {-} (j) leq x (j) leq c ^ {+} (j)}$ pro každého ${ displaystyle j = 1, ...., n}$ (2)

Pokud daný tok x vyhovuje (1), pak je tok zachován v každém uzlu a tok nazýváme cirkulací. Pokud tok x vyhovuje (2), říkáme, že je to možné.

Složitost

Runtime:

• Algoritmus končí uvnitř ${ displaystyle O (mU)}$ iterace
• Dominantní výpočet je výpočet nejkratší cesty
• Celková doba běhu je: ${ displaystyle O (m ^ {2} U + mUn log (n))}$

Reference

^[1]

externí odkazy

• Algoritmo mimo Kilter na Youtube (ve španělštině)