Problem minimalnego kosztu przepływu

Sieć przepływowa jest kierowanym wykresem G = (V, E)z wierzchołkiem źródłowym s ϵ Vi wierzchołkiem pochłaniającym t ϵ V, a każda krawędź (u, v) ϵ Ena wykresie (łącząca węzły u ϵ Vi v ϵ V) ma z nią 2 wielkości:

c(u, v) >= 0, pojemność krawędzi
a(u, v) >= 0, koszt wysłania jednej jednostki przez krawędź

Definiujemy funkcję 0 <= f(u, v) <= c(u, v)jako liczbę jednostek przechodzących przez daną krawędź (u, v). Zatem koszt danej krawędzi (u, v)wynosi a(u, v) * f(u, v). Problem minimalnego kosztu przepływu jest definiowany jako minimalizacja całkowitego kosztu na wszystkich krawędziach dla danej kwoty przepływu d, podana przez następującą ilość:

Problem dotyczy następujących ograniczeń:

Wymagania dotyczące pojemności : przepływ przez daną krawędź nie może przekraczać pojemności tej krawędzi ( f(u, v) <= c(u, v)).
Pochylenie symetrii : przepływ przez daną krawędź musi być niesymetryczny, gdy kierunek jest odwrócony ( f(u, v) = -f(v, u)).
Przepływ ochrony : przepływ netto w każdym węźle non-source non-zlewu musi być 0 (dla każdego u ∉ {s, t}, zsumowanie wszystkich w, sum f(u, w) = 0).
Wymagany przepływ : siatka wypływają źródła i przepływ netto do zlewu należy oba równe wymagany przepływ przez sieć (zsumowanie wszystkich u, sum f(s, u) = sum f(u, t) = d).

Biorąc pod uwagę sieć przepływu Gi wymagany przepływ d, określ minimalny koszt wysyłania djednostek przez sieć. Możesz założyć, że istnieje rozwiązanie. da wszystkie zdolności i koszty będą liczbami całkowitymi nieujemnymi. W przypadku sieci z Nwierzchołkami oznaczonymi jako wierzchołek [0, N-1]źródłowy będzie, 0a wierzchołek ujścia będzie N-1.

To jest golf-golf, więc wygrywa najkrótsza odpowiedź (w bajtach). Pamiętaj, że jest to konkurencja zarówno w językach, jak i między językami, więc nie bój się opublikować rozwiązania w pełnym języku.

Wbudowane są dozwolone, ale zachęcamy do uwzględnienia rozwiązań bez wbudowanych, jako dodatkowego rozwiązania w tej samej odpowiedzi lub jako niezależnej odpowiedzi.

Dane wejściowe mogą być w dowolny rozsądny sposób, który obejmuje zdolności i koszty każdej krawędzi oraz popyt.

Przypadki testowe

Przypadki testowe są dostarczane w następującym formacie:

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

Te przypadki testowe zostały obliczone za pomocą biblioteki NetworkX Python .

code-golf graph-theory optimization

— Mego
źródło

Piaskownica

— Mego

Grał w golfa przez długi czas, a potem zdał sobie sprawę, że grałem w zły algorytm, ponieważ nie umiem czytać

— Quintec

Odpowiedzi:

[R + lpSolve ], 201 186 149 144 bajtów

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

Wypróbuj online!

Kod konstruuje następujący problem liniowy i rozwiązuje go za pomocą lpSolvepakietu:

\begin{aligned} m i n & \sum_{\forall x \in V} \sum_{\forall y \in V} A_{x, y} \cdot f_{x, y} \\ s u b j e c t t o : \\ \sum_{x \in V} f_{v, x} - f_{x, v} = 0 & \forall v \in V : v \neq {s, t} \\ \sum_{x \in V} f_{s, x} - f_{x, s} = d \\ \sum_{x \in V} f_{t, x} - f_{x, t} = - d \\ f_{x, b} \leq C_{x, b} & \forall x \in V, \forall y \in V \end{aligned}

$\begin{align} min & \sum_{\forall x \in V}\ \sum_{\forall y \in V} A_{x,y} \cdot f_{x,y} \\ subject\ to : & \\ & \sum_{x \in V} f_{v,x} - f_{x,v} = 0 & \forall v \in V : v \neq \{s,t\} \\ & \sum_{x \in V} f_{s,x} - f_{x,s} = d \\ & \sum_{x \in V} f_{t,x} - f_{x,t} = -d \\ & f_{x,b} \leq C_{x,b} & \forall x \in V,\forall y \in V \end{align}$ gdzie:

$V$ jest zbiorem wierzchołków
$s$ jest wierzchołkiem źródłowym
$t$ s jest wierzchołkiem docelowym (lub tonącym)
$A_{x,y}$ to koszt przepływu dla krawędzix -> y
$f_{x,y}$ to przepływ krawędzi x -> yw optymalnym rozwiązaniu
$d$ jest wymaganym przepływem u ujścia (tj. popyt w chwili produkcja w chwili ) $t$ $s$
$C_{x,y}$ to maksymalna pojemność zboczax -> y

— digEmAll
źródło

Ładne, liniowe programowanie :) Niestety większość języków nie ma lpSolve... :(

— Quintec

To niestety prawda ... BTW nie jest dostępny na bazie R, to pakiet ... Musiałem poprosić o instalację na TIO;)

— digEmAll

Z jakiegoś powodu muszę jeszcze znaleźć krótki sposób na modyfikację MinCostMaxFlow, aby stał się MinCostFlow ... mój mózg jest usmażony, lol, chciałbym, aby była w tym funkcja w językach innych niż matematyka

— Quintec

@Quintec: czy masz na myśli konkretną implementację (np. W określonym języku) MinCostMaxFlow?

— digEmAll

Nie, mój ręcznie kodowany algorytm

— Quintec

Język Wolfram, 42 bajty

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

Trivial wbudowany. Niedostępne rozwiązanie już wkrótce.

— lirtosiast
źródło

Czy nadejdzie za 6-8 tygodni? : P

— Quintec,

Python 3 + NetworkX , 137 bajtów

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)

Brak łącza TryItOnline, ponieważ TIO nie ma zainstalowanej biblioteki NetworkX

Pobiera dane wejściowe wykresu jako listę krawędzi z atrybutami pojemności i wagi, takimi jak to:

[(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})]

To jest wersja kodu gry w golfa, której użyłem do weryfikacji przypadków testowych.

— Mego
źródło