Cirkulationsproblem - Circulation problem

Den cirkulationsproblem och dess varianter är en generalisering av nätverksflödesproblem, med den extra begränsning av en lägre gräns för kanten flöden, och med bevarande flöde också krävs för källan och sjunker (dvs det finns inga speciella noder). I varianter av problemet finns det flera varor som flödar genom nätverket och en kostnad för flödet.

Definition

Givet flödesnätverk med: ${\ displaystyle G (V, E)}$

${\ displaystyle l (v, w)}$, nedre gränsen på flöde från nod till nod ,${\ displaystyle v}$${\ displaystyle w}$

${\ displaystyle u (v, w)}$, övre gräns på flöde från nod till nod ,${\ displaystyle v}$${\ displaystyle w}$

${\ displaystyle c (v, w)}$, kostnad för en flödesenhet på ${\ displaystyle (v, w)}$

och begränsningarna:

${\ displaystyle l (v, w) \ leq f (v, w) \ leq u (v, w)}$,

${\ displaystyle \ sum _ {w \ in V} f (u, w) = 0}$ (flöde kan inte visas eller försvinna i noder).

Att hitta en flödesuppgift som uppfyller begränsningarna ger en lösning på det givna cirkulationsproblemet.

Minimera i minimikostnadsvarianten av problemet

${\ displaystyle \ sum _ {(v, w) \ in E} c (v, w) \ cdot f (v, w).}$

Cirkulation med flera varor

I ett cirkulationsproblem med flera varor måste du också hålla reda på flödet för de enskilda varorna:

${\ displaystyle \, f_ {i} (v, w)}$	Varuflödet från till . ${\ displaystyle i}$${\ displaystyle v}$${\ displaystyle w}$
${\ displaystyle \, f (v, w) = \ sum _ {i} f_ {i} (v, w)}$	Det totala flödet.

Det finns också en nedre gräns för varje varuflöde.

${\ displaystyle \, l_ {i} (v, w) \ leq f_ {i} (v, w)}$

Bevarandebegränsningen måste upprätthållas individuellt för varorna:

${\ displaystyle \ \ sum _ {w \ in V} f_ {i} (u, w) = 0.}$

Lösning

För cirkulationsproblemet har många polynomalgoritmer utvecklats (t.ex. Edmonds och Karp algoritm , 1972; Tarjan 1987-1988). Tardos hittade den första starkt polynomialgoritmen.

För flera varor är problemet NP-komplett för heltalströmmar. För fraktionsflöden är det lösbart under polynomtid , eftersom man kan formulera problemet som ett linjärt program .

Relaterade problem

Nedan ges några problem och hur man löser dem med den allmänna cirkulationsinställningen som anges ovan.

• Lägsta kostnad med cirkulationsproblem med flera varor - Använd alla begränsningar som anges ovan.
• Problem med lägsta kostnadscirkulation - Använd en enda vara
• Cirkulation med flera varor - Lös utan att optimera kostnaden.
• Enkel cirkulation - använd bara en vara utan kostnad.
• Flödesvaruflöde - Om det indikerar ett krav på varan från till , skapa en kant med för alla varor . Låt för alla andra kanter.${\ displaystyle K_ {i} (s_ {i}, t_ {i}, d_ {i})}$${\ displaystyle d_ {i}}$${\ displaystyle i}$${\ displaystyle s_ {i}}$${\ displaystyle t_ {i}}$${\ displaystyle (t_ {i}, s_ {i})}$${\ displaystyle l_ {i} (t_ {i}, s_ {i}) = u (t_ {i}, s_ {i}) = d_ {i}}$${\ displaystyle i}$${\ displaystyle l_ {i} (u, v) = 0}$
• Problem med flödesvaror för minimikostnader - Som ovan, men minimera kostnaden.
• Minsta kostnadsflödesproblem - Som ovan, med en vara.
• Maximalt flödesproblem - Ställ in alla kostnader på 0 och lägg till en kant från diskbänken till källan med , ∞ och .${\ displaystyle t}$${\ displaystyle s}$${\ displaystyle l (t, s) = 0}$${\ displaystyle u (t, s) =}$${\ displaystyle c (t, s) = - 1}$
• Minsta kostnad för maximal flöde - Hitta först det maximala flödet . Lös sedan med och .${\ displaystyle m}$${\ displaystyle l (t, s) = u (t, s) = m}$${\ displaystyle c (t, s) = 0}$
• Kortaste sökvägen med en källa - Låt och för alla kanter i diagrammet och lägg till en kant med och .${\ displaystyle l (u, v) = 0}$${\ displaystyle c (u, v) = 1}$${\ displaystyle (t, s)}$${\ displaystyle l (t, s) = c (t, s) = 1}$${\ displaystyle a (t, s) = 0}$
• Kortaste sökvägen för alla par - Låt alla kapaciteter vara obegränsade och hitta ett flöde på 1 för varor, en för varje noderpar.${\ displaystyle v (v-1) / 2}$

referenser