Maksimum Akış ve Doğrusal Atama Problemi

İşte bir sorun: İşletmeniz sözleşmeleri yerine getirmek için müteahhitler atadı. Listelerinizi gözden geçiriyorsunuz ve bir aylık bir sözleşme için hangi müteahhitlerin müsait olduğuna karar veriyorsunuz ve hangilerinin bir aylık görevler için olduğunu görmek için mevcut sözleşmelerinize bakıyorsunuz. Her bir yüklenicinin her bir sözleşmeyi ne kadar etkili bir şekilde yerine getirebileceğini bildiğinize göre, o ay için genel etkinliği en üst düzeye çıkarmak için yüklenicileri nasıl atayabilirsiniz?

Bu atama problemine bir örnektir ve problem klasik Macar algoritması ile çözülebilir.

Macar algoritması (Kuhn-Munkres algoritması olarak da bilinir), ağırlıklı iki parçalı bir grafikte ağırlık eşleşmesini maksimize eden bir polinom zaman algoritmasıdır. Burada, müteahhitler ve sözleşmeler, müteahhit ve sözleşme düğümleri arasındaki kenarların ağırlıkları olarak etkinlikleriyle ikili bir grafik olarak modellenebilir.

Bu makalede, doğrusal atama problemini çözmek için Edmonds-Karp algoritmasını kullanan Macar algoritmasının bir uygulamasını öğreneceksiniz. Ayrıca Edmonds-Karp algoritmasının Ford-Fulkerson yönteminin küçük bir modifikasyonu olduğunu ve bu modifikasyonun ne kadar önemli olduğunu öğreneceksiniz.

Maksimum Akış Problemi

Maksimum akış sorununun kendisi, gayri resmi olarak, tek bir kaynaktan tek bir terminale bir boru ağından bir miktar sıvı veya gazın taşınması sorunu olarak tanımlanabilir. Bu, ağdaki basıncın, sıvı veya gazın herhangi bir uzunluktaki boru veya boru bağlantı parçasında (farklı boru uzunluklarının buluştuğu yerler) oyalanmamasını sağlamak için yeterli olduğu varsayımıyla yapılır.

Grafikte belirli değişiklikler yapılarak atama problemi maksimum akış problemine dönüştürülebilir.

ön elemeler

Bu problemleri çözmek için gereken fikirler birçok matematik ve mühendislik disiplininde ortaya çıkar, genellikle benzer kavramlar farklı isimlerle bilinir ve farklı şekillerde ifade edilir (örneğin, komşuluk matrisleri ve komşuluk listeleri). Bu fikirler oldukça ezoterik olduğundan, bu kavramların herhangi bir ortam için ne kadar genel olarak tanımlanacağına ilişkin seçimler yapılır.

Bu makale, küçük bir giriş kümesi teorisinin ötesinde herhangi bir ön bilgi kabul etmeyecektir.

Bu gönderideki uygulamalar, sorunları yönlendirilmiş grafikler (digraf) olarak temsil eder.

DiGraph'ler

Bir digrafın setOfNodes ve setOfArcs olmak üzere iki özelliği vardır. Bu niteliklerin her ikisi de kümelerdir (sırasız koleksiyonlar). Bu gönderideki kod bloklarında, aslında Python'un donmuş kümesini kullanıyorum, ancak bu ayrıntı özellikle önemli değil.

 DiGraph = namedtuple('DiGraph', ['setOfNodes','setOfArcs'])

(Not: Bu ve bu makaledeki diğer tüm kodlar Python 3.6'da yazılmıştır.)

düğümler

Bir düğüm n , iki öznitelikten oluşur:

• n.uid : Benzersiz bir tanımlayıcı.

  Bu, herhangi iki x ve y düğümü için,

 x.uid != y.uid

• n.datum : Bu, herhangi bir veri nesnesini temsil eder.

 Node = namedtuple('Node', ['uid','datum'])

yaylar

Bir ark a , üç öznitelikten oluşur:

• a.fromNode : Bu, yukarıda tanımlandığı gibi bir düğümdür .

• a.toNode : Bu, yukarıda tanımlandığı gibi bir düğümdür .

• a.datum : Bu, herhangi bir veri nesnesini temsil eder.

 Arc = namedtuple('Arc', ['fromNode','toNode','datum'])

Digraftaki yay seti, digraftaki düğümler üzerinde ikili bir ilişkiyi temsil eder. arc a öğesinin varlığı, a.fromNode ve a.toNode arasında bir ilişkinin var olduğu anlamına gelir.

Yönlendirilmiş bir grafikte (yönlendirilmemiş bir grafiğin aksine), a.toNode ve a.toNode arasında bir ilişkinin varlığı, a.fromNode ve a.toNode arasında benzer bir a.fromNode var olduğu anlamına gelmez .

Bunun nedeni, yönlendirilmemiş bir grafikte ifade edilen ilişkinin mutlaka simetrik olmamasıdır.

DiGraph'ler

Düğümler ve yaylar bir digrafı tanımlamak için kullanılabilir, ancak kolaylık sağlamak için aşağıdaki algoritmalarda bir digraf bir sözlük olarak temsil edilecektir.

Yukarıdaki grafik gösterimini buna benzer bir sözlük gösterimine dönüştürebilen bir yöntem:

 def digraph_to_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) pdg(G) raise KeyError(err_msg) G_as_dict[a.fromNode] = (G_as_dict[a.fromNode].union(frozenset([a]))) if (a.fromNode in G_as_dict) else frozenset([a]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = frozenset([]) return G_as_dict

Ve işte onu bir sözlük sözlüğüne dönüştüren başka bir işlem, faydalı olacak başka bir işlem:

 def digraph_to_double_dict(G): G_as_dict = dict([]) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.fromNode not in G_as_dict): G_as_dict[a.fromNode] = dict({a.toNode : frozenset([a])}) else: if(a.toNode not in G_as_dict[a.fromNode]): G_as_dict[a.fromNode][a.toNode] = frozenset([a]) else: G_as_dict[a.fromNode][a.toNode] = G_as_dict[a.fromNode][a.toNode].union(frozenset([a])) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if a.toNode not in G_as_dict: G_as_dict[a.toNode] = dict({}) return G_as_dict

Makale bir sözlük tarafından temsil edilen bir digraftan bahsettiğinde, buna atıfta bulunmak için G_as_dict bahsedecektir.

Bazen, uid kimliği (benzersiz tanımlayıcı) aracılığıyla bir G digrafından bir düğüm almak yardımcı olur:

 def find_node_by_uid(find_uid, G): nodes = {n for n in G.setOfNodes if n.uid == find_uid} if(len(nodes) != 1): err_msg = 'Node with uid {find_uid!s} is not unique.'.format(**locals()) raise KeyError(err_msg) return nodes.pop()

Grafikleri tanımlarken, insanlar bazen aynı kavrama atıfta bulunmak için düğüm ve köşe terimlerini kullanırlar; aynısı ark ve kenar terimleri için de geçerlidir.

Python'daki iki popüler grafik temsili, sözlükleri kullanan ve grafikleri temsil etmek için nesneleri kullanan bir grafik temsilidir. Bu gönderideki temsil, yaygın olarak kullanılan bu iki gösterim arasında bir yerdedir.

Bu benim digraf temsilim . Bunun gibisi çok ama bu benim.

Yürüyüşler ve Yollar

S_Arcs , bir G digrafındaki yayların sonlu bir dizisi (sıralı derleme) olsun, öyle ki a , S_Arcs hariç herhangi bir yay ise ve b dizide a takip ediyorsa, o zaman içinde bir düğüm n = a.fromNode . G.setOfNodes a.toNode = b.fromNode .

n ilk yaydan başlayarak ve S_Arcs son yaya kadar devam ederek, S_Arcs her iki ardışık yay arasında yukarıda tanımlandığı gibi tüm düğümleri (karşılaşılan sırayla) S_Arcs . Bu işlem sırasında toplanan sıralı düğüm koleksiyonunu etiketleyin S_{Nodes} .

 def path_arcs_to_nodes(s_arcs): s_nodes = list([]) arc_it = iter(s_arcs) step_count = 0 last = None try: at_end = False last = a1 = next(arc_it) while (not at_end): s_nodes += [a1.fromNode] last = a2 = next(arc_it) step_count += 1 if(a1.toNode != a2.fromNode): err_msg = "Error at index {step_count!s} of Arc sequence.".format(**locals()) raise ValueError(err_msg) a1 = a2 except StopIteration as e: at_end = True if(last is not None): s_nodes += [last.toNode] return s_nodes

• Herhangi bir düğüm S_Nodes dizisinde birden fazla kez görünüyorsa, S_Arcs'ı G S_Arcs Yürüyüş olarak adlandırın.

• Aksi takdirde, S_Arcs G digraph üzerinde list(S_Nodes)[0] 'dan list(S_Nodes)[-1] 'e bir yol çağırın.

Kaynak Düğümü

Çağrı düğümü , s , G.setOfNodes ve G.setOfArcs , a.toNode = s s şekilde hiçbir yay içermiyorsa, G digrafındaki a kaynak düğümü çağırın.

 def source_nodes(G): to_nodes = frozenset({a.toNode for a in G.setOfArcs}) sources = G.setOfNodes.difference(to_nodes) return sources

Terminal Düğümü

Eğer t , G.setOfNodes ve G.setOfArcs , a.fromNode = t olacak şekilde hiçbir yay içermiyorsa, t düğümünü G digrafında a terminal düğümü olarak adlandırın.

 def terminal_nodes(G): from_nodes = frozenset({a.fromNode for a in G.setOfArcs}) terminals = G.setOfNodes.difference(from_nodes) return terminals

Kesikler ve Kesikler

Bağlı bir G digrafının kesme cut , G.setOfNodes düğüm kümesini G G.setOfArcs gelen yayların bir alt kümesidir. G her n düğümü ve G.setOfNodes en az bir ark a sahipse, G, n = a.fromNode G.setOfArcs n = a.toNode , ancak a.fromNode != a.toNode .

 Cut = namedtuple('Cut', ['setOfCutArcs'])

Yukarıdaki tanım, yayların bir alt kümesine atıfta bulunur, ancak G.setOfNodes düğümlerinin bir bölümünü de tanımlayabilir.

predecessors_of ve successors_of işlevleri için, n , G digrafının G.setOfNodes kümesindeki bir düğümdür ve cut , G öğesinin bir kesimidir :

 def cut_predecessors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) predecessors = frozenset({}) previous_count = len(predecessors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.fromNode for a in allowed_arcs if (a.toNode in reach_fringe)}) reach_fringe = reachable_from predecessors = predecessors.union(reach_fringe) current_count = len(predecessors) keep_going = current_count - previous_count > 0 previous_count = current_count return predecessors def cut_successors_of(n, cut, G): allowed_arcs = G.setOfArcs.difference(frozenset(cut.setOfCutArcs)) successors = frozenset({}) previous_count = len(successors) reach_fringe = frozenset({n}) keep_going = True while( keep_going ): reachable_from = frozenset({a.toNode for a in allowed_arcs if (a.fromNode in reach_fringe)}) reach_fringe = reachable_from successors = successors.union(reach_fringe) current_count = len(successors) keep_going = current_count - previous_count > 0 previous_count = current_count return successors

Kesim , G digrafının bir cut olsun.

 def get_first_part(cut, G): firstPartFringe = frozenset({a.fromNode for a in cut.setOfCutArcs}) firstPart = firstPartFringe for n in firstPart: preds = cut_predecessors_of(n,cut,G) firstPart = firstPart.union(preds) return firstPart def get_second_part(cut, G): secondPartFringe = frozenset({a.toNode for a in cut.setOfCutArcs}) secondPart = secondPartFringe for n in secondPart: succs= cut_successors_of(n,cut,G) secondPart = secondPart.union(succs) return secondPart

cut , G digrafının bir kesimidir eğer: (get_first_part( cut (get_first_part(cut, G).union(get_second_part(cut, G)) == G.setOfNodes) and (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0) cut , (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) de xy cut olarak adlandırılır. Bir xy kesim cut x düğümü bir kaynak düğüm ve xy kesimdeki y düğümü bir terminal düğüm olduğunda, bu kesime st kesim denir.

 STCut = namedtuple('STCut', ['s','t','cut'])

Akış Ağları

Bir akış ağını temsil etmek için bir G digrafı kullanabilirsiniz.

Her düğüme n atayın, burada n , G.setOfNodes ve bir n.datum olan bir FlowNodeDatum :

 FlowNodeDatum = namedtuple('FlowNodeDatum', ['flowIn','flowOut'])

Her yaya a , burada a G.setOfArcs ve a.datum bir FlowArcDatum .

 FlowArcDatum = namedtuple('FlowArcDatum', ['capacity','flow'])

flowNodeDatum.flowIn ve flowNodeDatum.flowOut pozitif gerçek sayılardır.

flowArcDatum.capacity ve flowArcDatum.flow da pozitif gerçek sayılardır.

G.setOfNodes içindeki her düğüm düğümü n için:

 n.datum.flowIn = sum({a.datum.flow for a in G.Arcs if a.toNode == n}) n.datum.flowOut = sum({a.datum.flow for a in G.Arcs if a.fromNode == n})

Digraf G artık bir akış ağını temsil etmektedir.

G akışı , G tüm a yayları a.flow a . akışını ifade eder.

Uygulanabilir Akışlar

Digraf G bir akış ağını temsil etsin.

G ile temsil edilen akış ağı , aşağıdaki durumlarda uygun akışlara sahiptir:

1. Kaynak düğümler ve uçbirim düğümleri dışında G.setOfNodes içindeki her n düğümü için: n.datum.flowIn = n.datum.flowOut .

2. G.setOfNodes içindeki her ark a : G.setOfNodes a.datum.capacity <= a.datum.flow .

Koşul 1, koruma kısıtlaması olarak adlandırılır.

Durum 2, kapasite kısıtlaması olarak adlandırılır.

Kesim Kapasitesi

G digrafı ile temsil edilen bir akış ağının kaynak düğümü s ve terminal düğümü t olan bir st cut stCut kesme kapasitesi :

 def cut_capacity(stCut, G): part_1 = get_first_part(stCut.cut,G) part_2 = get_second_part(stCut.cut,G) s_part = part_1 if stCut.s in part_1 else part_2 t_part = part_1 if stCut.t in part_1 else part_2 cut_capacity = sum({a.datum.capacity for a in stCut.cut.setOfCutArcs if ( (a.fromNode in s_part) and (a.toNode in t_part) )}) return cut_capacity

Minimum Kapasite Kesimi

stCut = stCut(s,t,cut) bir G digrafı ile temsil edilen bir akış ağının st kesimi olsun.

stCut , bu akış ağında başka bir st cut stCutCompetitor yoksa, G tarafından temsil edilen akış ağının minimum kapasite kesintisidir :

 cut_capacity(stCut, G) < cut_capacity(stCutCompetitor, G)

Akışları Uzaklaştırmak

Bir G digrafı almanın ve G.setOfNodes içindeki tüm düğümlerden ve ayrıca G.setOfNodes içindeki tüm yaylardan gelen tüm akış verilerini çıkarmanın sonucu olacak digrafa atıfta bulunmak G.setOfArcs .

 def strip_flows(G): new_nodes= frozenset( (Node(n.uid, FlowNodeDatum(0.0,0.0)) for n in G.setOfNodes) ) new_arcs = frozenset([]) for a in G.setOfArcs: new_fromNode = Node(a.fromNode.uid, FlowNodeDatum(0.0,0.0)) new_toNode = Node(a.toNode.uid, FlowNodeDatum(0.0,0.0)) new_arc = Arc(new_fromNode, new_toNode, FlowArcDatum(a.datum.capacity, 0.0)) new_arcs = new_arcs.union(frozenset([new_arc])) return DiGraph(new_nodes, new_arcs)

Maksimum Akış Problemi

G digrafı G , G.setOfNodes içinde bir kaynak düğüm s ve G.setOfNodes , G içinde bir terminal düğümü t olarak temsil edilen bir akış ağı , aşağıdaki durumlarda bir maksimum akış problemini temsil edebilir:

 (len(list(source_nodes(G))) == 1) and (next(iter(source_nodes(G))) == s) and (len(list(terminal_nodes(G))) == 1) and (next(iter(terminal_nodes(G))) == t)

Bu temsili etiketleyin:

 MaxFlowProblemState = namedtuple('MaxFlowProblemState', ['G','sourceNodeUid','terminalNodeUid','maxFlowProblemStateUid'])

Burada sourceNodeUid = s.uid , terminalNodeUid = t.uid ve maxFlowProblemStateUid sorun örneği için bir tanımlayıcıdır.

Maksimum Akış Çözümü

maxFlowProblem bir maksimum akış problemini temsil etmesine izin verin. maxFlowProblem çözümü, digraf H olarak temsil edilen bir akış ağı ile temsil edilebilir.

Digraf H , aşağıdaki durumlarda python maxFlowProblem girişindeki maksimum akış sorununa uygulanabilir bir çözümdür:

1. strip_flows(maxFlowProblem.G) == strip_flows(H) .

2. H bir akış ağıdır ve uygun akışlara sahiptir.

1 ve 2'ye ek olarak:

1. strip_flows(G) == strip_flows(K) ve find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn K edilen başka bir akış ağı olamaz.

O zaman H ayrıca maxFlowProblem için en uygun çözümdür.

Başka bir deyişle, uygulanabilir bir maksimum akış çözümü , aşağıdaki gibi bir digraf ile temsil edilebilir:

1. Herhangi bir düğüm ve arkın n.datum.flowIn , n.datum.flowOut ve a.datum.flow değerlerinin farklı olabilmesi dışında, ilgili maksimum akış probleminin digrafı G ile aynıdır.

2. Uygulanabilir akışları olan bir akış ağını temsil eder.

Ayrıca, aşağıdaki durumlarda optimal bir maksimum akış çözümünü temsil edebilir:

1. Maksimum akış probleminde uç düğüme karşılık gelen düğüm için flowIn mümkün olduğu kadar büyüktür (1 ve 2. koşullar hala sağlandığında).

H digrafı uygun bir maksimum akış çözümünü temsil ediyorsa: find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn , maksimum akış, minimum kesme teoreminden gelir (aşağıda tartışılmıştır). Gayri resmi olarak, H uygulanabilir akışlara sahip olduğu varsayıldığından, bu, herhangi bir (diğer) düğümü geçerken ( koruma kısıtlamaları ) akışın ne "yaratılamayacağı" ( kaynak düğüm s dışında) ne de "yok edilemeyeceği" ( terminal düğüm t hariç) anlamına gelir.

Maksimum akış problemi yalnızca tek bir kaynak düğümü s ve tek bir uç düğümü t içerdiğinden, s 'yaratılan' tüm akış t'de 'yok edilmelidir t veya akış ağının uygulanabilir akışları yok ( koruma kısıtlaması ihlal edilmiş olurdu) ).

H digrafı uygun bir maksimum akış çözümünü temsil etsin; yukarıdaki değere H st Akış Değeri denir.

İzin vermek:

 mfps=MaxFlowProblemState(H, maxFlowProblem.sourceNodeUid, maxFlowProblem.terminalNodeUid, maxFlowProblem.maxFlowProblemStateUid)

Bu, maxFlowProblem mfps ardıl durumu olduğu anlamına gelir; bu, mfps tam olarak maxFlowProblem'e benzediği anlamına gelir; ancak, maxFlowProblem içindeki arklar a a.flow değerlerinin, a.flow arklar a maxFlowProblem.setOfArcs farklı olabileceği dışında mfps.setOfArcs .

 def get_mfps_flow(mfps): flow_from_s = find_node_by_uid(mfps.sourceNodeUid,mfps.G).datum.flowOut flow_to_t = find_node_by_uid(mfps.terminalNodeUid,mfps.G).datum.flowIn if( (flow_to_t - flow_from_s) > 0): raise Exception('Infeasible st flow') return flow_to_t

İşte ilişkili maxFlowProb ile birlikte bir mfps görselleştirmesi. Görüntüdeki her ark a bir etiketi vardır, bu etiketler a.datum.flowFrom / a.datum.flowTo , görüntüdeki her n düğümünün bir etiketi vardır ve bu etiketler n.uid {n.datum.flowIn / a.datum.flowOut} .

st Kesme Akışı

mfps'nin bir mfps temsil MaxFlowProblemState ve stCut bir kesimini temsil etmesine izin mfps.G . stCut kesme akışı tanımlanır:

 def get_stcut_flow(stCut,mfps): s = find_node_by_uid(mfps.sourceNodeUid, mfps.G) t = find_node_by_uid(mfps.terminalNodeUid, mfps.G) part_1 = get_first_part(stCut.cut,mfps.G) part_2 = get_second_part(stCut.cut,mfps.G) s_part = part_1 if s in part_1 else part_2 t_part = part_1 if t in part_1 else part_2 s_t_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in s_part) ) t_s_sum = sum(a.datum.flow for a in mfps.G.setOfArcs if (a in stCut.cut.setOfCutArcs) and (a.fromNode in t_part) ) cut_flow = s_t_sum - t_s_sum return cut_flow

st kesme akışı , kaynak düğümü içeren bölümden terminal düğümü içeren bölüme olan akışların toplamı eksi terminal düğümünü içeren bölümden kaynak düğümü içeren bölüme olan akışların toplamıdır.

Maksimum Akış, Min Kesim

maxFlowProblem bir maksimum akış problemini temsil etsin ve maxFlowProblem çözümünün H maxFlowProblem ile temsil edilen bir akış ağı ile temsil edilmesine izin verin.

minStCut, minStCut ile temsil edilen akış ağının minimum kapasite kesintisi maxFlowProblem.G .

Maksimum akış probleminde akış yalnızca tek bir kaynak düğümde başladığı ve tek bir uç düğümde sona erdiği için ve kapasite kısıtlamaları ve koruma kısıtlamaları nedeniyle, maxFlowProblem.terminalNodeUid giren tüm akışın herhangi bir st kesimini geçmesi gerektiğini biliyoruz. özellikle minStCut . Bu şu anlama gelir:

 get_flow_value(H, maxFlowProblem) <= cut_capacity(minStCut, maxFlowProblem.G)

Maksimum Akış Problemini Çözme

maxFlowProblem maksimum akış problemini çözmenin temel fikri, digraf H ile temsil edilen maksimum akış çözümü ile başlamaktır. Böyle bir başlangıç ​​noktası H = strip_flows(maxFlowProblem.G) olabilir. O zaman görev, H kullanmak ve H.setOfArcs'taki bazı arkların a.datum.flow değerlerinin açgözlü a şekilde değiştirilmesiyle, K H.setOfArcs ile temsil edilen başka bir maksimum akış çözümü üretmektir, öyle ki K hala uygun akışlara sahip bir akış ağını temsil edemez. ve get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Bu süreç devam ettiği sürece, en son karşılaşılan maksimum akış çözümünün ( K ) kalitesi ( get_flow_value(K, maxFlowProblem) ) bulunan diğer maksimum akış çözümlerinden daha iyidir. Süreç, başka hiçbir iyileştirmenin mümkün olmadığını bildiği bir noktaya ulaşırsa, süreç sona erebilir ve optimal maksimum akış çözümünü döndürür.

Yukarıdaki açıklama geneldir ve böyle bir işlemin mümkün olup olmadığı veya ne kadar sürebileceği gibi birçok kanıtı atlar, birkaç detay ve algoritma daha vereceğim.

Maksimum Akış, Min Kesim Teoremi

Ford ve Fulkerson tarafından yazılan Ağlarda Akışlar kitabından, maksimum akış, minimum kesme teoreminin ifadesi (Teorem 5.1):

Herhangi bir ağ için, s'den t maksimum akış değeri, s ve t ayıran s kesimlerin minimum kesim kapasitesine eşittir.

Bu gönderideki tanımları kullanarak, şu anlama gelir:

H digrafı olarak temsil edilen bir akış ağı tarafından temsil edilen bir maxFlowProblem çözümü, aşağıdaki durumlarda optimaldir:

 get_flow_value(H, maxFlowProblem) == cut_capacity(minStCut, maxFlowProblem.G)

Teoremin bu kanıtını beğendim ve Wikipedia'da bir tane daha var.

Maksimum akış, minimum kesim teoremi , Ford-Fulkerson yönteminin doğruluğunu ve eksiksizliğini kanıtlamak için kullanılır.

Ayrıca yolları artırdıktan sonraki bölümde teoremin bir kanıtını vereceğim.

Ford-Fulkerson Metodu ve Edmonds-Karp Algoritması

CLRS, Ford-Fulkerson yöntemini şu şekilde tanımlar (bölüm 26.2):

 FORD-FULKERSON-METHOD(G, s, t): initialize flow f to 0 while there exists an augmenting path p in the residual graph G_f augment flow f along

Artık Grafik

G digrafı olarak temsil edilen bir akış ağının Artık Grafiği, G_f G_f olarak temsil edilebilir:

 ResidualDatum = namedtuple('ResidualDatum', ['residualCapacity','action']) def agg_n_to_u_cap(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.capacity for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def agg_n_to_u_flow(n,u,G_as_dict): arcs_out = G_as_dict[n] return sum([a.datum.flow for a in arcs_out if( (a.fromNode == n) and (a.toNode == u) ) ]) def get_residual_graph_of(G): G_as_dict = digraph_to_dict(G) residual_nodes = G.setOfNodes residual_arcs = frozenset([]) for n in G_as_dict: arcs_from = G_as_dict[n] nodes_to = frozenset([find_node_by_uid(a.toNode.uid,G) for a in arcs_from]) for u in nodes_to: n_to_u_cap_sum = agg_n_to_u_cap(n,u,G_as_dict) n_to_u_flow_sum = agg_n_to_u_flow(n,u,G_as_dict) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(n,u,datum=ResidualDatum(flow, 'push'))]) ) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) residual_arcs = residual_arcs.union( frozenset([Arc(u,n,datum=ResidualDatum(flow, 'pull'))]) ) return DiGraph(residual_nodes, residual_arcs)

• agg_n_to_u_cap(n,u,G_as_dict) G.setOfArcs kümesindeki tüm yaylar için a.datum.capacity toplamını döndürür; burada ark a , a.fromNode = n ve a.toNode = u ise alt kümededir.

• agg_n_to_u_cap(n,u,G_as_dict) G.setOfArcs kümesindeki tüm yaylar için a.datum.flow toplamını döndürür; burada ark a , a.fromNode = n ve a.toNode = u ise alt kümededir.

Kısaca, G_f artık grafiği , G G_f üzerinde gerçekleştirilebilecek belirli eylemleri temsil etmektedir.

G digrafı ile temsil edilen akış ağının G.setOfNodes içindeki her bir n,u düğüm çifti, G G_f artık grafiğinde 0, 1 veya 2 yay G_f .

1. G.setOfArcs a.fromNode = n ve a.toNode = u şekilde a ark yoksa n,u çifti G_f herhangi bir yay oluşturmaz.

2. n,u çifti G_f.setOfArcs içinde a arkını oluşturur, burada a , n u bir itme akış yayını olarak etiketlenmiş bir yayı temsil eder a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) eğer n_to_u_cap_sum > n_to_u_flow_sum

3. n,u çifti, n_to_u_flow_sum > 0.0 ise, G_f.setOfArcs a arkını oluşturur; burada a , n u bir çekme akış yayını olarak etiketlenmiş bir yayı temsil eder a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) .

• G_f.setOfArcs içindeki her itme akışı yayı , a.fromNode = n ve a.toNode = u ise ark a alt kümede olduğu G.setOfArcs alt kümesindeki yaylara toplam x <= n_to_u_cap_sum - n_to_u_flow_sum akışı ekleme eylemini temsil eder. a.toNode = u .

• G_f.setOfArcs içindeki her çekme akışı yayı , a.fromNode = n ve a.toNode = u ise ark a alt kümede olduğu G.setOfArcs alt kümesindeki yaylara toplam x <= n_to_u_flow_sum akışı çıkarma eylemini temsil eder.

G uygulanabilir yaylar üzerinde G_f bireysel bir itme veya çekme eylemi gerçekleştirmek, kapasite kısıtlamaları veya koruma kısıtlamaları oluşturulan akış ağında ihlal edilmiş olabileceğinden, uygulanabilir akışlar olmadan bir akış ağı oluşturabilir.

Bir maksimum akış çözümünün önceki örnek görselleştirmesinin kalıntı grafiğinin görselleştirmesi burada, görselleştirmede her ark a , a.residualCapacity temsil eder.

Büyütme Yolu

maxFlowProblem bir maksimum akış problemi olsun ve G_f = get_residual_graph_of(G) maxFlowProblem.G grafiği olsun.

augmentingPath için maxFlowProblem yolu artırma yolu , find_node_by_uid(maxFlowProblem.sourceNode,G_f) ile find_node_by_uid(maxFlowProblem.terminalNode,G_f) arasındaki herhangi bir yoldur.

Artan bir yol augmentingPath , digraf H tarafından temsil edilen bir maksimum akış çözümüne uygulanabileceği ve H digrafı ile temsil edilen başka bir maksimum akış çözümü üretilebileceği ortaya çıktı; burada, H optimal değilse get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) ) K

İşte nasıl:

 def augment(augmentingPath, H): augmentingPath = list(augmentingPath) H_as_dict = digraph_to_dict(H) new_nodes = frozenset({}) new_arcs = frozenset({}) visited_nodes = frozenset({}) visited_arcs = frozenset({}) bottleneck_residualCapacity = min( augmentingPath, key=lambda a: a.datum.residualCapacity ).datum.residualCapacity for x in augmentingPath: from_node_uid = x.fromNode.uid if x.datum.action == 'push' else x.toNode.uid to_node_uid = x.toNode.uid if x.datum.action == 'push' else x.fromNode.uid from_node = find_node_by_uid( from_node_uid, H ) to_node = find_node_by_uid( to_node_uid, H ) load = bottleneck_residualCapacity if x.datum.action == 'push' else -bottleneck_residualCapacity for a in H_as_dict[from_node]: if(a.toNode == to_node): test_sum = a.datum.flow + load new_flow = a.datum.flow new_from_node_flow_out = a.fromNode.datum.flowOut new_to_node_flow_in = a.toNode.datum.flowIn new_from_look = {n for n in new_nodes if (n.uid == a.fromNode.uid)} new_to_look = {n for n in new_nodes if (n.uid == a.toNode.uid) } prev_from_node = new_from_look.pop() if (len(new_from_look)>0) else a.fromNode prev_to_node = new_to_look.pop() if (len(new_to_look)>0) else a.toNode new_nodes = new_nodes.difference(frozenset({prev_from_node})) new_nodes = new_nodes.difference(frozenset({prev_to_node})) if(test_sum > a.datum.capacity): new_flow = a.datum.capacity new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + a.datum.capacity new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + a.datum.capacity load = test_sum - a.datum.capacity elif(test_sum < 0.0): new_flow = 0.0 new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow load = test_sum else: new_flow = test_sum new_from_node_flow_out = prev_from_node.datum.flowOut - a.datum.flow + new_flow new_to_node_flow_in = prev_to_node.datum.flowIn - a.datum.flow + new_flow load = 0.0 new_from_node_flow_out = round(new_from_node_flow_out, TOL) new_to_node_flow_in = round(new_to_node_flow_in, TOL) new_flow = round(new_flow, TOL) new_from_node = Node(prev_from_node.uid, FlowNodeDatum(prev_from_node.datum.flowIn, new_from_node_flow_out)) new_to_node = Node(prev_to_node.uid, FlowNodeDatum(new_to_node_flow_in, prev_to_node.datum.flowOut)) new_arc = Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, new_flow)) visited_nodes = visited_nodes.union(frozenset({a.fromNode,a.toNode})) visited_arcs = visited_arcs.union(frozenset({a})) new_nodes = new_nodes.union(frozenset({new_from_node, new_to_node})) new_arcs = new_arcs.union(frozenset({new_arc})) not_visited_nodes = H.setOfNodes.difference(visited_nodes) not_visited_arcs = H.setOfArcs.difference(visited_arcs) full_new_nodes = new_nodes.union(not_visited_nodes) full_new_arcs = new_arcs.union(not_visited_arcs) G = DiGraph(full_new_nodes, full_new_arcs) full_new_arcs_update = frozenset([]) for a in full_new_arcs: new_from_node = a.fromNode new_to_node = a.toNode new_from_node = find_node_by_uid( a.fromNode.uid, G ) new_to_node = find_node_by_uid( a.toNode.uid, G ) full_new_arcs_update = full_new_arcs_update.union( {Arc(new_from_node, new_to_node, FlowArcDatum(a.datum.capacity, a.datum.flow))} ) G = DiGraph(full_new_nodes, full_new_arcs_update) return G

Yukarıda TOL , ağdaki akış değerlerinin yuvarlanması için bir miktar tolerans değeridir. Bu, kayan nokta hesaplamalarının basamaklı belirsizliğini önlemek içindir. Örneğin, 10 anlamlı basamağa yuvarlamak için TOL = 10 kullandım.

K = augment(augmentingPath, H) olsun, o zaman K maxFlowProblem için uygun bir maksimum akış çözümünü temsil eder. İfadenin doğru olması için, K ile temsil edilen akış ağının uygun akışlara sahip olması gerekir ( kapasite kısıtlamasını veya koruma kısıtlamasını ihlal etmemelidir.

İşte nedeni: Yukarıdaki yöntemde, K digrafı ile temsil edilen yeni akış ağına eklenen her bir düğüm , ya H digrafındaki bir düğümün tam bir kopyasıdır ya da n.datum.flowIn şu şekilde eklenmiş bir düğüm n . n.datum.flowOut . Bu, H sağlandığı sürece koruma kısıtlamasının K karşılandığı anlamına gelir. Koruma kısıtlaması sağlanır çünkü ağdaki herhangi bir yeni ark a a.datum.flow <= a.datum.capacity ; bu nedenle, değiştirilmeden K.setOfArcs kopyalanan H.setOfArcs kümesinden gelen yaylar kapasite kısıtlamasını ihlal etmediği sürece, K kapasite kısıtlamasını ihlal etmez.

H optimal değilse get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) olduğu da doğrudur.

İşte nedeni: Bir maks akış probleminin G_f kalıntı grafiğinin digraf temsilinde bir artırma yolu artırma yolu için mevcut olması için augmentingPath , o zaman maxFlowProblem üzerindeki son yay a 'itme' yayı olmalı ve augmentingPath a.toNode == maxFlowProblem.terminalNode . Bir artırma yolu , bir artırma yolu olduğu maksimum akış probleminin uç düğümünde sona eren yol olarak tanımlanır. Kalıntı grafiğinin tanımından, bu kalıntı grafiğindeki bir artırma yolundaki son yayın bir "itme" yayı olması gerektiği açıktır, çünkü artırma yolundaki herhangi bir "çekme" yayı b , b.toNode == maxFlowProblem.terminalNode yol tanımından b.toNode == maxFlowProblem.terminalNode ve b.fromNode != maxFlowProblem.terminalNode . Ek olarak, path tanımından, uçbirim düğümünün augment yöntemiyle yalnızca bir kez değiştirildiği açıktır. Bu nedenle artırma, augment tam olarak bir kez değiştirir ve maxFlowProblem.terminalNode.flowIn değerini artırır, çünkü artırma maxFlowProblem.terminalNode.flowIn son yay augment maxFlowProblem.terminalNode.flowIn augmentingPath neden olan yay olmalıdır. 'İtme' yayları için geçerli olan maxFlowProblem.terminalNode.flowIn augment artırılabilir, azaltılamaz.

Sedgewick ve Wayne'den Bazı Kanıtlar

Robert Sedgewich ve Kevin Wayne tarafından yazılan Algoritmalar kitabının dördüncü baskısı yararlı olacak bazı harika ve kısa kanıtlara (sayfa 892-894) sahiptir. Onları burada yeniden oluşturacağım, ancak önceki tanımlara uygun bir dil kullanacağım. Kanıtlar için etiketlerim Sedgewick kitabındakiyle aynı.

Önerme E: Bir maksimum akış problemine uygulanabilir bir maksimum akış çözümünü temsil eden herhangi bir H digrafı için maxFlowProblem , herhangi bir stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Kanıt: Let stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Önerme E , stCut için doğrudan st akış değeri tanımından geçerlidir. Orada bazı n düğümlerini s-bölümünden ( get_first_part(stCut.cut, G) ) ve t-bölümüne (get_second_part(stCut.cut, G)) taşımak istediğimizi varsayalım, bunu yapmak için stCut.cut değiştirmemiz gerekiyor. stCut.cut , stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) değiştirebilir ve E önermesini geçersiz kılabilir. Ancak biz bu değişikliği yaparken stcut_flow değerinin nasıl değişeceğini görelim. n düğümü dengededir, yani n düğümüne gelen akışın toplamı, ondan çıkan akışın toplamına eşittir (bu, H uygun bir çözümü temsil etmesi için gereklidir). n düğümüne giren stcut_flow parçası olan tüm akışın ona s-bölümünden girdiğine dikkat edin (t-bölümünden n düğümüne doğrudan veya dolaylı olarak giren akış, yanlış yöne gittiği için stcut_flow değerinde sayılmazdı) tanımına göre). Ek olarak, n çıkan tüm akış sonunda (doğrudan veya dolaylı olarak) uç düğüme akacaktır (daha önce kanıtlanmıştır). n düğümünü t-bölümüne taşıdığımızda, s-bölümünden n giren tüm akış, yeni stcut_flow değerine eklenmelidir; ancak, n çıkan tüm akış, yeni stcut_flow değerinden çıkarılmalıdır; akışın doğrudan t-bölümüne giden kısmı çıkarılır çünkü bu akış artık yeni t-bölümünün içindedir ve stcut_flow olarak sayılmaz. n yönündeki akışın s-bölümündeki düğümlere giden kısmı da stcut_flow çıkarılmalıdır: n , t-bölümüne taşındıktan sonra, bu akışlar t-bölümünden ve s-bölümüne yönlendirilecektir ve böylece stcut_flow içinde hesaba katılmamalıdır, çünkü bu akışlar s-bölümüne giren akış kaldırılır ve bu akışların toplamı ile ve s-bölümünden t-bölümüne olan çıkış (tüm akışların st bitmeli) aynı miktarda azaltılmalıdır. n düğümü işlemden önce dengede olduğundan, güncelleme çıkarıldığı gibi yeni stcut_flow değerine aynı değeri ekleyecek ve böylece güncellemeden sonra E önermesini doğru bırakacaktır. E önermesinin geçerliliği, t-bölümünün boyutuna ilişkin tümevarımdan sonra gelir.

E önermesinin geçerli olduğu daha az belirgin olan durumları görselleştirmeye yardımcı olacak bazı örnek akış ağları ; resimde, kırmızı alanlar s-bölümünü, mavi alanlar t-bölümünü ve yeşil yaylar bir st kesimini gösterir. İkinci görüntüde, A düğümü ile B düğümü arasındaki akış artarken, t terminal düğümüne akış değişmez.:

Sonuç: Hiçbir st cut akış değeri, herhangi bir st cut'ın kapasitesini aşamaz.

Önerme F. (maksimum akış, minimum kesme teoremi): f bir st akış olsun. Aşağıdaki 3 koşul eşdeğerdir:

1. Kapasitesi f akışının değerine eşit olan bir st kesim var.

2. f bir maksimum akıştır .

3. f göre artırma yolu yoktur.

Koşul 1, doğal olarak koşul 2'yi ifade eder. Koşul 2, koşul 3'ü ima eder, çünkü artan bir yolun varlığı, f maksimumluğuyla çelişen daha büyük değerlere sahip bir akışın varlığını ima eder. Koşul 3, koşul 1'i ifade eder: C_s , artık grafikte artan bir yolla s ulaşılabilen tüm düğümlerin kümesi olsun. Kalan yaylar C_t olsun, o zaman t C_t olmalıdır (varsayımımıza göre). C_s C_t yaylar a sonra sadece a.datum.capacity = a.datum.flow veya a.datum.flow = 0.0 olan yayları içeren bir st kesim oluşturur. Eğer bu başka türlü olsaydı, o zaman s böyle bir düğüme artan bir yol olacağından, C_s kalan artık kapasiteye sahip bir yay ile bağlanan düğümler C_s kümesinde olacaktır. st kesim boyunca akış, st kesimin kapasitesine eşittir (çünkü C_t C_s kadar olan yaylar kapasiteye eşit akışa sahiptir) ve ayrıca st akışının değerine ( önerme E ile).

Maksimum akış, minimum kesme teoreminin bu ifadesi, Ağlarda Akışlar'dan önceki ifadeyi ima eder.

Sonuç (bütünlük özelliği): Kapasiteler tamsayı olduğunda, tamsayı değerli bir maksimum akış vardır ve Ford-Fulkerson algoritması onu bulur.

Kanıt: Her artırma yolu , akışı pozitif bir tamsayı, "itme" yaylarındaki kullanılmayan kapasitelerin minimumu ve "çekme" yaylarındaki akışlar kadar artırır, bunların tümü her zaman pozitif tam sayılardır.

Bu, CLRS'den Ford-Fulkerson yöntemi açıklamasını doğrular. Yöntem, artırma yolları ortadan kalkıncaya kadar, en son maksimum akış çözümünün optimal olduğu anlamına gelene kadar, artırma yollarını bulmaya ve daha iyi çözümlerle gelen en son maxFlowSolution augment uygulamaya devam etmektir.

Ford-Fulkerson'dan Edmonds-Karp'a

Maksimum akış problemlerinin çözümüne ilişkin kalan sorular şunlardır:

1. Artan yollar nasıl inşa edilmelidir?

2. Tamsayılar değil de gerçek sayılar kullanırsak yöntem sona erecek mi?

3. Sonlandırılması ne kadar sürer (varsa)?

Edmonds-Karp algoritması , her artırma yolunun , artık grafiğin bir genişlik ilk araması (BFS) tarafından oluşturulduğunu belirtir; Yukarıdaki 1. noktadaki bu kararın aynı zamanda algoritmayı sona erdirmeye (2. nokta) zorlayacağı ve asimptotik zaman ve uzay karmaşıklığının belirlenmesine izin vereceği ortaya çıkıyor.

İlk olarak, işte bir BFS uygulaması:

 def bfs(sourceNode, terminalNode, G_f): G_f_as_dict = digraph_to_dict(G_f) parent_arcs = dict([]) visited = frozenset([]) deq = deque([sourceNode]) while len(deq) > 0: curr = deq.popleft() if curr == terminalNode: break for a in G_f_as_dict.get(curr): if (a.toNode not in visited): visited = visited.union(frozenset([a.toNode])) parent_arcs[a.toNode] = a deq.extend([a.toNode]) path = list([]) curr = terminalNode while(curr != sourceNode): if (curr not in parent_arcs): err_msg = 'No augmenting path from {} to {}.'.format(sourceNode.uid, terminalNode.uid) raise StopIteration(err_msg) path.extend([parent_arcs[curr]]) curr = parent_arcs[curr].fromNode path.reverse() test = deque([path[0].fromNode]) for a in path: if(test[-1] != a.fromNode): err_msg = 'Bad path: {}'.format(path) raise ValueError(err_msg) test.extend([a.toNode]) return path

Python koleksiyonları modülünden bir deque kullandım.

Yukarıdaki 2. soruyu yanıtlamak için, Sedgewick ve Wayne'den başka bir kanıt vereceğim: Önerme G. N düğümlü ve A yaylı Edmonds-Karp algoritmasında ihtiyaç duyulan artırma yollarının sayısı en fazla NA/2 . Kanıt: Her artırma yolunun bir darboğaz yayı vardır - ya kapasiteye kadar doldurulan bir "itme" yaya ya da içinden akışın 0 olduğu bir "çekme" yaya karşılık geldiği için artık grafikten silinen bir yay . ark bir darboğaz yayı haline gelir, içinden geçen herhangi bir artırma yolunun uzunluğu 2 kat artmalıdır. Bunun nedeni, yollar farklı olduğundan bir yoldaki her düğümün ( path tanımından) yalnızca bir kez görünebilmesi veya hiç görünmeyebilmesidir. en kısa yoldan en uzuna doğru araştırılırsa bu, belirli bir darboğaz düğümünden geçen bir sonraki yol tarafından en az bir düğümün daha ziyaret edilmesi gerektiği anlamına gelir, bu da biz düğüme varmadan önce yolda ek 2 yay anlamına gelir. Arttırma yolu en fazla N uzunluğunda olduğundan, her bir yay en fazla N/2 artırma yolunda olabilir ve artırma yollarının toplam sayısı en fazla NA/2 .

Edmonds-Karp algoritması O(NA^2) içinde yürütülür. Algoritma sırasında en fazla NA/2 yolu araştırılacaksa ve her bir yolu BFS ile araştırmak N+A ise, ürünün en önemli terimi ve dolayısıyla asimptotik karmaşıklık O(NA^2) olur.

mfp bir maxFlowProblemState .

 def edmonds_karp(mfp): sid, tid = mfp.sourceNodeUid, mfp.terminalNodeUid no_more_paths = False loop_count = 0 while(not no_more_paths): residual_digraph = get_residual_graph_of(mfp.G) try: asource = find_node_by_uid(mfp.sourceNodeUid, residual_digraph) aterm = find_node_by_uid(mfp.terminalNodeUid, residual_digraph) apath = bfs(asource, aterm, residual_digraph) paint_mfp_path(mfp, loop_count, apath) G = augment(apath, mfp.G) s = find_node_by_uid(sid, G) t = find_node_by_uid(tid, G) mfp = MaxFlowProblemState(G, s.uid, t.uid, mfp.maxFlowProblemStateUid) loop_count += 1 except StopIteration as e: no_more_paths = True return mfp

Yukarıdaki sürüm verimsizdir ve her seferinde yeni bir maksimum akış çözümü ve yeni bir artık grafik oluşturduğundan (algoritma ilerledikçe mevcut digrafları değiştirmek yerine O(NA^2) den daha karmaşıktır. Gerçek bir O(NA^2) çözümüne ulaşmak için algoritma, hem maksimum akış problem durumunu temsil eden digrafı hem de bununla ilişkili artık grafiğini korumalıdır. Bu nedenle algoritma, yaylar ve düğümler üzerinde gereksiz yere yineleme yapmaktan kaçınmalı ve artık grafikteki değerlerini ve ilgili değerleri yalnızca gerektiği şekilde güncellemelidir.

Daha hızlı bir Edmonds Karp algoritması yazmak için yukarıdakilerden birkaç kod parçasını yeniden yazdım. Umarım yeni bir digraf oluşturan kodu gözden geçirmek, neler olduğunu anlamada yardımcı olmuştur. Hızlı algoritmada, detaylarına girmek istemediğim bazı yeni hileler ve Python veri yapıları kullanıyorum. a.fromNode ve a.toNode artık düğümler için dizeler ve kullanıcı kimlikleri olarak ele alındığını söyleyeceğim. Bu kod için mfps bir maxFlowProblemState

 import uuid def fast_get_mfps_flow(mfps): flow_from_s = {n for n in mfps.G.setOfNodes if n.uid == mfps.sourceNodeUid}.pop().datum.flowOut flow_to_t = {n for n in mfps.G.setOfNodes if n.uid == mfps.terminalNodeUid}.pop().datum.flowIn if( (flow_to_t - flow_from_s) > 0.00): raise Exception('Infeasible st flow') return flow_to_t def fast_e_k_preprocess(G): G = strip_flows(G) get = dict({}) get['nodes'] = dict({}) get['node_to_node_capacity'] = dict({}) get['node_to_node_flow'] = dict({}) get['arcs'] = dict({}) get['residual_arcs'] = dict({}) for a in G.setOfArcs: if(a.fromNode not in G.setOfNodes): err_msg = 'There is no Node {a.fromNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) if(a.toNode not in G.setOfNodes): err_msg = 'There is no Node {a.toNode.uid!s} to match the Arc from {a.fromNode.uid!s} to {a.toNode.uid!s}'.format(**locals()) raise KeyError(err_msg) get['nodes'][a.fromNode.uid] = a.fromNode get['nodes'][a.toNode.uid] = a.toNode lark = Arc(a.fromNode.uid, a.toNode.uid, FlowArcDatumWithUid(a.datum.capacity, a.datum.flow, uuid.uuid4())) if(a.fromNode.uid not in get['arcs']): get['arcs'][a.fromNode.uid] = dict({a.toNode.uid : dict({lark.datum.uid : lark})}) else: if(a.toNode.uid not in get['arcs'][a.fromNode.uid]): get['arcs'][a.fromNode.uid][a.toNode.uid] = dict({lark.datum.uid : lark}) else: get['arcs'][a.fromNode.uid][a.toNode.uid][lark.datum.uid] = lark for a in G.setOfArcs: if a.toNode.uid not in get['arcs']: get['arcs'][a.toNode.uid] = dict({}) for n in get['nodes']: get['residual_arcs'][n] = dict() get['node_to_node_capacity'][n] = dict() get['node_to_node_flow'][n] = dict() for u in get['nodes']: n_to_u_cap_sum = sum(a.datum.capacity for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) n_to_u_flow_sum = sum(a.datum.flow for a in G.setOfArcs if (a.fromNode.uid == n) and (a.toNode.uid == u) ) if(n_to_u_cap_sum > n_to_u_flow_sum): flow = round(n_to_u_cap_sum - n_to_u_flow_sum, TOL) get['residual_arcs'][n][u] = Arc(n,u,ResidualDatum(flow, 'push')) if(n_to_u_flow_sum > 0.0): flow = round(n_to_u_flow_sum, TOL) get['residual_arcs'][u][n] = Arc(u,n,ResidualDatum(flow, 'pull')) get['node_to_node_capacity'][n][u] = n_to_u_cap_sum get['node_to_node_flow'][n][u] = n_to_u_flow_sum return get def fast_bfs(sid, tid, get): parent_of = dict([]) visited = frozenset([]) deq = coll.deque([sid]) while len(deq) > 0: n = deq.popleft() if n == tid: break for u in get['residual_arcs'][n]: if (u not in visited): visited = visited.union(frozenset({u})) parent_of[u] = get['residual_arcs'][n][u] deq.extend([u]) path = list([]) curr = tid while(curr != sid): if (curr not in parent_of): err_msg = 'No augmenting path from {} to {}.'.format(sid, curr) raise StopIteration(err_msg) path.extend([parent_of[curr]]) curr = parent_of[curr].fromNode path.reverse() return path def fast_edmonds_karp(mfps): sid, tid = mfps.sourceNodeUid, mfps.terminalNodeUid get = fast_e_k_preprocess(mfps.G) no_more_paths, loop_count = False, 0 while(not no_more_paths): try: apath = fast_bfs(sid, tid, get) get = fast_augment(apath, get) loop_count += 1 except StopIteration as e: no_more_paths = True nodes = frozenset(get['nodes'].values()) arcs = frozenset({}) for from_node in get['arcs']: for to_node in get['arcs'][from_node]: for arc in get['arcs'][from_node][to_node]: arcs |= frozenset({get['arcs'][from_node][to_node][arc]}) G = DiGraph(nodes, arcs) mfps = MaxFlowProblemState(G, sourceNodeUid=sid, terminalNodeUid=tid, maxFlowProblemStateUid=mfps.maxFlowProblemStateUid) return mfps

İşte bu algoritmanın yukarıdan örnek akış ağını nasıl çözdüğüne dair bir görselleştirme. Görselleştirme, adımları en güncel akış ağını temsil eden G grafiğine yansıtıldığı ve bu akış ağının artık grafiğine yansıtıldığı şekliyle gösterir. Kalıntı grafiğindeki artırma yolları kırmızı yollar olarak gösterilir ve sorunu temsil eden digraf , belirli bir artırma yolundan etkilenen düğümler ve yaylar kümesini yeşil renkle vurgulanır. Her durumda, grafiğin değiştirilecek kısımlarını (kırmızı veya yeşil) vurgulayacağım ve ardından değişikliklerden sonra grafiği (sadece siyah) göstereceğim.

İşte bu algoritmanın farklı bir örnek akış ağını nasıl çözdüğüne dair başka bir görselleştirme. Bunun gerçek sayılar kullandığına ve aynı fromNode ve toNode değerlerine sahip birden çok yay içerdiğine dikkat edin.

**Ayrıca, 'çekme' Artık Verili Yaylar, Artırma Yolunun bir parçası olabileceğinden, Uçan Ağın DiGraph'ında etkilenen düğümlerin _ G'deki bir yolda olmayabilir G! .

İki Parçalı Grafikler

Bir G digrafımız olduğunu G.setOfNodes G düğümleri iki kümeye ( part_1 ve part_2 ) bölmek mümkünse, G.setOfArcs içindeki herhangi bir ark a için a.fromNode in part_1 ve a.toNode içinde part_1 . a.fromNode part_2 ve a.toNode part_2 olması da doğru olamaz.

Diğer bir deyişle, her ark bir kümedeki bir düğümü diğer kümedeki bir düğüme bağlamak zorunda kalacak şekilde iki düğüm grubuna bölünebiliyorsa G iki parçalıdır .

Bipartit Testi

Bir G digrafımız olduğunu varsayalım, bunun iki parçalı olup olmadığını test etmek istiyoruz. Bunu O(|G.setOfNodes|+|G.setOfArcs|) içinde açgözlü bir şekilde grafiği iki renge boyayarak yapabiliriz.

İlk olarak, yeni bir digraf H oluşturmamız gerekiyor. Bu grafik G ile aynı düğüm kümesine sahip olacak, ancak G daha fazla yaya sahip olacak. G her yay a , H 2 yay oluşturacaktır; ilk yay a ile aynı olacaktır ve ikinci yay a direktörünü tersine çevirir ( b = Arc(a.toNode,a.fromNode,a.datum) ).

 Bipartition = coll.namedtuple('Bipartition',['firstPart', 'secondPart', 'G']) def bipartition(G): nodes = frozenset(G.setOfNodes arcs = frozenset(G.setOfArcs) arcs = arcs.union( frozenset( {Arc(a.toNode,a.fromNode,a.datum) for a in G.setOfArcs} ) ) H = DiGraph(nodes, arcs) H_as_dict = digraph_to_dict(H) color = dict([]) some_node = next(iter(H.setOfNodes)) deq = coll.deque([some_node]) color[some_node] = -1 while len(deq) > 0: curr = deq.popleft() for a in H_as_dict.get(curr): if (a.toNode not in color): color[a.toNode] = -1*color[curr] deq.extend([a.toNode]) elif(color[curr] == color[a.toNode]): print(curr,a.toNode) raise Exception('Not Bipartite.') firstPart = frozenset( {n for n in color if color[n] == -1 } ) secondPart = frozenset( {n for n in color if color[n] == 1 } ) if( firstPart.union(secondPart) != G.setOfNodes ): raise Exception('Not Bipartite.') return Bipartition(firstPart, secondPart, G)

Eşleşmeler ve Maksimum Eşleşmeler

Bir G digrafımız olduğunu ve matching G.setOfArcs gelen yayların bir alt kümesi olduğunu varsayalım. eşleşmedeki herhangi iki yay a ve b için matching ise bir matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Başka bir deyişle, eşleşen bir iki yay bir düğümü paylaşmaz.

Eşleştirme matching , G içinde len(matching) < len(alt_matching) gibi eşleşen başka bir alt_matching yoksa maksimum eşleşmedir. Başka bir deyişle, matching tanımını hala karşılayan G.setOfArcs gelen en büyük yay kümesiyse, eşleştirme bir maksimum eşleşmedir (önceden eşleştirmede olmayan herhangi bir yayın eklenmesi eşleştirme tanımını bozacaktır).

G.setOfArcs içindeki her n düğümü için, a.fromNode == n or a.toNode == n olan matching bir a yay varsa, maksimum eşleşme matching mükemmel bir eşleşmedir.

Maksimum İki Parçalı Eşleştirme

Maksimum ikili eşleşme , ikili olan bir G digrafında maksimum eşleşmedir.

G iki parçalı olduğu göz önüne alındığında, maksimum iki parçalı eşleşme bulma problemi, Edmonds-Karp algoritması ile çözülebilen bir maksimum akış problemine dönüştürülebilir ve daha sonra maksimum iki parçalı eşleşme , çözümden maksimum akış problemine geri döndürülebilir.

bipartition , G bir iki partisyonu olsun.

Bunu yapmak için, bazı yeni düğümler ( H.setOfNodes ) ve bazı yeni yaylar ( H.setOfArcs ) içeren yeni bir digraf ( H ​​) oluşturmam gerekiyor. H.setOfNodes , G.setOfNodes içindeki tüm düğümleri ve s (bir kaynak düğüm ) ve t (bir terminal düğümü ) olmak üzere iki düğüm daha içerir .

H.setOfArcs , her G.setOfArcs için bir yay içerecektir. Bir yay a G.setOfArcs ve a.fromNode bipartition.firstPart içindeyse ve a.toNode bipartition.secondPart içindeyse, a in H dahil edin (bir FlowArcDatum(1,0) ekleyerek).

a.fromNode bipartition.secondPart içindeyse ve a.toNode bipartition.firstPart Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) içinde H.setOfArcs .

İki parçalı bir grafiğin tanımı, her iki düğümün de aynı bölümde olduğu herhangi bir düğümü hiçbir arkın bağlamamasını sağlar. H.setOfArcs ayrıca bipartition.firstPart içindeki düğüm s her düğüme bir yay içerir. Son olarak, H.setOfArcs , bipartition.secondPart içindeki her düğümden t düğümüne bir yay içerir. a.datum.capacity = 1 H.setOfArcs tüm a için 1.

İlk önce G.setOfNodes içindeki düğümleri iki ayrık kümeyi ( part1 ve part2 ) bölün, G.setOfArcs hiçbir ark bir kümeden aynı kümeye yönlendirilmez (bu bölümleme mümkündür çünkü G iki parçalıdır ). Ardından, G.setOfArcs'ta part2 part1 yönlendirilen tüm yayları G.setOfArcs H.setOfArcs . Ardından tek bir kaynak düğümü s ve tek bir terminal düğümü t oluşturun ve biraz daha yay oluşturun

Ardından, bir maxFlowProblemState .

 def solve_mbm( bipartition ): s = Node(uuid.uuid4(), FlowNodeDatum(0,0)) t = Node(uuid.uuid4(), FlowNodeDatum(0,0)) translate = {} arcs = frozenset([]) for a in bipartition.G.setOfArcs: if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) ): fark = Arc(a.fromNode,a.toNode,FlowArcDatum(1,0)) arcs = arcs.union({fark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a elif ( (a.toNode in bipartition.firstPart) and (a.fromNode in bipartition.secondPart) ): bark = Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) arcs = arcs.union({bark}) translate[frozenset({a.fromNode.uid,a.toNode.uid})] = a arcs1 = frozenset( {Arc(s,n,FlowArcDatum(1,0)) for n in bipartition.firstPart } ) arcs2 = frozenset( {Arc(n,t,FlowArcDatum(1,0)) for n in bipartition.secondPart } ) arcs = arcs.union(arcs1.union(arcs2)) nodes = frozenset( {Node(n.uid,FlowNodeDatum(0,0)) for n in bipartition.G.setOfNodes} ).union({s}).union({t}) G = DiGraph(nodes, arcs) mfp = MaxFlowProblemState(G, s.uid, t.uid, 'bipartite') result = edmonds_karp(mfp) lookup_set = {a for a in result.G.setOfArcs if (a.datum.flow > 0) and (a.fromNode.uid != s.uid) and (a.toNode.uid != t.uid)} matching = {translate[frozenset({a.fromNode.uid,a.toNode.uid})] for a in lookup_set} return matching

Minimal Düğüm Kapağı

Bir G digrafındaki düğüm kapağı, G.setOfNodes'dan gelen bir düğümler ( cover ) kümesidir, öyle ki G.setOfNodes herhangi a yayı için bu doğru olmalıdır: ( G.setOfArcs (a.fromNode in cover) or (a.toNode in cover) .

Minimal düğüm örtüsü, grafikte hala bir düğüm örtüsü olan mümkün olan en küçük düğüm kümesidir. Konig'in teoremi, iki parçalı bir grafikte, o grafikteki maksimum eşleşmenin boyutunun minimum düğüm kapağının boyutuna eşit olduğunu belirtir ve düğüm kapağının maksimum eşleşmeden nasıl kurtarılabileceğini önerir:

bipartition ve maksimum eşleşme matching sahip olduğumuzu varsayalım. Yeni bir digraf tanımlayın H , H.setOfNodes=G.setOfNodes , H.setOfArcs içindeki yaylar iki kümenin birleşimidir.

İlk küme, a.fromNode in bipartition.firstPart içindeki a.fromNode ve a.toNode in bipartition.secondPart matching , oluşturulan yayda a.fromNode ve a.toNode değiştirilirse, bu tür yaylara a a.datum a.datum.inMatching=True özniteliği, bunların bir eşleşmedeki yaylardan türetildiğini gösterir.

İkinci küme, eşleşmede yaylar a matching ; şu değişiklikle birlikte, a.fromNode in bipartition.secondPart a.toNode in bipartition.firstPart a.toNode , oluşturulan arkta a.fromNode ve a.toNode değiştirilir (bu tür yaylara a.datum.inMatching=False öznitelik).

Ardından, eşleşen herhangi bir ark için bipartition.firstPart içindeki her n düğümünden başlayarak bir derinlik ilk araması (DFS) çalıştırın; bu, matching herhangi a ark için ne n == a.fromNode ne de n == a.toNodes . DFS sırasında, bazı düğümler ziyaret edilir ve bazıları ziyaret edilmez (bu bilgiyi n.datum.visited alanında saklayın). Minimum düğüm kapsamı , {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } düğümlerinin ve {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} düğümlerinin birleşimidir. {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Bunun, maksimum eşleşmeden minimum düğüm kaplamasına , çelişkili bir ispatla yol açtığı gösterilebilir, sözde kapsanmayan bir yay a alın ve a.fromNode ve a.toNode ait olup olmadığına ( toNode veya fromNode ) eşleşen matching herhangi bir yaya . Her durum, DFS'nin düğümleri ziyaret etme sırası ve eşleşmenin maksimum eşleşme matching gerçeği nedeniyle bir çelişkiye yol açar.

Bu adımları uygulayacak bir fonksiyonumuz olduğunu ve G digrafı verildiğinde minimum düğüm örtüsünü ve maksimum eşleşme matching içeren düğüm kümesini döndürdüğünü varsayalım:

 ArcMatchingDatum = coll.namedtuple('ArcMatchingDatum', ['inMatching' ]) NodeMatchingDatum = coll.namedtuple('NodeMatchingDatum', ['visited']) def dfs_helper(snodes, G): sniter, do_stop = iter(snodes), False visited, visited_uids = set(), set() while(not do_stop): try: stack = [ next(sniter) ] while len(stack) > 0: curr = stack.pop() if curr.uid not in visited_uids: visited = visited.union( frozenset( {Node(curr.uid, NodeMatchingDatum(False))} ) ) visited_uids = visited.union(frozenset({curr.uid})) succ = frozenset({a.toNode for a in G.setOfArcs if a.fromNode == curr}) stack.extend( succ.difference( frozenset(visited) ) ) except StopIteration as e: stack, do_stop = [], True return visited def get_min_node_cover(matching, bipartition): nodes = frozenset( { Node(n.uid, NodeMatchingDatum(False)) for n in bipartition.G.setOfNodes} ) G = DiGraph(nodes, None) charcs = frozenset( {a for a in matching if ( (a.fromNode in bipartition.firstPart) and (a.toNode in bipartition.secondPart) )} ) arcs0 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(True) ) for a in charcs } ) arcs1 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(True) ) for a in matching.difference(charcs) } ) not_matching = bipartition.G.setOfArcs.difference( matching ) charcs = frozenset( {a for a in not_matching if ( (a.fromNode in bipartition.secondPart) and (a.toNode in bipartition.firstPart) )} ) arcs2 = frozenset( { Arc(find_node_by_uid(a.toNode.uid,G), find_node_by_uid(a.fromNode.uid,G), ArcMatchingDatum(False) ) for a in charcs } ) arcs3 = frozenset( { Arc(find_node_by_uid(a.fromNode.uid,G), find_node_by_uid(a.toNode.uid,G), ArcMatchingDatum(False) ) for a in not_matching.difference(charcs) } ) arcs = arcs0.union(arcs1.union(arcs2.union(arcs3))) G = DiGraph(nodes, arcs) bip = Bipartition({find_node_by_uid(n.uid,G) for n in bipartition.firstPart},{find_node_by_uid(n.uid,G) for n in bipartition.secondPart},G) match_from_nodes = frozenset({find_node_by_uid(a.fromNode.uid,G) for a in matching}) match_to_nodes = frozenset({find_node_by_uid(a.toNode.uid,G) for a in matching}) snodes = bip.firstPart.difference(match_from_nodes).difference(match_to_nodes) visited_nodes = dfs_helper(snodes, bip.G) not_visited_nodes = bip.G.setOfNodes.difference(visited_nodes) H = DiGraph(visited_nodes.union(not_visited_nodes), arcs) cover1 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } ) cover2 = frozenset( {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (not a.toNode.datum.visited) ) } ) min_cover_nodes = cover1.union(cover2) true_min_cover_nodes = frozenset({find_node_by_uid(n.uid, bipartition.G) for n in min_cover_nodes}) return min_cover_nodes

Doğrusal Atama Problemi

Doğrusal atama problemi, ağırlıklı iki parçalı bir grafikte maksimum ağırlık eşleşmesini bulmaktan oluşur.

Bu yazının en başındaki gibi problemler doğrusal atama problemi olarak ifade edilebilir. Bir çalışan grubu, bir dizi görev ve bir çalışanın bir göreve atanmasının karlılığını gösteren bir fonksiyon verildiğinde, yaptığımız tüm atamaların toplamını maksimize etmek istiyoruz; bu bir lineer atama problemidir .

Görev ve işçi sayısının eşit olduğunu varsayın, ancak bu varsayımın kaldırılmasının kolay olduğunu göstereceğim. Uygulamada, bir arc a için a.datum.weight özniteliği ile ark ağırlıklarını temsil ediyorum.

 WeightArcDatum = namedtuple('WeightArcDatum', [weight])

Kuhn-Munkres Algoritması

Kuhn-Munkres Algoritması, doğrusal atama problemini çözer. İyi bir uygulama O(N^{4}) zaman alabilir (burada N , digrafta sorunu temsil eden düğüm sayısıdır). Açıklanması daha kolay bir uygulama, O(N^{5}) ( DiGraphs öğesini yeniden oluşturan bir sürüm için) ve O(N^{4}) için ( DiGraphs öğesini koruyan bir sürüm için) alır. Bu, Edmonds-Karp algoritmasının iki farklı uygulamasına benzer.

Bu açıklama için, yalnızca tam ikili grafiklerle çalışıyorum ( düğümlerin yarısının ikili bölümün bir bölümünde ve diğer yarısının ikinci bölümde olduğu). Çalışanda, görev motivasyonu, görevler kadar çok işçi olduğu anlamına gelir.

Bu önemli bir durum gibi görünüyor (ya bu kümeler eşit değilse!) ama bu sorunu düzeltmek kolaydır; Son bölümde bunun nasıl yapılacağı hakkında konuşuyorum.

Burada açıklanan algoritmanın versiyonu, faydalı sıfır ağırlıklı yay kavramını kullanır. Ne yazık ki, bu kavram yalnızca bir minimizasyonu çözerken anlamlıdır (işçi-görev atamalarımızın karlarını maksimize etmek yerine bu tür atamaların maliyetini en aza indiriyorsak).

Neyse ki, maksimum doğrusal atama problemini minimum doğrusal atama problemine dönüştürmek, her a yayı Ma.datum.weight olarak ayarlayarak kolaydır, burada M=max({a.datum.weight for a in G.setOfArcs}) . Orijinal maksimize etme probleminin çözümü, ark ağırlıkları değiştirildikten sonra problemin çözümüne benzer olacaktır. Kalan kısım için bu değişikliği yaptığımızı varsayalım.

Kuhn-Munkres algoritması , ağırlıklı ikili grafikteki minimum ağırlık eşleşmesini , ağırlıksız ikili grafiklerdeki bir dizi maksimum eşleşmeyle çözer. Doğrusal atama probleminin digraf temsilinde mükemmel bir eşleşme bulursak ve eşleşmedeki her yayın ağırlığı sıfır ise, bu eşleşme digraftaki tüm düğümlerin olduğunu gösterdiğinden minimum ağırlık eşleşmesini bulduk. mümkün olan en düşük maliyetli bir yay ile eşleştirilir (önceki tanımlara göre hiçbir maliyet 0'dan düşük olamaz).

Eşleştirmeye başka hiçbir yay eklenemez (çünkü tüm düğümler zaten eşleştirilmiştir) ve eşleştirmeden hiçbir yay çıkarılmamalıdır, çünkü olası herhangi bir değiştirme yayının en az aynı derecede büyük bir ağırlık değeri olacaktır.

Yalnızca sıfır ağırlıklı yaylar içeren G alt grafiğinin maksimum eşleşmesini bulursak ve bu mükemmel bir eşleşme değilse, tam bir çözüme sahip değiliz ( eşleşme mükemmel olmadığından). Bununla birlikte, G.setOfArcs içindeki yayların ağırlıklarını yeni 0 ağırlıklı yayların görüneceği ve H optimal çözümü G optimal çözümü ile aynı olacak şekilde değiştirerek yeni bir H digrafı üretebiliriz. Her yinelemede en az bir sıfır ağırlıklı yayın üretildiğini garanti ettiğimiz için, bu tür yinelemelerden en fazla |G.setOfNodes|^{2}=N^{2} mükemmel bir eşleşmeye ulaşacağımızı garanti ederiz.

bipartition bipartition 'da bipartition.firstPart öğesinin çalışanları temsil eden düğümleri içerdiğini ve bipartition.secondPart görevleri temsil eden düğümleri temsil ettiğini varsayalım.

Algoritma, yeni bir digraf H üreterek başlar. H.setOfNodes = G.setOfNodes . H bazı yaylar , bipartition.firstPart içindeki n düğümlerinden üretilir. Bu tür her bir n düğümü , bipartition.G.setOfArcs içindeki her ark a için H.setOfArcs içinde bir b ark üretir; burada a.fromNode = n veya a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) burada z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

H daha fazla yay , bipartition.secondPart içindeki n düğümlerinden üretilir. Bu tür her bir düğüm n , bipartition.G.setOfArcs içindeki her ark a için H.setOfArcs içinde bir b ark üretir; burada a.fromNode = n veya a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) burada z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Ardından, yalnızca H gelen sıfır ağırlıklı yaylardan ve bu yaylara gelen düğümlerden oluşan yeni bir K digrafı oluşturun. K düğümler üzerinde bir bipartition bölüm oluşturun, ardından K üzerinde maksimum eşleştirme ( matching ) elde etmek için solve_mbm( bipartition ) kullanın. matching H mükemmel bir eşleşme ise ( matching yaylar H.setOfNodes içindeki tüm düğümlerde meydana H.setOfNodes ), o zaman matching doğrusal atama problemine en uygun çözümdür.

Aksi takdirde, matching mükemmel değilse, node_cover = get_min_node_cover(matching, bipartition(K)) kullanarak K minimum düğüm kapağını oluşturun. Ardından, z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Define nodes = H.setOfNodes , arcs1 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} , arcs2 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} , arcs3 = {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} != sembolü bir XOR operatörü gibi davranır.Ardından arcs = arcs1.union(arcs2.union(arcs3)) , H=DiGraph(nodes,arcs) . KMA etiketi Mükemmel bir eşleşme elde edilene kadar algoritma devam eder.Bu eşleştirme aynı zamanda lineer atama probleminin de çözümüdür.

 def kuhn_munkres( bipartition ): nodes = bipartition.G.setOfNodes arcs = frozenset({}) for n in bipartition.firstPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) for n in bipartition.secondPart: z = min( {x.datum.weight for x in bipartition.G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )} ) arcs = arcs.union( frozenset({Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) }) ) H = DiGraph(nodes, arcs) assignment, value = dict({}), 0 not_done = True while( not_done ): zwarcs = frozenset( {a for a in H.setOfArcs if a.datum.weight == 0} ) znodes = frozenset( {n.fromNode for n in zwarcs} ).union( frozenset( {n.toNode for n in zwarcs} ) ) K = DiGraph(znodes, zwarcs) k_bipartition = bipartition(K) matching = solve_mbm( k_bipartition ) mnodes = frozenset({a.fromNode for a in matching}).union(frozenset({a.toNode for a in matching})) if( len(mnodes) == len(H.setOfNodes) ): for a in matching: assignment[ a.fromNode.uid ] = a.toNode.uid value = sum({a.datum.weight for a in matching}) not_done = False else: node_cover = get_min_node_cover(matching, bipartition(K)) z = min( frozenset( {a.datum.weight for a in H.setOfArcs if a not in node_cover} ) ) nodes = H.setOfNodes arcs1 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh-z)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) and (a.toNode not in node_cover)} ) arcs2 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh)) for a in H.setOfArcs if ( (a.fromNode not in node_cover) != (a.toNode not in node_cover)} ) arcs3 = frozenset( {Arc(a.fromNode,a.toNode,ArcWeightDatum(a.datum.weigh+z)) for a in H.setOfArcs if ( (a.fromNode in node_cover) and (a.toNode in node_cover)} ) arcs = arcs1.union(arcs2.union(arcs3)) H = DiGraph(nodes,arcs) return value, assignment

Bu uygulama O(N^{5}) dir çünkü her yinelemede yeni bir maksimum eşleşme matching oluşturur; Edmonds-Karp'ın önceki iki uygulamasına benzer şekilde, bu algoritma değiştirilebilir, böylece eşleşmeyi takip eder ve onu her yinelemeye akıllıca uyarlar. Bu yapıldığında, karmaşıklık O(N^{4}) olur. Bu algoritmanın (bazı daha gelişmiş veri yapıları gerektiren) daha gelişmiş ve daha yeni bir sürümü O(N^{3}) içinde çalışabilir. Hem yukarıdaki daha basit uygulamanın hem de daha gelişmiş uygulamanın ayrıntıları, bu blog gönderisini motive eden bu gönderide bulunabilir.

Yay ağırlıkları üzerindeki işlemlerin hiçbiri, algoritma tarafından döndürülen son atamayı değiştirmez. İşte nedeni: Girdi grafiklerimiz her zaman tam iki parçalı grafikler olduğundan, bir çözüm, bir bölümdeki her düğümü , bu iki düğüm arasındaki yay yoluyla ikinci bölümdeki başka bir düğüme eşlemelidir. Yay ağırlıkları üzerinde gerçekleştirilen işlemlerin herhangi bir düğümde meydana gelen yayların sırasını (ağırlık sırasına göre) asla değiştirmediğine dikkat edin.

Bu nedenle, algoritma mükemmel bir tam iki parçalı eşleşmede sona erdiğinde, her düğüme sıfır ağırlıklı bir yay atanır, çünkü bu düğümden gelen yayların göreceli sırası algoritma sırasında değişmemiştir ve sıfır ağırlıklı bir yay mümkün olan en ucuz yaydır ve mükemmel tam ikili eşleme , her düğüm için böyle bir yayın var olduğunu garanti eder. Bu, üretilen çözümün, ark ağırlıklarında herhangi bir değişiklik olmaksızın orijinal doğrusal atama probleminden gelen çözümle gerçekten aynı olduğu anlamına gelir.

Dengesiz Atamalar

Algoritma, açıklandığı gibi yalnızca tam iki parçalı grafiklerde çalıştığından ( düğümlerin yarısının iki bölümün bir bölümünde ve diğer yarısının ikinci bölümde olduğu) oldukça sınırlı gibi görünüyor. Çalışanda, görev motivasyonu, görev sayısı kadar işçi olduğu anlamına gelir (oldukça sınırlayıcı görünmektedir).

Ancak bu kısıtlamayı ortadan kaldıran kolay bir dönüşüm var. Görevlerden daha az işçi olduğunu varsayalım, bazı kukla işçiler ekliyoruz (sonuçtaki grafiği tam bir iki parçalı grafik yapmaya yetecek kadar). Each dummy worker has an arc directed from the worker to each of the tasks. Each such arc has weight 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any task assigned a dummy worker is not initiated.

Suppose that there are more tasks than workers. We add some dummy tasks (enough to make the resulting graph a complete bipartite graph ). Each dummy task has an arc directed from each worker to the dummy task. Each such arc has a weight of 0 (placing it in a matching gives no added profit). After this change the graph is a complete bipartite graph which we can solve for. Any worker assigned to dummy task is not employed during the period.

A Linear Assignment Example

Finally, let's do an example with the code I've been using. I'm going to modify the example problem from here. We have 3 tasks: we need to clean the bathroom , sweep the floor , and wash the windows .

The workers available to use are Alice , Bob , Charlie , and Diane . Each of the workers gives us the wage they require per task. Here are the wages per worker:

If we want to pay the least amount of money, but still get all the tasks done, who should do what task? Start by introducing a dummy task to make the digraph representing the problem bipartite.

Supposing that the problem is encoded in a digraph , then kuhn_munkres( bipartition(G) ) will solve the problem and return the assignment. It's easy to verify that the optimal (lowest cost) assignment will cost $5.

Here's a visualization of the solution the code above generates:

That is it. You now know everything you need to know about the linear assignment problem.

You can find all of the code from this article on GitHub.

Toptal Mühendislik Blogunda Daha Fazla Okuma:

• Python/NetworkX ile Grafik Veri Bilimi