Minimum-Cost-Flow-Problem

9

Ein Flussnetzwerk ist ein gerichteter Graph G = (V, E)mit einem Quell- s ϵ Vund einem Senkenscheitelpunkt t ϵ V, mit denen jeder Kante (u, v) ϵ Edes Graphen (Verbindungsknoten u ϵ Vund v ϵ V) zwei Größen zugeordnet sind:

  1. c(u, v) >= 0, die Kapazität der Kante
  2. a(u, v) >= 0, die Kosten für das Senden einer Einheit durch die Kante

Wir definieren eine Funktion 0 <= f(u, v) <= c(u, v)als die Anzahl der Einheiten, die durch eine bestimmte Kante geleitet werden (u, v). Somit sind die Kosten für eine bestimmte Kante (u, v)liegt a(u, v) * f(u, v). Das Problem des Mindestkostenflusses ist definiert als Minimierung der Gesamtkosten über alle Kanten für eine bestimmte Durchflussmenge d, gegeben durch die folgende Menge:

Kosten

Die folgenden Einschränkungen gelten für das Problem:

  1. Kapazitätsanforderungen : Der Durchfluss durch eine bestimmte Kante darf die Kapazität dieser Kante nicht überschreiten ( f(u, v) <= c(u, v)).
  2. Schrägsymmetrie : Die Strömung durch eine bestimmte Kante muss antisymmetrisch sein, wenn die Richtung umgekehrt wird ( f(u, v) = -f(v, u)).
  3. Flusserhaltung : der Nettofluss in jeden nicht-Senke nicht-Quellknoten muss 0 sein (für jeden u ∉ {s, t}, über alle Summieren w, sum f(u, w) = 0).
  4. Erforderliche Strömungs : das Netz von der Quelle ausfließen und dem Nettostrom in die Spüle beide müssen den erforderlichen Durchfluss durch das Netz equal (Summation über alle u, sum f(s, u) = sum f(u, t) = d).

Geben Sie bei einem Flow-Netzwerk Gund einem erforderlichen Flow ddie Mindestkosten für das Senden von dEinheiten über das Netzwerk aus. Sie können davon ausgehen, dass eine Lösung vorhanden ist. dAlle Kapazitäten und Kosten sind nicht negative ganze Zahlen. Bei einem Netzwerk mit mit Ngekennzeichneten [0, N-1]Scheitelpunkten ist der Quellscheitelpunkt 0und der Senkenscheitelpunkt N-1.

Dies ist , daher gewinnt die kürzeste Antwort (in Bytes). Denken Sie daran, dass dies ein Wettbewerb innerhalb von Sprachen sowie zwischen Sprachen ist. Haben Sie also keine Angst, eine Lösung in einer ausführlichen Sprache zu veröffentlichen.

Eingebaute sind zulässig, es wird jedoch empfohlen, Lösungen ohne eingebaute Elemente entweder als zusätzliche Lösung in dieselbe Antwort oder als unabhängige Antwort aufzunehmen.

Die Eingabe kann auf jede vernünftige Weise erfolgen, die die Kapazitäten und Kosten jeder Kante und die Nachfrage umfasst.

Testfälle

Testfälle werden im folgenden Format bereitgestellt:

c=<2D matrix of capacities> a=<2D matrix of costs> d=<demand> -> <solution>

c=[[0, 3, 2, 3, 2], [3, 0, 5, 3, 3], [2, 5, 0, 4, 5], [3, 3, 4, 0, 4], [2, 3, 5, 4, 0]] a=[[0, 1, 1, 2, 1], [1, 0, 1, 2, 3], [1, 1, 0, 2, 2], [2, 2, 2, 0, 3], [1, 3, 2, 3, 0]] d=7 -> 20
c=[[0, 1, 1, 5, 4], [1, 0, 2, 4, 2], [1, 2, 0, 1, 1], [5, 4, 1, 0, 3], [4, 2, 1, 3, 0]] a=[[0, 1, 1, 2, 2], [1, 0, 2, 4, 1], [1, 2, 0, 1, 1], [2, 4, 1, 0, 3], [2, 1, 1, 3, 0]] d=7 -> 17
c=[[0, 1, 4, 5, 4, 2, 3], [1, 0, 5, 4, 3, 3, 5], [4, 5, 0, 1, 5, 5, 5], [5, 4, 1, 0, 3, 2, 5], [4, 3, 5, 3, 0, 4, 4], [2, 3, 5, 2, 4, 0, 2], [3, 5, 5, 5, 4, 2, 0]] a=[[0, 1, 4, 2, 4, 1, 1], [1, 0, 3, 2, 2, 1, 1], [4, 3, 0, 1, 4, 5, 2], [2, 2, 1, 0, 2, 2, 3], [4, 2, 4, 2, 0, 4, 1], [1, 1, 5, 2, 4, 0, 2], [1, 1, 2, 3, 1, 2, 0]] d=10 -> 31
c=[[0, 16, 14, 10, 14, 11, 10, 4, 3, 16], [16, 0, 18, 19, 1, 6, 10, 19, 5, 4], [14, 18, 0, 2, 15, 9, 3, 14, 20, 13], [10, 19, 2, 0, 2, 10, 12, 17, 19, 22], [14, 1, 15, 2, 0, 11, 23, 25, 10, 19], [11, 6, 9, 10, 11, 0, 14, 16, 25, 4], [10, 10, 3, 12, 23, 14, 0, 11, 7, 8], [4, 19, 14, 17, 25, 16, 11, 0, 14, 5], [3, 5, 20, 19, 10, 25, 7, 14, 0, 22], [16, 4, 13, 22, 19, 4, 8, 5, 22, 0]] a=[[0, 12, 4, 2, 9, 1, 1, 3, 1, 6], [12, 0, 12, 16, 1, 2, 9, 13, 2, 3], [4, 12, 0, 2, 2, 2, 2, 10, 1, 1], [2, 16, 2, 0, 2, 1, 8, 4, 4, 2], [9, 1, 2, 2, 0, 5, 6, 23, 5, 8], [1, 2, 2, 1, 5, 0, 13, 12, 12, 1], [1, 9, 2, 8, 6, 13, 0, 9, 4, 4], [3, 13, 10, 4, 23, 12, 9, 0, 13, 1], [1, 2, 1, 4, 5, 12, 4, 13, 0, 13], [6, 3, 1, 2, 8, 1, 4, 1, 13, 0]] d=50 -> 213

Diese Testfälle wurden mit der NetworkX Python-Bibliothek berechnet .

Mego
quelle
Sandbox
Mego
1
Beim Golfspielen wurde mir lange klar, dass ich den falschen Algorithmus spielte, weil ich nicht lesen kann
Quintec

Antworten:

3

[R + lpSolve ], 201 186 149 144 Bytes

function(c,a,d,`^`=rep,N=ncol(c),G=diag(N),P=t(1^N),M=P%x%G+G%x%-P)lpSolve::lp(,a,rbind(M,diag(N*N)),c('=','<')^c(N,N*N),c(d,0^(N-2),-d,c))$objv

Probieren Sie es online aus!

Der Code erstellt das folgende lineare Problem und löst es mit dem lpSolvePaket:

minxV yVAx,yfx,ysubject to:xVfv,xfx,v=0vV:v{s,t}xVfs,xfx,s=dxVft,xfx,t=dfx,bCx,bxV,yV

  • V
  • s
  • t
  • Ax,yx -> y
  • fx,yx -> y
  • dts
  • Cx,yx -> y
digEmAll
quelle
Schöne, lineare Programmierung :) Leider haben die meisten Sprachen keine lpSolve... :(
Quintec
Das ist leider wahr ... Übrigens ist es nicht auf Base-R verfügbar, es ist ein Paket ... Ich musste darum bitten, auf TIO zu installieren;)
digEmAll
Aus irgendeinem Grund habe ich noch keinen kurzen Weg gefunden, MinCostMaxFlow zu MinCostFlow zu machen ... mein Gehirn ist gebraten lol, ich wünschte, es gäbe eine Funktion dafür in anderen Sprachen als mathematica
Quintec
@Quintec: Beziehen Sie sich auf eine bestimmte Implementierung (z. B. in einer bestimmten Sprache) von MinCostMaxFlow?
digEmAll
Nein, mein
handcodierter
1

Wolfram Language, 42 Bytes

FindMinimumCostFlow[#,1,VertexCount@#,#2]&

Trivial eingebaut. Nicht eingebaute Lösung kommt bald.

lirtosiast
quelle
Kommt es in 6-8 Wochen? : P
Quintec
1

Python 3 + NetworkX , 137 Bytes

from networkx import*
def f(g,d,z='demand'):N=len(g)**.5//1;G=DiGraph(g);G.node[0][z]=-d;G.node[N-1][z]=d;return min_cost_flow_cost(G)

Kein TryItOnline-Link, da in TIO die NetworkX-Bibliothek nicht installiert ist

Nimmt die Grafikeingabe als Kantenliste mit Kapazitäts- und Gewichtsattributen wie folgt:

[(0, 0, {'capacity': 0, 'weight': 0}), (0, 1, {'capacity': 3, 'weight': 1}), (0, 2, {'capacity': 2, 'weight': 1}), (0, 3, {'capacity': 3, 'weight': 2}), (0, 4, {'capacity': 2, 'weight': 1}), (1, 0, {'capacity': 3, 'weight': 1}), (1, 1, {'capacity': 0, 'weight': 0}), (1, 2, {'capacity': 5, 'weight': 1}), (1, 3, {'capacity': 3, 'weight': 2}), (1, 4, {'capacity': 3, 'weight': 3}), (2, 0, {'capacity': 2, 'weight': 1}), (2, 1, {'capacity': 5, 'weight': 1}), (2, 2, {'capacity': 0, 'weight': 0}), (2, 3, {'capacity': 4, 'weight': 2}), (2, 4, {'capacity': 5, 'weight': 2}), (3, 0, {'capacity': 3, 'weight': 2}), (3, 1, {'capacity': 3, 'weight': 2}), (3, 2, {'capacity': 4, 'weight': 2}), (3, 3, {'capacity': 0, 'weight': 0}), (3, 4, {'capacity': 4, 'weight': 3}), (4, 0, {'capacity': 2, 'weight': 1}), (4, 1, {'capacity': 3, 'weight': 3}), (4, 2, {'capacity': 5, 'weight': 2}), (4, 3, {'capacity': 4, 'weight': 3}), (4, 4, {'capacity': 0, 'weight': 0})]

Dies ist eine Golfversion des Codes, mit dem ich die Testfälle überprüft habe.

Mego
quelle