Arus Maksimum dan Masalah Penugasan Linier

Inilah masalahnya: Bisnis Anda menugaskan kontraktor untuk memenuhi kontrak. Anda melihat daftar nama Anda dan memutuskan kontraktor mana yang tersedia untuk pertunangan satu bulan dan Anda melihat melalui kontrak yang tersedia untuk melihat mana di antara mereka yang untuk tugas satu bulan. Mengingat bahwa Anda tahu seberapa efektif setiap kontraktor dapat memenuhi setiap kontrak, bagaimana Anda menugaskan kontraktor untuk memaksimalkan efektivitas keseluruhan untuk bulan itu?

Ini adalah contoh dari masalah penugasan, dan masalah tersebut dapat diselesaikan dengan algoritma Hungaria klasik.

Algoritma Hungaria (juga dikenal sebagai algoritma Kuhn-Munkres) adalah algoritma waktu polinomial yang memaksimalkan pencocokan bobot dalam graf bipartit berbobot. Di sini, kontraktor dan kontrak dapat dimodelkan sebagai grafik bipartit, dengan efektivitasnya sebagai bobot tepi antara kontraktor dan simpul kontrak.

Pada artikel ini, Anda akan belajar tentang implementasi algoritma Hungaria yang menggunakan algoritma Edmonds-Karp untuk menyelesaikan masalah penugasan linier. Anda juga akan mempelajari bagaimana algoritma Edmonds-Karp adalah sedikit modifikasi dari metode Ford-Fulkerson dan bagaimana modifikasi ini penting.

Masalah Aliran Maksimum

Masalah aliran maksimum itu sendiri dapat digambarkan secara informal sebagai masalah pemindahan sejumlah fluida atau gas melalui jaringan pipa dari satu sumber ke satu terminal. Hal ini dilakukan dengan asumsi bahwa tekanan dalam jaringan cukup untuk memastikan bahwa cairan atau gas tidak dapat berlama-lama di sepanjang pipa atau fitting pipa (tempat-tempat di mana panjang pipa yang berbeda bertemu).

Dengan membuat perubahan tertentu pada grafik, masalah penugasan dapat diubah menjadi masalah aliran maksimum.

Persiapan

Ide-ide yang diperlukan untuk memecahkan masalah ini muncul dalam banyak disiplin matematika dan teknik, seringkali konsep serupa dikenal dengan nama yang berbeda dan diekspresikan dengan cara yang berbeda (misalnya, matriks ketetanggaan dan daftar ketetanggaan). Karena ide-ide ini cukup esoteris, pilihan dibuat mengenai seberapa umum konsep-konsep ini akan didefinisikan untuk pengaturan tertentu.

Artikel ini tidak akan mengasumsikan pengetahuan sebelumnya di luar sedikit teori himpunan pengantar.

Implementasi pada postingan ini merepresentasikan permasalahan sebagai graf berarah (digraph).

DiGraphs

Digraf memiliki dua atribut, setOfNodes dan setOfArcs . Kedua atribut ini adalah himpunan (koleksi tidak berurutan). Di blok kode pada posting ini, saya sebenarnya menggunakan frozenset Python, tetapi detail itu tidak terlalu penting.

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

(Catatan: Ini, dan semua kode lain dalam artikel ini, ditulis dengan Python 3.6.)

Node

Sebuah node n terdiri dari dua atribut:

• n.uid : Pengidentifikasi unik.

  Ini berarti bahwa untuk setiap dua simpul x dan y ,

 x.uid != y.uid

• n.datum : Ini mewakili objek data apa pun.

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

busur

Busur a terdiri dari tiga atribut:

• a.fromNode : Ini adalah node , seperti yang didefinisikan di atas.

• a.toNode : Ini adalah node , seperti yang didefinisikan di atas.

• a.datum : Ini mewakili objek data apa pun.

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

Himpunan busur di digraf mewakili relasi biner pada simpul di digraf . Adanya arc a menyiratkan bahwa ada hubungan antara a.fromNode dan a.toNode .

Dalam graf berarah (berlawanan dengan graf tak berarah), keberadaan hubungan antara a.fromNode dan a.toNode tidak menyiratkan bahwa ada hubungan serupa antara a.toNode dan a.fromNode .

Hal ini karena pada graf tak berarah, hubungan yang diekspresikan belum tentu simetris.

DiGraphs

Node dan arc dapat digunakan untuk mendefinisikan digraph , tetapi untuk kemudahan, dalam algoritme di bawah ini, digraph akan direpresentasikan sebagai kamus.

Berikut adalah metode yang dapat mengubah representasi grafik di atas menjadi representasi kamus yang mirip dengan ini:

 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

Dan inilah satu lagi yang mengubahnya menjadi kamus kamus, operasi lain yang akan berguna:

 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

Ketika artikel berbicara tentang digraf yang diwakili oleh kamus, artikel tersebut akan menyebutkan G_as_dict untuk merujuknya.

Terkadang sangat membantu untuk mengambil simpul dari digraf G melalui uid (pengidentifikasi unik):

 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()

Dalam mendefinisikan graf, orang terkadang menggunakan istilah simpul dan simpul untuk merujuk pada konsep yang sama; hal yang sama berlaku untuk istilah busur dan tepi.

Dua representasi grafik populer di Python adalah yang satu ini menggunakan kamus dan satu lagi yang menggunakan objek untuk mewakili grafik. Representasi dalam posting ini berada di antara dua representasi yang umum digunakan ini.

Ini adalah representasi digraph saya. Ada banyak yang seperti itu, tapi yang ini milikku.

Jalan dan Jalan

Misalkan S_Arcs merupakan barisan berhingga (kumpulan terurut) dari busur -busur dalam digraf G sedemikian sehingga jika a adalah sembarang busur dalam S_Arcs kecuali yang terakhir, dan b mengikuti a dalam barisan tersebut, maka harus ada simpul n = a.fromNode di G.setOfNodes sedemikian rupa sehingga a.toNode = b.fromNode .

Mulai dari busur pertama di S_Arcs , dan berlanjut hingga busur terakhir di S_Arcs , kumpulkan (dalam urutan yang ditemukan) semua node n seperti yang didefinisikan di atas di antara masing-masing dua busur berurutan di S_Arcs . Beri label kumpulan node yang diurutkan yang dikumpulkan selama operasi ini 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

• Jika ada simpul yang muncul lebih dari satu kali dalam urutan S_Nodes maka panggil S_Arcs a Walk pada digraf G .

• Jika tidak, panggil S_Arcs jalur dari list(S_Nodes)[0] ke list(S_Nodes)[-1] pada digraph G .

Node Sumber

Panggil simpul s sebagai simpul sumber dalam digraf G jika s ada di G.setOfNodes dan G.setOfArcs tidak mengandung busur a sedemikian rupa sehingga a.toNode = s .

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

simpul terminal

Panggil simpul t sebagai simpul terminal dalam digraf G jika t ada di G.setOfNodes dan G.setOfArcs tidak mengandung busur a sedemikian rupa sehingga a.fromNode = t .

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

Pemotongan dan Pemotongan st

Potongan cut dari digraf terhubung G adalah subset dari busur dari G.setOfArcs yang mempartisi himpunan node G.setOfNodes di G . G terhubung jika setiap simpul n di G.setOfNodes dan memiliki setidaknya satu busur a di G.setOfArcs sedemikian rupa sehingga n = a.fromNode atau n = a.toNode , tetapi a.fromNode != a.toNode .

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

Definisi di atas mengacu pada subset dari busur , tetapi juga dapat mendefinisikan partisi dari node G.setOfNodes .

Untuk fungsi predecessors_of dan successors_of , n adalah simpul di himpunan G.setOfNodes dari digraf G , dan cut adalah potongan dari G :

 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

Biarkan cut menjadi potongan digraf G .

 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 adalah potongan digraf G jika: (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 disebut xy cut if (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . Jika simpul x pada cut xy adalah simpul sumber dan simpul y pada pemotongan xy adalah simpul terminal , maka pemotongan ini disebut pemotongan st .

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

Jaringan Aliran

Anda dapat menggunakan digraf G untuk mewakili jaringan aliran.

Tetapkan setiap node n , di mana n berada di G.setOfNodes sebuah n.datum yang merupakan FlowNodeDatum :

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

Tetapkan setiap busur a , di mana a ada di G.setOfArcs dan a.datum yang merupakan FlowArcDatum .

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

flowNodeDatum.flowIn dan flowNodeDatum.flowOut adalah bilangan real positif.

flowArcDatum.capacity dan flowArcDatum.flow juga bilangan real positif.

Untuk setiap node node n di G.setOfNodes :

 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 sekarang mewakili jaringan aliran .

Aliran G mengacu pada a.flow untuk semua busur a di G .

Aliran yang Layak

Biarkan digraf G mewakili jaringan aliran .

Jaringan aliran yang diwakili oleh G memiliki aliran yang layak jika:

1. Untuk setiap node n di G.setOfNodes kecuali node sumber dan node terminal : n.datum.flowIn = n.datum.flowOut .

2. Untuk setiap busur a di G.setOfNodes : a.datum.capacity <= a.datum.flow .

Kondisi 1 disebut kendala konservasi.

Kondisi 2 disebut batasan kapasitas.

Kapasitas potong

Kapasitas potong dari st cut stCut dengan node sumber s dan node terminal t dari jaringan aliran yang diwakili oleh digraf G adalah:

 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

Potongan Kapasitas Minimum

Biarkan stCut = stCut(s,t,cut) menjadi potongan pertama dari jaringan aliran yang diwakili oleh digraf G .

stCut adalah pemotongan kapasitas minimum dari jaringan aliran yang diwakili oleh G jika tidak ada stCutCompetitor stCutCompetitor dalam jaringan aliran ini sehingga:

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

Melucuti Arusnya

Saya ingin merujuk ke digraf yang akan menjadi hasil dari mengambil digraf G dan menghapus semua aliran data dari semua node di G.setOfNodes dan juga semua busur di 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)

Masalah Aliran Maksimum

Jaringan aliran direpresentasikan sebagai digraf G , simpul sumber s di G.setOfNodes dan simpul terminal t di G.setOfNodes , G dapat mewakili masalah aliran maksimum jika:

 (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)

Beri label representasi ini:

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

Di mana sourceNodeUid = s.uid , terminalNodeUid = t.uid , dan maxFlowProblemStateUid adalah pengidentifikasi untuk instance masalah.

Solusi Aliran Maksimum

Biarkan maxFlowProblem mewakili masalah aliran maksimum . Solusi untuk maxFlowProblem dapat diwakili oleh jaringan aliran yang direpresentasikan sebagai digraf H .

Digraph H adalah solusi yang layak untuk masalah aliran maksimum pada input python maxFlowProblem jika:

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

2. H adalah jaringan aliran dan memiliki aliran yang layak .

Jika selain 1 dan 2:

1. Tidak ada jaringan aliran lain yang diwakili oleh digraf K seperti strip_flows(G) == strip_flows(K) dan find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

Maka H juga merupakan solusi optimal untuk maxFlowProblem .

Dengan kata lain solusi aliran maksimum yang layak dapat direpresentasikan oleh sebuah digraf , yang:

1. Identik dengan digraf G dari masalah aliran maksimum yang sesuai dengan pengecualian bahwa n.datum.flowIn , n.datum.flowOut dan a.datum.flow dari setiap node dan busur mungkin berbeda.

2. Merupakan jaringan aliran yang memiliki aliran yang layak .

Dan, itu dapat mewakili solusi aliran maksimum yang optimal jika tambahan:

1. flowIn untuk node yang berkorespondensi dengan terminal node dalam masalah aliran maksimum adalah sebesar mungkin (bila kondisi 1 dan 2 masih terpenuhi).

Jika digraf H mewakili solusi aliran maksimum yang layak : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn mengikuti dari aliran max, teorema min cut (dibahas di bawah). Secara informal, karena H diasumsikan memiliki aliran yang layak , ini berarti bahwa aliran tidak dapat 'diciptakan' (kecuali pada simpul sumber s ) atau 'dihancurkan' (kecuali pada simpul terminal t ) saat melintasi simpul (lainnya) ( konstrain konservasi ).

Karena masalah aliran maksimum hanya berisi satu simpul sumber s dan satu simpul terminal t , semua aliran 'diciptakan' pada s harus 'dihancurkan' pada t atau jaringan aliran tidak memiliki aliran yang layak ( konstrain konservasi akan dilanggar ).

Biarkan digraf H mewakili solusi aliran maksimum yang layak ; nilai di atas disebut st Flow Value dari H .

Membiarkan:

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

Ini berarti bahwa mfps adalah status penerus dari maxFlowProblem , yang berarti bahwa mfps seperti maxFlowProblem dengan pengecualian bahwa nilai a.flow untuk busur a di maxFlowProblem.setOfArcs mungkin berbeda dari a.flow untuk busur a di 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

Berikut adalah visualisasi mfps beserta maxFlowProb yang terkait. Setiap busur a pada gambar memiliki label, label ini adalah a.datum.flowFrom / a.datum.flowTo , setiap simpul n pada gambar memiliki label, dan label ini adalah n.uid {n.datum.flowIn / a.datum.flowOut} .

Aliran potong st

Biarkan mfps mewakili MaxFlowProblemState dan biarkan stCut mewakili potongan mfps.G . Aliran potong stCut didefinisikan:

 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 cut flow adalah jumlah arus dari partisi yang berisi simpul sumber ke partisi yang berisi simpul terminal dikurangi jumlah arus dari partisi yang berisi simpul terminal ke partisi yang berisi simpul sumber .

Aliran Maks, Pemotongan Min

Biarkan maxFlowProblem mewakili masalah aliran maksimum dan biarkan solusi untuk maxFlowProblem diwakili oleh jaringan aliran yang direpresentasikan sebagai digraf H .

Biarkan minStCut menjadi potongan kapasitas minimum dari jaringan aliran yang diwakili oleh maxFlowProblem.G .

Karena dalam masalah aliran maksimum , aliran hanya berasal dari satu simpul sumber dan berakhir pada satu simpul terminal dan, karena kendala kapasitas dan kendala konservasi , kita tahu bahwa semua aliran yang memasuki maxFlowProblem.terminalNodeUid harus melewati setiap st cut , khususnya harus melewati minStCut . Ini berarti:

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

Memecahkan Masalah Aliran Maksimum

Ide dasar untuk memecahkan masalah aliran maksimum maxFlowProblem adalah memulai dengan solusi aliran maksimum yang diwakili oleh digraf H . Titik awal seperti itu dapat berupa H = strip_flows(maxFlowProblem.G) . Tugasnya kemudian menggunakan H dan dengan beberapa modifikasi serakah dari nilai a.datum.flow dari beberapa busur a di H.setOfArcs untuk menghasilkan solusi aliran maksimum lain yang diwakili oleh digraf K sedemikian rupa sehingga K masih tidak dapat mewakili jaringan aliran dengan aliran yang layak dan get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . Selama proses ini berlanjut, kualitas ( get_flow_value(K, maxFlowProblem) ) dari solusi aliran maksimum yang paling baru ditemui ( K ) lebih baik daripada solusi aliran maksimum lainnya yang telah ditemukan. Jika proses mencapai titik yang diketahui bahwa tidak ada perbaikan lain yang mungkin, proses dapat dihentikan dan akan mengembalikan solusi aliran maksimum yang optimal.

Uraian di atas bersifat umum dan melewatkan banyak bukti seperti apakah proses seperti itu mungkin atau berapa lama waktu yang dibutuhkan, saya akan memberikan beberapa detail lagi dan algoritme.

Aliran Maks, Teorema Potong Min

Dari buku Flows in Networks oleh Ford dan Fulkerson, pernyataan teorema aliran maks, teorema min cut (Teorema 5.1) adalah:

Untuk setiap jaringan, nilai aliran maksimal dari s ke t sama dengan kapasitas pemotongan minimum dari semua pemotongan yang memisahkan s dan t .

Menggunakan definisi dalam posting ini, yang diterjemahkan menjadi:

Solusi untuk maxFlowProblem yang diwakili oleh jaringan aliran yang direpresentasikan sebagai digraf H optimal jika:

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

Saya suka bukti teorema ini dan Wikipedia memiliki satu lagi.

Teorema max flow, min cut digunakan untuk membuktikan kebenaran dan kelengkapan metode Ford-Fulkerson .

Saya juga akan memberikan bukti teorema di bagian setelah augmenting paths .

Metode Ford-Fulkerson dan Algoritma Edmonds-Karp

CLRS mendefinisikan metode Ford-Fulkerson seperti ini (bagian 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

Grafik sisa

Grafik Residu dari jaringan aliran yang direpresentasikan sebagai digraf G dapat direpresentasikan sebagai digraf G_f :

 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) mengembalikan jumlah a.datum.capacity untuk semua busur dalam subset G.setOfArcs di mana busur a berada di subset jika a.fromNode = n dan a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) mengembalikan jumlah a.datum.flow untuk semua busur dalam subset G.setOfArcs di mana busur a berada di subset jika a.fromNode = n dan a.toNode = u .

Secara singkat, graf residual G_f mewakili tindakan tertentu yang dapat dilakukan pada digraf G .

Setiap pasangan node n,u dalam G.setOfNodes dari jaringan aliran yang diwakili oleh digraf G dapat menghasilkan 0, 1, atau 2 busur pada graf residual G_f dari G .

1. Pasangan n,u tidak menghasilkan busur apa pun di G_f jika tidak ada busur a di G.setOfArcs sedemikian rupa sehingga a.fromNode = n dan a.toNode = u .

2. Pasangan n,u menghasilkan busur a di G_f.setOfArcs di mana a mewakili busur berlabel busur aliran dorong dari n ke u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) jika n_to_u_cap_sum > n_to_u_flow_sum .

3. Pasangan n,u menghasilkan busur a di G_f.setOfArcs di mana a mewakili busur berlabel busur aliran tarik dari n ke u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) jika n_to_u_flow_sum > 0.0 .

• Setiap busur aliran push di G_f.setOfArcs mewakili tindakan penambahan total x <= n_to_u_cap_sum - n_to_u_flow_sum aliran ke busur di subset dari G.setOfArcs di mana busur a berada di subset jika a.fromNode = n dan a.toNode = u

• Setiap busur aliran tarikan di G_f.setOfArcs mewakili tindakan pengurangan total x <= n_to_u_flow_sum aliran ke busur dalam himpunan bagian dari G.setOfArcs di mana busur a berada dalam himpunan bagian jika a.fromNode = n dan a.toNode = u .

Melakukan tindakan push atau pull individu dari G_f pada busur yang berlaku di G mungkin menghasilkan jaringan aliran tanpa aliran yang layak karena kendala kapasitas atau kendala konservasi mungkin dilanggar dalam jaringan aliran yang dihasilkan .

Berikut adalah visualisasi grafik residual dari contoh visualisasi sebelumnya dari solusi aliran maksimum , dalam visualisasi masing-masing busur a mewakili a.residualCapacity .

Menambah Jalur

Biarkan maxFlowProblem menjadi masalah aliran maks , dan biarkan G_f = get_residual_graph_of(G) menjadi grafik residual dari maxFlowProblem.G .

Jalur augmenting augmentingPath untuk maxFlowProblem adalah jalur apa pun dari find_node_by_uid(maxFlowProblem.sourceNode,G_f) ke find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

Ternyata augmenting path augmentingPath dapat diterapkan ke solusi aliran maks yang diwakili oleh digraf H menghasilkan solusi aliran maks lainnya yang diwakili oleh digraf K di mana get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) jika H tidak optimal .

Berikut caranya:

 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

Di atas, TOL adalah beberapa nilai toleransi untuk pembulatan nilai aliran dalam jaringan. Hal ini untuk menghindari ketidaktepatan cascading perhitungan floating point. Jadi, misalnya, saya menggunakan TOL = 10 yang berarti membulatkan hingga 10 angka penting.

Biarkan K = augment(augmentingPath, H) , maka K mewakili solusi aliran maks yang layak untuk maxFlowProblem . Agar pernyataan benar, jaringan aliran yang diwakili oleh K harus memiliki aliran yang layak (tidak melanggar batasan kapasitas atau batasan konservasi .

Inilah alasannya: Dalam metode di atas, setiap simpul yang ditambahkan ke jaringan aliran baru yang diwakili oleh digraf K adalah salinan tepat dari simpul dari digraf H atau simpul n yang memiliki nomor yang sama ditambahkan ke n.datum.flowIn sebagai itu n.datum.flowOut . Ini berarti bahwa kendala konservasi terpenuhi di K selama itu dipenuhi di H . Batasan konservasi terpenuhi karena kami secara eksplisit memeriksa bahwa setiap busur baru a dalam jaringan memiliki a.datum.flow <= a.datum.capacity ; jadi, selama busur dari himpunan H.setOfArcs yang disalin tanpa dimodifikasi ke K.setOfArcs tidak melanggar batasan kapasitas , maka K tidak melanggar batasan kapasitas .

Benar juga bahwa get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) jika H tidak optimal .

Inilah alasannya: Agar jalur augmentingPath ada dalam representasi digraf dari grafik residual G_f dari masalah aliran maks maxFlowProblem maka busur terakhir a pada augmentingPath harus berupa busur 'push' dan harus memiliki a.toNode == maxFlowProblem.terminalNode . Jalur augmentasi didefinisikan sebagai jalur yang berakhir pada simpul terminal dari masalah aliran maksimum yang merupakan jalur augmentasi . Dari definisi graf residual , jelas bahwa busur terakhir dalam jalur augmentasi pada graf residual tersebut harus berupa busur 'push' karena setiap busur ' tarik' b di jalur augmentasi akan memiliki b.toNode == maxFlowProblem.terminalNode dan b.fromNode != maxFlowProblem.terminalNode dari definisi path . Selain itu, dari definisi path , jelas bahwa simpul terminal hanya dimodifikasi satu kali dengan metode augment . Jadi augment memodifikasi maxFlowProblem.terminalNode.flowIn tepat satu kali dan itu meningkatkan nilai maxFlowProblem.terminalNode.flowIn karena busur terakhir di augmentingPath harus menjadi busur yang menyebabkan modifikasi di maxFlowProblem.terminalNode.flowIn selama augment . Dari definisi augment yang berlaku untuk 'push' arcs , maxFlowProblem.terminalNode.flowIn hanya dapat ditingkatkan, tidak dikurangi.

Beberapa Bukti dari Sedgewick dan Wayne

Buku Algorithms, edisi keempat oleh Robert Sedgewich dan Kevin Wayne memiliki beberapa bukti yang bagus dan singkat (halaman 892-894) yang akan berguna. Saya akan membuatnya ulang di sini, meskipun saya akan menggunakan bahasa yang sesuai dengan definisi sebelumnya. Label saya untuk buktinya sama dengan di buku Sedgewick.

Proposisi E: Untuk setiap digraf H yang mewakili solusi aliran maksimum yang layak untuk masalah aliran maksimum maxFlowProblem , untuk setiap stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

Bukti: Biarkan stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . Proposisi E berlaku untuk stCut langsung dari definisi nilai aliran st . Misalkan di sana kita ingin memindahkan beberapa node n dari partisi-s ( get_first_part(stCut.cut, G) ) dan ke dalam partisi-t (get_second_part(stCut.cut, G)) , untuk melakukannya kita perlu mengubah stCut.cut , yang dapat mengubah stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) dan membatalkan proposisi E . Namun, mari kita lihat bagaimana nilai stcut_flow akan berubah saat kita melakukan perubahan ini. simpul n berada pada kesetimbangan yang berarti bahwa jumlah aliran ke simpul n sama dengan jumlah aliran keluar (ini diperlukan untuk H untuk mewakili solusi yang layak ). Perhatikan bahwa semua aliran yang merupakan bagian dari stcut_flow yang memasuki simpul n memasukinya dari partisi s (aliran yang memasuki simpul n dari partisi t baik secara langsung maupun tidak langsung tidak akan dihitung dalam nilai stcut_flow karena menuju ke arah yang salah berdasarkan definisi). Selain itu, semua aliran keluar n akhirnya (langsung atau tidak langsung) mengalir ke simpul terminal (dibuktikan sebelumnya). Ketika kita memindahkan node n ke dalam partisi-t, semua aliran yang masuk n dari partisi-s harus ditambahkan ke nilai stcut_flow yang baru; namun, semua aliran yang keluar dari n harus dikurangi dari nilai stcut_flow yang baru; bagian aliran yang menuju langsung ke partisi-t dikurangi karena aliran ini sekarang internal ke partisi-t baru dan tidak dihitung sebagai stcut_flow . Bagian aliran dari n menuju ke node di partisi s juga harus dikurangi dari stcut_flow : Setelah n dipindahkan ke partisi t, aliran ini akan diarahkan dari partisi t ke partisi s dan seterusnya tidak boleh diperhitungkan dalam stcut_flow , karena aliran ini dihilangkan aliran masuk ke partisi s dan harus dikurangi dengan jumlah aliran ini, dan aliran keluar dari partisi s ke partisi t (di mana semua mengalir dari st harus berakhir) harus dikurangi dengan jumlah yang sama. Karena simpul n berada pada keseimbangan sebelum proses, pembaruan akan menambahkan nilai yang sama ke nilai stcut_flow baru saat dikurangi sehingga meninggalkan proposisi E benar setelah pembaruan. Validitas proposisi E kemudian mengikuti dari induksi pada ukuran partisi-t.

Berikut adalah beberapa contoh jaringan aliran untuk membantu memvisualisasikan kasus yang kurang jelas di mana proposisi E berlaku; pada gambar, area merah menunjukkan partisi-s, area biru mewakili partisi-t, dan busur hijau menunjukkan potongan st . Pada gambar kedua, aliran antara node A dan node B meningkat sedangkan aliran ke terminal node t tidak berubah.:

Akibat wajar: Tidak ada nilai aliran pemotongan st yang dapat melebihi kapasitas pemotongan st mana pun .

Proposisi F. (aliran maks, teorema potong min): Biarkan f menjadi aliran st . 3 kondisi berikut ini setara:

1. Terdapat sebuah st cut yang kapasitasnya sama dengan nilai aliran f .

2. f adalah aliran maksimum .

3. Tidak ada jalur augmentasi sehubungan dengan f .

Kondisi 1 menyiratkan kondisi 2 secara wajar. Kondisi 2 menyiratkan kondisi 3 karena keberadaan jalur tambahan menyiratkan adanya aliran dengan nilai yang lebih besar, bertentangan dengan maksimalitas f . Kondisi 3 menyiratkan kondisi 1: Biarkan C_s menjadi himpunan semua node yang dapat dicapai dari s dengan jalur augmentasi di grafik residual . Biarkan C_t menjadi busur yang tersisa , maka t harus berada di C_t (dengan asumsi kami). Busur yang melintasi dari C_s ke C_t kemudian membentuk potongan st yang hanya berisi busur a di mana a.datum.capacity = a.datum.flow atau a.datum.flow = 0.0 . Jika sebaliknya, maka simpul- simpul yang dihubungkan oleh busur dengan sisa kapasitas ke C_s akan berada dalam himpunan C_s karena akan ada jalur tambahan dari s ke simpul semacam itu. Aliran melintasi potongan pertama sama dengan kapasitas potongan pertama (karena busur dari C_s ke C_t memiliki aliran yang sama dengan kapasitas) dan juga dengan nilai aliran pertama (dengan proposisi E ).

Pernyataan aliran maks, teorema min cut ini menyiratkan pernyataan sebelumnya dari Flows in Networks.

Akibat wajar (properti integral): Ketika kapasitas adalah bilangan bulat, terdapat aliran maks bernilai bilangan bulat, dan algoritma Ford-Fulkerson menemukannya.

Bukti: Setiap jalur augmentasi meningkatkan aliran dengan bilangan bulat positif, kapasitas minimum yang tidak terpakai di busur 'push' dan arus di busur 'tarik' , yang semuanya selalu bilangan bulat positif.

Ini membenarkan deskripsi metode Ford-Fulkerson dari CLRS . Metodenya adalah terus menemukan jalur augmentasi dan menerapkan augment ke maxFlowSolution terbaru yang menghasilkan solusi yang lebih baik, hingga tidak ada lagi jalur augmentasi yang berarti bahwa solusi aliran maksimum terbaru adalah optimal .

Dari Ford-Fulkerson ke Edmonds-Karp

Pertanyaan yang tersisa mengenai pemecahan masalah aliran maksimum adalah:

1. Bagaimana seharusnya jalur tambahan dibangun?

2. Apakah metode akan berhenti jika kita menggunakan bilangan real dan bukan bilangan bulat?

3. Berapa lama waktu yang dibutuhkan untuk mengakhiri (jika ya)?

Algoritme Edmonds-Karp menetapkan bahwa setiap jalur tambahan dibangun oleh pencarian pertama yang luas (BFS) dari grafik sisa ; ternyata keputusan poin 1 di atas ini juga akan memaksa algoritma untuk berhenti (poin 2) dan memungkinkan untuk menentukan kompleksitas ruang dan waktu asimtotik.

Pertama, inilah implementasi BFS :

 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

Saya menggunakan deque dari modul koleksi python.

Untuk menjawab pertanyaan 2 di atas, saya akan memparafrasekan bukti lain dari Sedgewick dan Wayne: Proposisi G. Jumlah jalur augmenting yang dibutuhkan dalam algoritma Edmonds-Karp dengan N node dan A arc paling banyak NA/2 . Bukti: Setiap jalur augmenting memiliki busur bottleneck - busur yang dihapus dari grafik residual karena sesuai dengan busur 'push' yang menjadi terisi penuh atau busur 'tarik' yang melaluinya aliran menjadi 0. Setiap kali arc menjadi bottleneck arc , panjang dari setiap augmenting path yang melaluinya harus bertambah dengan faktor 2. Hal ini karena setiap node dalam suatu path mungkin muncul hanya sekali atau tidak sama sekali (dari definisi path ) karena path sedang dieksplorasi dari jalur terpendek ke terpanjang itu berarti bahwa setidaknya satu node lagi harus dikunjungi oleh jalur berikutnya yang melewati node bottleneck tertentu yang berarti tambahan 2 busur di jalur sebelum kita tiba di node . Karena jalur augmentasi paling panjang N setiap busur dapat berada di paling banyak N/2 jalur augmentasi , dan jumlah total jalur augmentasi paling banyak NA/2 .

Algoritma Edmonds-Karp dieksekusi dalam O(NA^2) . Jika paling banyak jalur NA/2 akan dieksplorasi selama algoritma dan menjelajahi setiap jalur dengan BFS adalah N+A maka suku yang paling signifikan dari produk dan karenanya kompleksitas asimtotiknya adalah O(NA^2) .

Biarkan mfp menjadi 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

Versi di atas tidak efisien dan memiliki kompleksitas yang lebih buruk daripada O(NA^2) karena ia membangun solusi aliran maksimum baru dan grafik residual baru setiap kali (daripada memodifikasi digraf yang ada seiring kemajuan algoritma). Untuk mendapatkan solusi O(NA^2) yang sebenarnya, algoritme harus mempertahankan digraf yang mewakili status masalah aliran maksimum dan grafik residual yang terkait. Jadi algoritme harus menghindari iterasi pada busur dan simpul yang tidak perlu dan memperbarui nilainya dan nilai terkait dalam grafik residual hanya jika diperlukan.

Untuk menulis algoritma Edmonds Karp yang lebih cepat, saya menulis ulang beberapa potongan kode dari atas. Saya harap membaca kode yang menghasilkan digraf baru dapat membantu dalam memahami apa yang terjadi. Dalam algoritma cepat, saya menggunakan beberapa trik baru dan struktur data Python yang tidak ingin saya bahas secara mendetail. Saya akan mengatakan bahwa a.fromNode dan a.toNode sekarang diperlakukan sebagai string dan uid ke node . Untuk kode ini, biarkan mfps menjadi 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

Berikut adalah visualisasi bagaimana algoritma ini memecahkan contoh jaringan aliran dari atas. Visualisasi menunjukkan langkah-langkah sebagaimana tercermin dalam digraf G yang mewakili jaringan aliran paling mutakhir dan sebagaimana tercermin dalam grafik sisa jaringan aliran tersebut. Jalur augmentasi dalam grafik residual ditampilkan sebagai jalur merah, dan digraf yang mewakili masalah himpunan simpul dan busur yang dipengaruhi oleh jalur augmentasi yang diberikan disorot dalam warna hijau. Dalam setiap kasus, saya akan menyoroti bagian grafik yang akan diubah (merah atau hijau) dan kemudian menunjukkan grafik setelah perubahan (hanya dalam warna hitam).

Berikut visualisasi lain tentang bagaimana algoritma ini memecahkan contoh jaringan aliran yang berbeda. Perhatikan bahwa yang ini menggunakan bilangan real dan berisi banyak busur dengan nilai fromNode dan toNode yang sama.

**Perhatikan juga bahwa karena Busur dengan ResidualDatum 'menarik' mungkin menjadi bagian dari Jalur Augmentasi, node yang terpengaruh di DiGraph Jaringan Terbang _mungkin tidak berada di jalur di G! .

Grafik Bipartit

Misalkan kita memiliki digraf G , G adalah bipartit jika node di G.setOfNodes dapat dipartisi menjadi dua set ( part_1 dan part_2 ) sehingga untuk sembarang busur a di G.setOfArcs tidak mungkin benar bahwa a.fromNode di part_1 dan a.toNode di part_1 . Juga tidak mungkin benar bahwa a.fromNode di part_2 dan a.toNode di part_2 .

Dengan kata lain G adalah bipartit jika dapat dipartisi menjadi dua set node sedemikian rupa sehingga setiap busur harus menghubungkan sebuah node dalam satu set ke node di set lainnya.

Menguji Bipartit

Misalkan kita memiliki digraf G , kita ingin menguji apakah itu bipartit . Kita bisa melakukannya di O(|G.setOfNodes|+|G.setOfArcs|) dengan mewarnai graf menjadi dua warna.

Pertama, kita perlu membangkitkan digraf baru H . Grafik ini akan memiliki himpunan simpul yang sama dengan G , tetapi akan memiliki lebih banyak busur daripada G . Setiap busur a di G akan membuat 2 busur di H ; busur pertama akan identik dengan a , dan busur kedua membalikkan direktur a ( 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)

Pencocokan dan Pencocokan Maksimum

Misalkan kita memiliki digraf G dan matching adalah subset dari busur dari G.setOfArcs . matching adalah pencocokan jika untuk dua busur a dan b dalam matching : len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . Dengan kata lain, tidak ada dua busur dalam pencocokan yang berbagi simpul .

Matching matching , adalah pencocokan maksimum jika tidak ada alt_matching lain yang cocok di G sehingga len(matching) < len(alt_matching) . Dengan kata lain, matching adalah pencocokan maksimum jika himpunan busur terbesar dari G.setOfArcs masih memenuhi definisi pencocokan (penambahan busur yang belum ada dalam pencocokan akan mematahkan definisi pencocokan ).

Pencocokan matching maksimum adalah pencocokan sempurna jika setiap untuk simpul n di G.setOfArcs terdapat busur a dalam matching di mana a.fromNode == n or a.toNode == n .

Pencocokan Bipartit Maksimum

Pencocokan maksimum bipartit adalah pencocokan maksimum pada digraf G yang bipartit .

Mengingat bahwa G adalah bipartit , masalah menemukan pencocokan bipartit maksimum dapat ditransformasikan menjadi masalah aliran maksimum yang dapat diselesaikan dengan algoritma Edmonds-Karp dan kemudian pencocokan bipartit maksimum dapat dipulihkan dari solusi ke masalah aliran maksimum .

Biarkan bipartition menjadi bipartisi dari G .

Untuk melakukan ini, saya perlu membuat digraph baru ( H ) dengan beberapa node baru ( H.setOfNodes ) dan beberapa busur baru ( H.setOfArcs ). H.setOfNodes berisi semua node di G.setOfNodes dan dua node lagi , s ( node ​​sumber ) dan t ( node ​​terminal ).

H.setOfArcs akan berisi satu busur untuk setiap G.setOfArcs . Jika busur a ada di G.setOfArcs dan a.fromNode ada di bipartition.firstPart dan a.toNode ada di bipartition.secondPart maka sertakan a di H (menambahkan FlowArcDatum(1,0) ).

Jika a.fromNode ada di bipartition.secondPart dan a.toNode ada di bipartition.firstPart , maka sertakan Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) di H.setOfArcs .

Definisi graf bipartit memastikan bahwa tidak ada busur yang menghubungkan setiap node di mana kedua node berada di partisi yang sama. H.setOfArcs juga berisi busur dari node s ke setiap node di bipartition.firstPart . Terakhir, H.setOfArcs berisi busur setiap simpul di bipartition.secondPart ke simpul t . a.datum.capacity = 1 untuk semua a di H.setOfArcs .

Pertama partisi node di G.setOfNodes dua set terpisah ( part1 dan part2 ) sedemikian rupa sehingga tidak ada busur di G.setOfArcs yang diarahkan dari satu set ke set yang sama (partisi ini dimungkinkan karena G adalah bipartit ). Selanjutnya, tambahkan semua busur di G.setOfArcs yang diarahkan dari part1 ke part2 ke dalam H.setOfArcs . Kemudian buat simpul sumber tunggal s dan simpul terminal tunggal t dan buat beberapa busur lagi

Kemudian, buat 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

Penutup Node Minimal

Penutup simpul dalam digraf G adalah kumpulan simpul ( cover ) dari G.setOfNodes sedemikian rupa sehingga untuk setiap busur a dari G.setOfArcs ini harus benar: (a.fromNode in cover) or (a.toNode in cover) .

Penutup simpul minimal adalah himpunan simpul terkecil yang mungkin dalam graf yang masih merupakan penutup simpul . Teorema Konig menyatakan bahwa dalam graf bipartit , ukuran pencocokan maksimum pada grafik tersebut sama dengan ukuran penutup simpul minimal , dan ini menyarankan bagaimana penutup simpul dapat dipulihkan dari pencocokan maksimum :

Misalkan kita memiliki bipartisi bipartition dan pencocokan matching maksimum . Tentukan digraf baru H , H.setOfNodes=G.setOfNodes , busur di H.setOfArcs adalah gabungan dari dua himpunan.

Set pertama adalah busur a dalam matching , dengan perubahan bahwa jika a.fromNode in bipartition.firstPart dan a.toNode in bipartition.secondPart maka a.fromNode dan a.toNode ditukar dalam busur yang dibuat memberikan a.datum.inMatching=True busur seperti itu a.datum.inMatching=True untuk menunjukkan bahwa atribut tersebut diturunkan dari busur dalam .

Himpunan kedua adalah arc a NOT in matching , dengan perubahan bahwa jika a.fromNode in bipartition.secondPart dan a.toNode in bipartition.firstPart maka a.fromNode dan a.toNode ditukar di arc yang dibuat (berikan arc tersebut a.datum.inMatching=False Atribut salah).

Selanjutnya, jalankan depth first search (DFS) mulai dari setiap node n di bipartition.firstPart yang bukan n == a.fromNode atau n == a.toNodes untuk setiap arc a dalam matching . Selama DFS, beberapa node dikunjungi dan beberapa tidak (simpan informasi ini di bidang n.datum.visited ). Penutup simpul minimum adalah gabungan simpul {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } dan simpul {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

Ini dapat ditunjukkan untuk memimpin dari pencocokan maksimum ke penutup simpul minimal dengan bukti oleh kontradiksi, ambil beberapa busur a seharusnya tidak tercakup dan pertimbangkan keempat kasus mengenai apakah a.fromNode dan a.toNode termasuk (apakah sebagai toNode atau fromNode ) ke busur apa pun dalam pencocokan matching . Setiap kasus mengarah ke kontradiksi karena urutan DFS mengunjungi node dan fakta bahwa matching adalah pencocokan maksimum .

Misalkan kita memiliki fungsi untuk menjalankan langkah-langkah ini dan mengembalikan himpunan simpul yang terdiri dari penutup simpul minimal ketika diberi digraf G , dan pencocokan matching maksimum :

 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

Masalah Penugasan Linier

Masalah penugasan linier terdiri dari menemukan pencocokan bobot maksimum dalam grafik bipartit berbobot.

Masalah seperti yang di awal posting ini dapat dinyatakan sebagai masalah penugasan linier . Mengingat satu set pekerja, satu set tugas, dan fungsi yang menunjukkan profitabilitas penugasan satu pekerja untuk satu tugas, kami ingin memaksimalkan jumlah semua tugas yang kami buat; ini adalah masalah penugasan linier .

Asumsikan bahwa jumlah tugas dan pekerja sama, meskipun saya akan menunjukkan bahwa asumsi ini mudah dihilangkan. Dalam implementasinya, saya merepresentasikan bobot busur dengan atribut a.datum.weight untuk busur a .

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

Algoritma Kuhn-Munkres

Algoritma Kuhn-Munkres memecahkan masalah penugasan linier . Implementasi yang baik dapat memakan waktu O(N^{4}) , (di mana N adalah jumlah node dalam digraf yang mewakili masalah). Implementasi yang lebih mudah dijelaskan membutuhkan O(N^{5}) (untuk versi yang meregenerasi DiGraphs ) dan O(N^{4}) untuk (untuk versi yang mempertahankan DiGraphs ). Ini mirip dengan dua implementasi berbeda dari algoritma Edmonds-Karp .

Untuk deskripsi ini, saya hanya bekerja dengan grafik bipartit lengkap (di mana setengah node berada di satu bagian bipartisi dan setengah lainnya di bagian kedua). Dalam pekerja, motivasi tugas ini berarti ada pekerja sebanyak tugas.

Ini sepertinya kondisi yang signifikan (bagaimana jika set ini tidak sama!) tetapi mudah untuk memperbaiki masalah ini; Saya berbicara tentang bagaimana melakukannya di bagian terakhir.

Versi algoritme yang dijelaskan di sini menggunakan konsep busur bobot nol yang berguna. Sayangnya, konsep ini hanya masuk akal ketika kita menyelesaikan minimalisasi (jika alih-alih memaksimalkan keuntungan dari penugasan tugas pekerja kita, kita malah meminimalkan biaya penugasan tersebut).

Untungnya, mudah untuk mengubah masalah penugasan linier maksimum menjadi masalah penugasan linier minimum dengan mengatur setiap busur a bobot ke Ma.datum.weight di mana M=max({a.datum.weight for a in G.setOfArcs}) . Solusi dari masalah pemaksimalan awal akan identik dengan solusi masalah meminimalkan setelah bobot busur diubah. Jadi untuk sisanya, asumsikan bahwa kita membuat perubahan ini.

Algoritma Kuhn-Munkres menyelesaikan pencocokan bobot minimum dalam graf bipartit berbobot dengan urutan pencocokan maksimum dalam graf bipartit tak berbobot. Jika a kami menemukan kecocokan sempurna pada representasi digraf dari masalah penugasan linier , dan jika bobot setiap busur dalam pencocokan adalah nol, maka kami telah menemukan pencocokan bobot minimum karena pencocokan ini menunjukkan bahwa semua simpul dalam digraf telah dicocokkan dengan busur dengan biaya serendah mungkin (tidak ada biaya yang bisa lebih rendah dari 0, berdasarkan definisi sebelumnya).

Tidak ada busur lain yang dapat ditambahkan ke pencocokan (karena semua simpul sudah cocok) dan tidak ada busur yang harus dihapus dari pencocokan karena busur pengganti yang mungkin akan memiliki nilai bobot paling tidak sama besar.

Jika kita menemukan kecocokan maksimum dari subgraf G yang hanya berisi busur berbobot nol , dan itu bukan pencocokan sempurna , kita tidak memiliki solusi lengkap (karena pencocokannya tidak sempurna ). Namun, kita dapat menghasilkan digraf baru H dengan mengubah bobot busur di G.setOfArcs sedemikian rupa sehingga busur berbobot 0 baru muncul dan solusi optimal H sama dengan solusi optimal G . Karena kami menjamin bahwa setidaknya satu busur berbobot nol dihasilkan pada setiap iterasi, kami menjamin bahwa kami akan mencapai pencocokan sempurna dalam tidak lebih dari |G.setOfNodes|^{2}=N^{2} iterasi tersebut.

Misalkan dalam bipartition bipartition , bipartition.firstPart berisi node yang mewakili pekerja, dan bipartition.secondPart mewakili node yang mewakili tugas.

Algoritma dimulai dengan menghasilkan digraf baru H . H.setOfNodes = G.setOfNodes . Beberapa busur di H dihasilkan dari simpul n di bipartition.firstPart . Setiap simpul n tersebut menghasilkan busur b di H.setOfArcs untuk setiap busur a di bipartition.G.setOfArcs di mana a.fromNode = n atau a.toNode = n , b=Arc(a.fromNode, a.toNode, a.datum.weight - z) di mana z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

Lebih banyak busur di H dihasilkan dari simpul n di bipartition.secondPart . Setiap simpul n tersebut menghasilkan busur b di H.setOfArcs untuk setiap busur a di bipartition.G.setOfArcs di mana a.fromNode = n atau a.toNode = n , b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) where z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: Selanjutnya, bentuk digraf baru K yang hanya terdiri dari busur berbobot nol dari H , dan simpul yang datang pada busur tersebut . Bentuklah bipartition pada node di K , lalu gunakan solve_mbm( bipartition ) untuk mendapatkan pencocokan ( matching ) yang maksimal pada K . Jika matching adalah pencocokan sempurna di H ( busur dalam matching terjadi pada semua node di H.setOfNodes ) maka matching adalah solusi optimal untuk masalah penugasan linier .

Jika tidak, jika matching tidak sempurna , buat penutup simpul minimal K menggunakan node_cover = get_min_node_cover(matching, bipartition(K)) . Selanjutnya, definisikan z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . Tentukan 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)} Simbol != pada ekspresi sebelumnya bertindak sebagai operator XOR Kemudian arcs = arcs1.union(arcs2.union(arcs3)) Selanjutnya, H=DiGraph(nodes,arcs) Kembali ke label KMA.Algoritma berlanjut sampai diperoleh pencocokan sempurna.Pencocokan ini juga merupakan solusi dari masalah penugasan linier .

 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

Implementasi ini adalah O(N^{5}) karena menghasilkan pencocokan matching maksimum baru pada setiap iterasi; mirip dengan dua implementasi Edmonds-Karp sebelumnya, algoritma ini dapat dimodifikasi sehingga dapat melacak pencocokan dan menyesuaikannya dengan cerdas untuk setiap iterasi. Ketika ini selesai, kompleksitasnya menjadi O(N^{4}) . Versi yang lebih maju dan lebih baru dari algoritme ini (memerlukan beberapa struktur data yang lebih canggih) dapat berjalan di O(N^{3}) . Detail implementasi yang lebih sederhana di atas dan implementasi yang lebih maju dapat ditemukan di posting ini yang memotivasi posting blog ini.

Tak satu pun dari operasi pada bobot busur mengubah tugas akhir yang dikembalikan oleh algoritma. Inilah alasannya: Karena grafik input kami selalu merupakan grafik bipartit lengkap , solusi harus memetakan setiap node dalam satu partisi ke node lain di partisi kedua, melalui busur antara dua node ini. Perhatikan bahwa operasi yang dilakukan pada bobot busur tidak pernah mengubah urutan (diurutkan berdasarkan bobot) dari insiden busur pada simpul tertentu.

Jadi, ketika algoritme berakhir pada pencocokan bipartit lengkap yang sempurna, setiap simpul diberi busur berbobot nol , karena urutan relatif busur dari simpul itu tidak berubah selama algoritma, dan karena busur berbobot nol adalah busur termurah yang mungkin dan pencocokan bipartit lengkap yang sempurna menjamin bahwa satu busur seperti itu ada untuk setiap simpul . Ini berarti bahwa solusi yang dihasilkan memang sama dengan solusi dari masalah penugasan linier asli tanpa modifikasi bobot busur .

Tugas Tidak Seimbang

Sepertinya algoritme ini sangat terbatas karena seperti yang dijelaskan, ia hanya beroperasi pada grafik bipartit lengkap (di mana setengah node berada di satu bagian bipartisi dan setengah lainnya di bagian kedua). Pada pekerja, motivasi tugas ini berarti bahwa ada pekerja sebanyak tugas (tampaknya cukup membatasi).

Namun, ada transformasi mudah yang menghilangkan batasan ini. Misalkan ada lebih sedikit pekerja daripada tugas, kami menambahkan beberapa pekerja dummy (cukup untuk membuat grafik yang dihasilkan menjadi grafik bipartit lengkap ). 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:

Hanya itu saja. 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.

Bacaan Lebih Lanjut di Blog Teknik Toptal:

• Ilmu Data Grafik Dengan Python/NetworkX