التدفق الأقصى ومشكلة التخصيص الخطي

إليك مشكلة: عملك يعين مقاولين للوفاء بالعقود. تقوم بالاطلاع على قوائم المرشحين الخاصة بك وتحديد المقاولين المتاحين للمشاركة لمدة شهر واحد وتنظر في العقود المتاحة لديك لمعرفة أي منهم للمهام التي تستغرق شهرًا واحدًا. بالنظر إلى أنك تعرف مدى فعالية كل مقاول في تنفيذ كل عقد ، كيف يمكنك تعيين مقاولين لزيادة الفعالية الإجمالية لهذا الشهر؟

هذا مثال على مشكلة التخصيص ، ويمكن حل المشكلة بالخوارزمية الهنغارية الكلاسيكية.

الخوارزمية المجرية (المعروفة أيضًا باسم خوارزمية Kuhn-Munkres) هي خوارزمية متعددة الحدود تزيد من مطابقة الوزن إلى أقصى حد في رسم بياني ثنائي الأجزاء. هنا ، يمكن نمذجة المقاولين والعقود كرسم بياني ثنائي ، مع فعاليتهم كأوزان للحواف بين المقاول وعقد العقد.

في هذه المقالة ، ستتعرف على تطبيق الخوارزمية المجرية التي تستخدم خوارزمية Edmonds-Karp لحل مشكلة التعيين الخطي. سوف تتعلم أيضًا كيف أن خوارزمية Edmonds-Karp هي تعديل طفيف لطريقة Ford-Fulkerson وكيف أن هذا التعديل مهم.

مشكلة التدفق الأقصى

يمكن وصف مشكلة التدفق الأقصى نفسها بشكل غير رسمي بأنها مشكلة نقل بعض السوائل أو الغاز عبر شبكة من الأنابيب من مصدر واحد إلى طرف واحد. يتم ذلك بافتراض أن الضغط في الشبكة كافٍ لضمان عدم بقاء السائل أو الغاز في أي طول من الأنابيب أو تركيبات الأنابيب (تلك الأماكن التي تلتقي فيها أطوال مختلفة من الأنابيب).

من خلال إجراء بعض التغييرات على الرسم البياني ، يمكن تحويل مشكلة التخصيص إلى مشكلة التدفق الأقصى.

مقدمات

تنشأ الأفكار اللازمة لحل هذه المشكلات في العديد من التخصصات الرياضية والهندسية ، وغالبًا ما تُعرف المفاهيم المتشابهة بأسماء مختلفة ويتم التعبير عنها بطرق مختلفة (على سبيل المثال ، مصفوفات التقارب وقوائم الجوار). نظرًا لأن هذه الأفكار مقصورة على فئة معينة ، يتم اتخاذ الخيارات فيما يتعلق بكيفية تحديد هذه المفاهيم بشكل عام لأي مكان محدد.

لن تفترض هذه المقالة أي معرفة مسبقة تتجاوز نظرية المجموعة التمهيدية الصغيرة.

تمثل التطبيقات في هذا المنشور المشكلات على أنها رسوم بيانية موجهة (Digraph).

ديجرافس

يحتوي الرسم البياني على سمتين ، setOfNodes و setOfArcs . كل من هاتين السمتين عبارة عن مجموعات (مجموعات غير مرتبة). في كتل التعليمات البرمجية في هذا المنشور ، أستخدم مجموعة لغة Python بالفعل ، لكن هذه التفاصيل ليست مهمة بشكل خاص.

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

(ملاحظة: هذا ، وجميع الأكواد الأخرى الواردة في هذه المقالة ، مكتوبة في Python 3.6.)

العقد

تتكون العقدة n من سمتين:

• n.uid : معرّف فريد.

  هذا يعني أنه بالنسبة لأي عقدتين x و y ،

 x.uid != y.uid

• n.datum : هذا يمثل أي كائن بيانات.

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

أقواس

يتكون القوس a من ثلاث سمات:

• a.fromNode : هذه عقدة ، على النحو المحدد أعلاه.

• a.toNode : هذه عقدة على النحو المحدد أعلاه.

• a.datum : هذا يمثل أي كائن بيانات.

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

تمثل مجموعة الأقواس في Digraph علاقة ثنائية على العقد في Digraph . يشير وجود القوس a إلى وجود علاقة بين a.fromNode و a.toNode .

في الرسم البياني الموجه (على عكس الرسم البياني غير الموجه) ، لا يعني وجود علاقة بين a.fromNode و a.toNode وجود علاقة مماثلة بين a.toNode و a.fromNode .

هذا لأنه في الرسم البياني غير المباشر ، فإن العلاقة التي يتم التعبير عنها ليست بالضرورة متناظرة.

ديجرافس

يمكن استخدام العقد والأقواس لتعريف الرسم البياني ، ولكن للراحة ، في الخوارزميات أدناه ، سيتم تمثيل Digraph باستخدام القاموس.

إليك طريقة يمكنها تحويل تمثيل الرسم البياني أعلاه إلى تمثيل معجم مشابه لذلك:

 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

وإليك طريقة أخرى تحولها إلى قاموس من القواميس ، وهي عملية أخرى ستكون مفيدة:

 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

عندما يتحدث المقال عن digraph كما يمثله القاموس ، فإنه G_as_dict للإشارة إليه.

أحيانًا يكون من المفيد إحضار عقدة من digraph G بواسطتها عبر uid (المعرف الفريد):

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

عند تعريف الرسوم البيانية ، يستخدم الأشخاص أحيانًا المصطلحين " عقدة " و "قمة الرأس" للإشارة إلى نفس المفهوم ؛ وينطبق الشيء نفسه على المصطلحين قوس وحافة.

هناك تمثيلان شائعان للرسم البياني في بايثون ، وهما هذا الذي يستخدم القواميس والآخر يستخدم كائنات لتمثيل الرسوم البيانية. التمثيل في هذا المنشور يقع في مكان ما بين هذين التمثيلين الشائعين الاستخدام.

هذا هو تمثيل ديجراف الخاص بي. هناك الكثير مثله ، لكن هذا لي.

مناحي ومسارات

دع S_Arcs يكون تسلسلًا محدودًا (مجموعة مرتبة) من الأقواس في S_Arcs G بحيث إذا كان a أي قوس في S_Arcs باستثناء الأخير ، و b يتبع a في التسلسل ، فيجب أن يكون هناك عقدة n = a.fromNode G.setOfNodes مثل أن a.toNode = b.fromNode .

بدءًا من القوس الأول في S_Arcs ، واستمرارًا حتى آخر قوس في S_Arcs ، اجمع (بالترتيب الذي تمت مواجهته) جميع العقد n كما هو محدد أعلاه بين كل قوسين متتاليين في S_Arcs . قم بتسمية المجموعة المرتبة للعقد التي تم جمعها أثناء هذه العملية 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

• إذا ظهرت أي عقدة أكثر من مرة في التسلسل S_Nodes ، فاتصل S_Arcs a Walk on digraph G

• خلاف ذلك ، قم باستدعاء S_Arcs بمسار من list(S_Nodes)[0] إلى list(S_Nodes)[-1] على digraph G

عقدة المصدر

نداء العقدة هي عقدة مصدر s digraph G إذا كانت s في G.setOfNodes و G.setOfArcs لا تحتوي a قوس بحيث أن 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

عقدة طرفية

نداء العقدة t عقدة طرفية في digraph G إذا كانت t في G.setOfNodes و G.setOfArcs لا تحتوي a قوس بحيث أن 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

التخفيضات و st التخفيضات

القطع cut من digraph G هو مجموعة فرعية من الأقواس من G.setOfArcs والتي تقسم مجموعة العقد G.setOfNodes في G G متصل إذا كانت كل عقدة n في G.setOfNodes a.fromNode != a.toNode قوس a على n = a.toNode n = a.fromNode G.setOfArcs

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

يشير التعريف أعلاه إلى مجموعة فرعية من الأقواس ، ولكن يمكنه أيضًا تحديد قسم من عُقد G.setOfNodes .

بالنسبة إلى الوظائف predecessors_of و successors_of ، فإن n عبارة عن عقدة في مجموعة G.setOfNodes من digraph G ، cut عبارة عن قطع 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

دع cut يكون قطعًا من digraph 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 عبارة عن قطع من digraph G إذا: (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 اسم xy cut إذا (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y) . عندما تكون العقدة x في cut xy هي عقدة مصدر وتكون العقدة y في القطع xy عقدة طرفية ، فإن هذا القطع يسمى st cut .

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

شبكات التدفق

يمكنك استخدام digraph G لتمثيل شبكة التدفق.

قم بتعيين كل عقدة n ، n.datum يكون n FlowNodeDatum G.setOfNodes

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

قم بتعيين كل قوس a ، حيث يكون a في G.setOfArcs و a.datum الذي يمثل FlowArcDatum .

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

flowNodeDatum.flowIn و flowNodeDatum.flowOut أرقام حقيقية موجبة.

flowArcDatum.capacity و flowArcDatum.flow هي أيضًا أرقام حقيقية موجبة.

لكل عقدة n في 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})

تمثل Digraph G الآن شبكة تدفق .

يشير تدفق G إلى تدفق a.flow لجميع الأقواس a في G

تدفقات مجدية

دع digraph G تمثل شبكة تدفق .

تتمتع شبكة التدفق التي يمثلها G بتدفقات مجدية إذا:

1. لكل n عقدة في G.setOfNodes باستثناء العقد المصدر والعقد الطرفية : n.datum.flowIn = n.datum.flowOut .

2. لكل قوس a G.setOfNodes : a.datum.capacity <= a.datum.flow .

يسمى الشرط 1 قيد الحفظ.

يسمى الشرط 2 قيد القدرة.

قدرة القطع

قدرة القطع t st cut stCut مع عقدة المصدر والعقدة الطرفية s لشبكة التدفق الممثلة بواسطة digraph G هي:

 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

الحد الأدنى من السعة المقطوعة

لنفترض stCut = stCut(s,t,cut) يكون قطعًا من شبكة التدفق يمثلها digraph G

stCut هو الحد الأدنى لسعة قطع شبكة التدفق التي يمثلها G في حالة عدم وجود stCutCompetitor في شبكة التدفق هذه مثل:

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

تجريد التدفقات بعيدا

أود أن أشير إلى digraph الذي سيكون نتيجة أخذ digraph G وتجريد جميع بيانات التدفق من جميع العقد في G.setOfNodes وأيضًا جميع الأقواس في 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)

مشكلة التدفق القصوى

تمثل شبكة التدفق على شكل digraph G ، عقدة مصدر في s G.setOfNodes الطرفية t في G.setOfNodes ، G يمكن أن تمثل مشكلة تدفق قصوى إذا:

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

قم بتسمية هذا التمثيل:

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

حيث sourceNodeUid = s.uid و terminalNodeUid = t.uid و maxFlowProblemStateUid معرفًا لمثيل المشكلة.

أقصى حل للتدفق

دع maxFlowProblem يمثل مشكلة التدفق الأقصى . يمكن تمثيل حل maxFlowProblem من خلال شبكة تدفق ممثلة في شكل Digraph H

Digraph H هو حل عملي لمشكلة التدفق الأقصى في python maxFlowProblem إذا:

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

2. H عبارة عن شبكة تدفق ولها تدفقات مجدية .

إذا كان بالإضافة إلى 1 و 2:

1. لا يمكن أن يكون هناك شبكة تدفق أخرى ممثلة بواسطة digraph K مثل strip_flows(G) == strip_flows(K) و find_node_by_uid(t.uid,G).flowIn < find_node_by_uid(t.uid,K).flowIn .

إذن H هو الحل الأمثل لمشكلة maxFlowProblem .

بعبارة أخرى ، يمكن تمثيل حل أقصى تدفق ممكن بواسطة Digraph ، والتي:

1. مطابق لـ digraph G لمشكلة الحد الأقصى للتدفق المقابل باستثناء أن n.datum.flowIn و n.datum.flowOut و a.datum.flow لأي من العقد والأقواس قد تكون مختلفة.

2. يمثل شبكة تدفق ذات تدفقات مجدية .

ويمكن أن يمثل حل التدفق الأقصى الأمثل إذا كان بالإضافة إلى ذلك:

1. يكون flowIn الخاص بالعقدة المقابلة للعقدة الطرفية في مشكلة التدفق الأقصى كبيرًا قدر الإمكان (عندما لا يزال الشرطان 1 و 2 مستوفين).

إذا كان digraph H يمثل حل تدفق أقصى ممكن : find_node_by_uid(s.uid,H).flowOut = find_node_by_uid(t.uid,H).flowIn هذا يتبع من الحد الأقصى للتدفق ، نظرية القطع الدقيقة (الموضحة أدناه). بشكل غير رسمي ، نظرًا لأنه يُفترض أن يكون لدى H تدفقات مجدية ، فهذا يعني أنه لا يمكن "إنشاء" التدفق (باستثناء عقدة المصدر s ولا "إتلافه" (باستثناء العقدة الطرفية t ) أثناء عبور أي عقدة (أخرى) ( قيود الحفظ ).

نظرًا لأن مشكلة التدفق الأقصى تحتوي فقط على عقدة مصدر واحدة s طرفية واحدة ، يجب "تدمير" كل التدفق "الذي تم إنشاؤه" عند t s لا تحتوي شبكة التدفق على تدفقات ممكنة t كان من الممكن انتهاك قيد الحفظ ).

دع digraph H يمثل حل تدفق أقصى ممكن ؛ تسمى القيمة أعلاه قيمة التدفق st لـ H

يترك:

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

هذا يعني أن mfps هي حالة لاحقة لـ maxFlowProblem ، مما يعني فقط أن mfps يشبه maxFlowProblem باستثناء أن قيم a.flow للأقواس a maxFlowProblem.setOfArcs قد تكون مختلفة عن a.flow للأقواس a 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

فيما يلي تصوُّر لـ mfps مع maxFlowProb المرتبط به. كل قوس a في الصورة له ملصق ، هذه الملصقات هي a.datum.flowFrom / a.datum.flowTo ، كل عقدة n في الصورة لها ملصق ، وهذه التسميات هي n.uid {n.datum.flowIn / a.datum.flowOut} .

تدفق قطع st

دع mfps يمثل MaxFlowProblemState ودع stCut يمثل قطعًا من mfps.G يتم تعريف تدفق القطع لـ stCut :

 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 هو مجموع التدفقات من القسم الذي يحتوي على العقدة المصدر إلى القسم الذي يحتوي على العقدة الطرفية مطروحًا منه مجموع التدفقات من القسم الذي يحتوي على العقدة الطرفية إلى القسم الذي يحتوي على العقدة المصدر .

الحد الأقصى للتدفق ، الحد الأدنى للقطع

دع maxFlowProblem يمثل مشكلة التدفق الأقصى ودع الحل لمشكلة maxFlowProblem يمثله شبكة تدفق ممثلة على شكل digraph H

دع minStCut هو الحد الأدنى لسعة قطع شبكة التدفق التي يمثلها maxFlowProblem.G .

نظرًا لأن التدفق في أقصى تدفق ينشأ في عقدة مصدر واحدة فقط وينتهي عند عقدة طرفية واحدة ، وبسبب قيود السعة وقيود الحفظ ، نعلم أن كل التدفق الذي يدخل maxFlowProblem.terminalNodeUid يجب أن يتجاوز أي قطع st ، على وجه الخصوص يجب أن minStCut . هذا يعنى:

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

حل مشكلة التدفق الأقصى

الفكرة الأساسية لحل مشكلة التدفق الأقصى maxFlowProblem هي البدء بحل أقصى تدفق يمثله digraph H يمكن أن تكون نقطة البداية هذه H = strip_flows(maxFlowProblem.G) . تتمثل K بعد ذلك في استخدام H ومن خلال بعض K a.datum.flow لقيم تدفق البيانات لبعض الأقواس a في مجموعة H.setOfArcs و get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) . طالما استمرت هذه العملية ، فإن الجودة ( get_flow_value(K, maxFlowProblem) ) الخاصة بأحدث حل للتدفق الأقصى ( K ) أفضل من أي حل أقصى آخر تم العثور عليه. إذا وصلت العملية إلى نقطة تعرف أنه لا يوجد تحسين آخر ممكن ، يمكن أن تنتهي العملية وستعيد الحل الأمثل للتدفق الأقصى .

الوصف أعلاه عام ويتخطى العديد من الأدلة مثل ما إذا كانت هذه العملية ممكنة أو المدة التي قد تستغرقها ، سأقدم بعض التفاصيل الإضافية والخوارزمية.

نظرية التدفق الأقصى ، الحد الأدنى للقطع

من كتاب Flows in Networks by Ford و Fulkerson ، فإن بيان التدفق الأقصى ، نظرية القطع الأدنى (نظرية 5.1) هو:

بالنسبة لأي شبكة ، تكون قيمة التدفق القصوى من s إلى t مساوية لسعة القطع الدنيا لجميع عمليات القطع التي تفصل بين s و t .

باستخدام التعريفات الواردة في هذا المنشور ، والتي تترجم إلى:

الحل الأمثل لمشكلة maxFlowProblem التي تمثلها شبكة التدفق الممثلة كـ digraph H هو الحل الأمثل إذا:

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

أنا أحب هذا الدليل على النظرية وويكيبيديا لديها دليل آخر.

يتم استخدام نظرية max flow، min cut لإثبات صحة واكتمال طريقة Ford-Fulkerson .

سأقدم أيضًا دليلًا على النظرية في القسم بعد زيادة المسارات .

طريقة Ford-Fulkerson وخوارزمية Edmonds-Karp

تعرف CLRS طريقة Ford-Fulkerson على هذا النحو (القسم 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

الرسم البياني المتبقي

يمكن تمثيل الرسم البياني المتبقي لشبكة التدفق المُمَثَّل على أنه digraph G على أنه digraph 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) مجموع a.datum.capacity لكل الأقواس في المجموعة الفرعية لـ G.setOfArcs حيث يكون القوس a في المجموعة الفرعية إذا كانت a.fromNode = n و a.toNode = u .

• agg_n_to_u_cap(n,u,G_as_dict) مجموع a.datum.flow لكل الأقواس في المجموعة الفرعية لـ G.setOfArcs حيث يكون القوس a في المجموعة الفرعية إذا كانت a.fromNode = n و a.toNode = u .

باختصار ، يمثل الرسم البياني المتبقي G_f بعض الإجراءات التي يمكن إجراؤها على الرسم البياني G

يمكن لكل زوج من العقد n,u في G.setOfNodes من شبكة التدفق التي يمثلها digraph G ، توليد 0 أو 1 أو 2 قوس في الرسم البياني المتبقي G_f لـ G

1. لا يُنشئ الزوج n,u أي أقواس في G_f إذا لم يكن هناك قوس a في G.setOfArcs مثل أن a.fromNode = n و a.toNode = u .

2. يولد الزوج n,u القوس a في G_f.setOfArcs حيث يمثل a قوسًا يسمى قوس تدفق الدفع من n إلى u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) إذا كان n_to_u_cap_sum > n_to_u_flow_sum .

3. يولد الزوج n,u القوس a في G_f.setOfArcs حيث يمثل a قوسًا يسمى قوس تدفق السحب من n إلى u a = Arc(n,u,datum=ResidualNode(n_to_u_cap_sum - n_to_u_flow_sum)) إذا كان n_to_u_flow_sum > 0.0 .

• a.toNode = u كل قوس تدفق دفع a G_f.setOfArcs إجراء a.fromNode = n G.setOfArcs x <= n_to_u_cap_sum - n_to_u_flow_sum a.toNode = u .

• يمثل كل قوس تدفق سحب في G_f.setOfArcs إجراء طرح إجمالي تدفق x <= n_to_u_flow_sum إلى أقواس في المجموعة الفرعية لـ G.setOfArcs حيث يكون القوس a في المجموعة الفرعية إذا كانت a.fromNode = n و a.toNode = u .

قد يؤدي تنفيذ إجراء دفع أو سحب فردي من G_f على الأقواس القابلة للتطبيق في G إلى إنشاء شبكة تدفق بدون تدفقات ممكنة لأن قيود السعة أو قيود الحفظ قد تنتهك في شبكة التدفق المتولدة.

فيما يلي تصور للرسم البياني المتبقي للتخيل المثال السابق لحل أقصى تدفق ، في التصور يمثل كل قوس a a.residualCapacity .

زيادة المسار

اجعل maxFlowProblem مشكلة تدفق قصوى ، G_f = get_residual_graph_of(G) هو الرسم البياني المتبقي لـ maxFlowProblem.G .

مسار augmentingPath لـ maxFlowProblem هو أي مسار من find_node_by_uid(maxFlowProblem.sourceNode,G_f) find_node_by_uid(maxFlowProblem.terminalNode,G_f) .

اتضح أنه يمكن تطبيق مسار augmentingPath على حل أقصى تدفق يمثله digraph H لتوليد حل أقصى تدفق آخر يمثله digraph K حيث get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) إذا لم يكن H هو الأمثل .

إليك الطريقة:

 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

في ما سبق ، TOL هي بعض قيمة التسامح لتقريب قيم التدفق في الشبكة. هذا لتجنب عدم الدقة المتتالية لحسابات الفاصلة العائمة. لذلك ، على سبيل المثال ، استخدمت TOL = 10 إلى 10 أرقام معنوية.

لنفترض أن K = augment(augmentingPath, H) ، ثم K يمثل حل أقصى تدفق ممكن لـ maxFlowProblem . لكي تكون العبارة صحيحة ، يجب أن يكون لشبكة التدفق التي يمثلها K تدفقات مجدية (لا تنتهك قيود السعة أو قيد الحفظ .

إليك السبب: في الطريقة أعلاه ، كل عقدة تمت إضافتها إلى شبكة التدفق الجديدة ممثلة بواسطة digraph K هي إما نسخة طبق الأصل من عقدة من digraph H أو عقدة n لديها نفس الرقم الذي تمت إضافته إلى n.datum.flowIn الخاص بها. n.datum.flowOut . هذا يعني أن قيد الحفظ يتم استيفائه في K طالما أنه كان مقتنعًا في H تم استيفاء قيد الحفظ لأننا نتحقق صراحة من أن أي قوس a في الشبكة له a.datum.flow <= a.datum.capacity ؛ وهكذا ، طالما أن الأقواس من مجموعة H.setOfArcs التي تم نسخها دون تعديل في K.setOfArcs لا تنتهك قيود السعة ، فإن K لا تنتهك قيود السعة .

من الصحيح أيضًا أن get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) إذا لم يكن H هو الأمثل .

وإليك السبب: لكي يوجد مسار augmentingPath في المسار المعزز في G_f للرسم البياني المتبقي G_f لمشكلة التدفق الأقصى maxFlowProblem يجب أن يكون القوس الأخير a augmentingPath قوسًا "دفعًا" ويجب أن يحتوي على a.toNode == maxFlowProblem.terminalNode . يُعرَّف المسار المعزز بأنه المسار الذي ينتهي عند العقدة الطرفية لمشكلة التدفق الأقصى التي يكون مسار زيادة لها. من تعريف الرسم البياني المتبقي ، من الواضح أن القوس الأخير في مسار التعزيز على هذا الرسم البياني المتبقي يجب أن يكون قوسًا "دفعًا" لأن أي قوس " سحب" b في مسار الزيادة سيكون b.toNode == maxFlowProblem.terminalNode و b.fromNode != maxFlowProblem.terminalNode من تعريف المسار . بالإضافة إلى ذلك ، من تعريف المسار ، من الواضح أن العقدة الطرفية يتم تعديلها مرة واحدة فقط بواسطة طريقة augment . وبالتالي فإن maxFlowProblem.terminalNode.flowIn augment واحدة بالضبط وتزيد من قيمة maxFlowProblem.terminalNode.flowIn لأن القوس الأخير في augmentingPath يجب أن يكون القوس الذي يتسبب في التعديل في maxFlowProblem.terminalNode.flowIn أثناء augment . من تعريف الزيادة كما تنطبق على أقواس "الدفع" ، يمكن فقط augment maxFlowProblem.terminalNode.flowIn ، وليس إنقاصها.

بعض البراهين من Sedgewick و Wayne

يحتوي كتاب الخوارزميات ، الطبعة الرابعة لروبرت سيدجويتش وكيفن واين ، على بعض البراهين الرائعة والقصيرة (الصفحات 892-894) التي ستكون مفيدة. سأعيد إنشائها هنا ، على الرغم من أنني سأستخدم لغة تتلاءم مع التعريفات السابقة. ملصقاتي الخاصة بالبراهين هي نفسها الموجودة في كتاب Sedgewick.

Proposition E: لأي digraph H يمثل حل تدفق أقصى ممكن لمشكلة تدفق أقصى maxFlowProblem ، لأي stCut get_stcut_flow(stCut,H,maxFlowProblem) = get_flow_value(H, maxFlowProblem) .

الإثبات: دع stCut=stCut(maxFlowProblem.sourceNode,maxFlowProblem.terminalNode,set([a for a in H.setOfArcs if a.toNode == maxFlowProblem.terminalNode])) . ينطبق الاقتراح E على stCut مباشرة من تعريف قيمة التدفق الحادي . لنفترض أننا نرغب في نقل بعض العقدة n من القسم s ( get_first_part(stCut.cut, G) ) وإلى القسم t (get_second_part(stCut.cut, G)) ، للقيام بذلك نحتاج إلى تغيير stCut.cut ، والذي يمكن أن يغير stcut_flow = get_stcut_flow(stCut,H,maxFlowProblem) ويبطل الاقتراح E. ومع ذلك ، دعونا نرى كيف ستتغير قيمة stcut_flow ونحن نجري هذا التغيير. العقدة n في حالة توازن مما يعني أن مجموع التدفق إلى العقدة n يساوي مجموع التدفق الخارج منها (وهذا ضروري لـ H لتمثيل حل ممكن ). لاحظ أن كل التدفق الذي يعد جزءًا من stcut_flow الذي يدخل العقدة n يدخله من القسم s (التدفق الذي يدخل العقدة n من القسم t إما بشكل مباشر أو غير مباشر لن يتم حسابه في قيمة stcut_flow لأنه يتجه في الاتجاه الخاطئ على أساس التعريف). بالإضافة إلى ذلك ، فإن كل التدفق الخارج n سوف يتدفق في النهاية (بشكل مباشر أو غير مباشر) إلى العقدة الطرفية (تم إثباته سابقًا). عندما ننقل العقدة n إلى القسم t ، يجب إضافة كل التدفق الذي يدخل n من القسم s إلى قيمة stcut_flow الجديدة ؛ ومع ذلك ، يجب طرح كل التدفق الخارج n من القيمة الجديدة stcut_flow ؛ يتم طرح جزء التدفق المتجه مباشرة إلى القسم t لأن هذا التدفق أصبح الآن داخليًا للقسم t الجديد ولا يتم حسابه على أنه stcut_flow . يجب أيضًا طرح جزء التدفق من العنوان n إلى العقد في القسم s من stcut_flow : بعد نقل n إلى القسم t ، سيتم توجيه هذه التدفقات من القسم t إلى القسم s وهكذا لا يجب احتسابه في stcut_flow ، حيث يتم إزالة هذه التدفقات التدفق إلى القسم s ويجب تقليله بمجموع هذه التدفقات ، والتدفق من القسم s إلى القسم t (حيث تتدفق جميع التدفقات من يجب أن ينتهي st)) بنفس المقدار. نظرًا لأن العقدة n كانت في حالة توازن قبل العملية ، فسيضيف التحديث نفس القيمة إلى قيمة stcut_flow الجديدة حيث تم طرحها وبالتالي ترك الاقتراح E صحيحًا بعد التحديث. ثم تتبع صحة الاقتراح E من الاستقراء على حجم القسم t.

فيما يلي بعض أمثلة شبكات التدفق للمساعدة في تصور الحالات الأقل وضوحًا حيث يحمل الاقتراح E ؛ في الصورة ، تشير المناطق الحمراء إلى القسم s ، بينما تمثل المناطق الزرقاء القسم t ، بينما تشير الأقواس الخضراء إلى قطع st . في الصورة الثانية ، يزداد التدفق بين العقدة A والعقدة B بينما التدفق إلى العقدة الطرفية t لا يتغير:

نتيجة طبيعية: لا يمكن أن تتجاوز قيمة تدفق القطع قدرة أي قطع .

الاقتراح F. (أقصى تدفق ، نظرية القطع الدقيقة): لنفترض أن f هو تدفق st . الشروط الثلاثة التالية متكافئة:

1. يوجد قطع st تساوي سعته قيمة التدفق f .

2. f هو أقصى تدفق .

3. لا يوجد مسار زيادة فيما يتعلق بـ f .

الشرط 1 يعني الشرط 2 بالنتيجة الطبيعية. يشير الشرط 2 إلى الشرط 3 لأن وجود مسار زيادة يعني وجود تدفق بقيم أكبر ، بما يتعارض مع أقصى قيمة لـ f . يشير الشرط 3 إلى الشرط s : لنفترض أن C_s هي مجموعة جميع العقد التي يمكن الوصول إليها من خلال مسار زيادة في الرسم البياني المتبقي . لنفترض أن C_t هي الأقواس المتبقية ، ثم يجب أن تكون t في C_t (بافتراضنا). الأقواس المتقاطعة من C_s إلى C_t تشكل قطعًا يحتوي a أقواس فقط حيث إما a.datum.capacity = a.datum.flow أو a.datum.flow = 0.0 . إذا كان هذا بخلاف ذلك ، فإن العقد المتصلة بقوس مع السعة المتبقية المتبقية لـ C_s ستكون في مجموعة C_s حيث سيكون هناك مسار زيادة من s إلى هذه العقدة . التدفق عبر المقطع st يساوي سعة st cut (نظرًا لأن الأقواس من C_s إلى C_t لها تدفق مساوٍ للسعة) وأيضًا لقيمة التدفق st (حسب الاقتراح E ).

هذا البيان الخاص بالتدفق الأقصى ، نظرية القطع الدقيقة يشير إلى العبارة السابقة من التدفقات في الشبكات.

النتيجة الطبيعية (خاصية التكامل): عندما تكون السعات أعدادًا صحيحة ، يوجد حد أقصى للتدفق ذي قيمة صحيحة ، وتجده خوارزمية Ford-Fulkerson.

الإثبات: يزيد كل مسار زيادة التدفق بعدد صحيح موجب ، والحد الأدنى من القدرات غير المستخدمة في أقواس "الدفع" والتدفقات في أقواس "السحب" ، وكلها دائمًا أعداد صحيحة موجبة.

هذا يبرر وصف طريقة Ford-Fulkerson من CLRS . تتمثل الطريقة في الاستمرار في العثور على مسارات maxFlowSolution augment حلول أفضل ، حتى لا يكون هناك المزيد من المسار المعزز مما يعني أن أحدث حل للتدفق الأقصى هو الأمثل .

من Ford-Fulkerson إلى Edmonds-Karp

الأسئلة المتبقية المتعلقة بحل مشكلات التدفق الأقصى هي:

1. كيف يجب إنشاء مسارات الزيادة ؟

2. هل ستنتهي الطريقة إذا استخدمنا الأعداد الحقيقية وليس الأعداد الصحيحة؟

3. كم من الوقت سيستغرق الإنهاء (إذا حدث ذلك)؟

تحدد خوارزمية Edmonds-Karp أن كل مسار زيادة يتم إنشاؤه بواسطة بحث أول عرض (BFS) للرسم البياني المتبقي ؛ اتضح أن قرار النقطة 1 أعلاه سيؤدي أيضًا إلى إجبار الخوارزمية على الإنهاء (النقطة 2) ويسمح بتحديد الوقت المقارب وتعقيد المكان.

أولاً ، إليك تطبيق 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

لقد استخدمت deque من وحدة مجموعات python.

للإجابة على السؤال 2 أعلاه ، سأعيد صياغة دليل آخر من Sedgewick و Wayne: Proposition G. عدد مسارات الزيادة المطلوبة في خوارزمية Edmonds-Karp مع العقد N والأقواس A على الأكثر NA/2 . الدليل: كل مسار زيادة له قوس عنق الزجاجة - قوس تم حذفه من الرسم البياني المتبقي لأنه يتوافق إما مع قوس "دفع" يتم ملؤه بالسعة أو قوس "سحب" يتحول من خلاله التدفق إلى 0. في كل مرة يتحول القوس إلى قوس عنق الزجاجة ، ويجب أن يزيد طول أي مسار زيادة من خلاله بمعامل 2. وذلك لأن كل عقدة في المسار قد تظهر مرة واحدة فقط أو لا تظهر على الإطلاق (من تعريف المسار ) نظرًا لأن المسارات موجودة استكشاف من أقصر مسار إلى أطول مما يعني أنه يجب زيارة عقدة واحدة على الأقل من خلال المسار التالي الذي يمر عبر عقدة عنق الزجاجة المعينة مما يعني وجود قوسين إضافيين على المسار قبل أن نصل إلى العقدة . نظرًا لأن مسار الزيادة يكون بطول N على الأكثر ، يمكن أن يكون كل قوس على الأكثر N/2 من مسارات التعزيز ، ويكون العدد الإجمالي لمسارات الزيادة NA/2 على الأكثر.

يتم تنفيذ خوارزمية Edmonds-Karp في O(NA^2) . إذا تم استكشاف مسارات NA/2 على الأكثر أثناء الخوارزمية واستكشاف كل مسار باستخدام BFS هو N+A ، فإن المصطلح الأكثر أهمية للمنتج وبالتالي التعقيد المقارب هو O(NA^2) .

دع mfp يكون 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

الإصدار أعلاه غير فعال وله تعقيد أسوأ من O(NA^2) لأنه ينشئ حلًا جديدًا للتدفق الأقصى ورسمًا بيانيًا جديدًا في كل مرة (بدلاً من تعديل الرسوم البيانية الحالية مع تقدم الخوارزمية). للوصول إلى حل O(NA^2) حقيقي ، يجب أن تحافظ الخوارزمية على كل من الرسم البياني الذي يمثل حالة مشكلة التدفق القصوى والرسم البياني المتبقي المرتبط بها. لذلك يجب أن تتجنب الخوارزمية التكرار عبر الأقواس والعقد دون داع وتحديث قيمها والقيم المرتبطة بها في الرسم البياني المتبقي فقط عند الضرورة.

لكتابة خوارزمية Edmonds Karp أسرع ، أعدت كتابة عدة أجزاء من الكود مما ورد أعلاه. آمل أن يكون الاطلاع على الكود الذي أنشأ مخططًا جديدًا مفيدًا في فهم ما يحدث. في الخوارزمية السريعة ، أستخدم بعض الحيل الجديدة وهياكل بيانات Python التي لا أريد أن أتطرق إليها بالتفصيل. a.fromNode أن a.toNode . بالنسبة لهذا الرمز ، دع mfps يكون 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

فيما يلي تصور لكيفية حل هذه الخوارزمية لشبكة التدفق النموذجية من الأعلى. يُظهر التصور الخطوات كما تنعكس في Digraph G التي تمثل أحدث شبكة تدفق وكما تنعكس في الرسم البياني المتبقي لشبكة التدفق تلك. تظهر مسارات التعزيز في الرسم البياني المتبقي كمسارات حمراء ، والرسم البياني الذي يمثل المشكلة ، يتم تمييز مجموعة العقد والأقواس المتأثرة بمسار زيادة معين باللون الأخضر. في كل حالة ، سأقوم بتمييز أجزاء الرسم البياني التي سيتم تغييرها (باللون الأحمر أو الأخضر) ثم أعرض الرسم البياني بعد التغييرات (باللون الأسود فقط).

إليك تصور آخر لكيفية حل هذه الخوارزمية لشبكة تدفق مختلفة كمثال. لاحظ أن هذا الرقم يستخدم أرقامًا حقيقية ويحتوي على أقواس متعددة بنفس قيم fromNode و toNode .

** لاحظ أيضًا أنه نظرًا لأن الأقواس التي تحتوي على "سحب" البيانات المتبقية قد تكون جزءًا من المسار المعزز ، فإن العقد المتأثرة في الرسم البياني للشبكة الجوية _ قد لا تكون على مسار في G! .

الرسوم البيانية ثنائية الأجزاء

لنفترض أن لدينا digraph G ، G ثنائي القسم إذا كان من الممكن تقسيم العقد في G.setOfNodes إلى مجموعتين ( part_1 و part_2 ) a.fromNode لا يمكن أن يكون صحيحًا أن a.fromNode a G.setOfArcs part_1 أ- part_1 a.toNode لا يمكن أيضًا أن يكون صحيحًا أن a.fromNode في part_2 و a.toNode في part_2 .

بعبارة أخرى ، يكون G ثنائيًا إذا كان من الممكن تقسيمه إلى مجموعتين من العقد بحيث يجب على كل قوس توصيل عقدة في مجموعة واحدة بعقدة في المجموعة الأخرى.

اختبار ثنائي الأطراف

لنفترض أن لدينا digraph G ، نريد اختبار ما إذا كان ثنائيًا أم لا. يمكننا القيام بذلك في O(|G.setOfNodes|+|G.setOfArcs|) عن طريق التلوين الجشع للرسم البياني إلى لونين.

أولاً ، نحتاج إلى إنشاء digraph H جديد. سيكون لهذا الرسم البياني نفس مجموعة العقد مثل G ، لكن سيكون به أقواس أكثر من G كل قوس a في G سيخلق قوسين في H ؛ سيكون القوس الأول مطابقًا لـ a ، ويعكس القوس الثاني مدير 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)

المطابقات والحد الأقصى من المطابقات

لنفترض أن لدينا digraph G وأن matching هي مجموعة فرعية من الأقواس من G.setOfArcs . matching هي matching إذا كان أي قوسين a و b متطابقين: len(frozenset( {a.fromNode} ).union( {a.toNode} ).union( {b.fromNode} ).union( {b.toNode} )) == 4 . بمعنى آخر ، لا يوجد قوسان في تطابق مشترك يشتركان في عقدة .

مطابقة matching ، هي أقصى مطابقة إذا لم يكن هناك تطابق alt_matching في G مثل أن len(matching) < len(alt_matching) . بمعنى آخر ، matching هي الحد الأقصى للمطابقة إذا كانت أكبر مجموعة من الأقواس من G.setOfArcs والتي لا تزال تفي بتعريف المطابقة (إضافة أي قوس غير موجود بالفعل في المطابقة سيؤدي إلى كسر تعريف المطابقة ).

المطابقة القصوى هي matching مثالية إذا كان هناك قوس a في matching في كل عقدة n في G.setOfArcs حيث a.fromNode == n or a.toNode == n .

أقصى تطابق ثنائي

المطابقة القصوى بين الطرفين هي أقصى مطابقة على Digraph G وهو ثنائي الجزء .

بالنظر إلى أن G ثنائية الأطراف ، يمكن تحويل مشكلة إيجاد مطابقة قصوى ثنائية الأطراف إلى مشكلة تدفق أقصى يمكن حلها باستخدام خوارزمية Edmonds-Karp ومن ثم يمكن استرداد الحد الأقصى من المطابقة الثنائية من الحل إلى مشكلة التدفق الأقصى .

دع bipartition يكونان من قسمين من G

للقيام بذلك ، أحتاج إلى إنشاء رسم H.setOfNodes جديد ( H ) مع بعض العقد الجديدة ( H.setOfNodes ) وبعض الأقواس الجديدة ( H.setOfArcs ). يحتوي H.setOfNodes على جميع العقد في G.setOfNodes أخريين ، s ( عقدة مصدر ) و t ( عقدة طرفية ).

H.setOfArcs على قوس واحد لكل G.setOfArcs . إذا FlowArcDatum(1,0) القوس a a G.setOfArcs H a.fromNode a.toNode bipartition.firstPart bipartition.secondPart

bipartition.firstPart a.fromNode bipartition.secondPart H.setOfArcs a.toNode Arc(a.toNode,a.fromNode,FlowArcDatum(1,0))

يضمن تعريف الرسم البياني ثنائي الأجزاء عدم وجود قوس يربط أي عقد حيث تكون كلا العقدتين في نفس القسم. يحتوي H.setOfArcs أيضًا على قوس من العقدة إلى كل عقدة s bipartition.firstPart . أخيرًا ، يحتوي H.setOfArcs على قوس لكل عقدة في bipartition.secondPart to node t . a.datum.capacity = 1 a H.setOfArcs

قم أولاً بتقسيم العقد في G.setOfNodes ، المجموعتين المنفصلتين ( part1 الأول والجزء part2 ) بحيث لا يتم توجيه أي قوس في G.setOfArcs G بعد ذلك ، أضف جميع الأقواس في G.setOfArcs والتي يتم توجيهها من part1 1 إلى الجزء H.setOfArcs part2 ثم قم بإنشاء عقدة مصدر واحدة وعقدة طرفية واحدة s t المزيد من الأقواس

ثم قم ببناء 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

الحد الأدنى من غطاء العقدة

غطاء العقدة في digraph G عبارة عن مجموعة من العقد ( cover ) من G.setOfNodes بحيث يجب أن يكون هذا صحيحًا لأي قوس a G.setOfArcs : (a.fromNode in cover) or (a.toNode in cover) .

الحد الأدنى من غطاء العقدة هو أصغر مجموعة ممكنة من العقد في الرسم البياني والتي لا تزال عبارة عن غطاء عقدة . تنص نظرية كونيج على أنه في الرسم البياني الثنائي ، يكون حجم الحد الأقصى للمطابقة على هذا الرسم البياني مساويًا لحجم الحد الأدنى من غطاء العقدة ، وتقترح كيف يمكن استرداد غطاء العقدة من أقصى مطابقة :

لنفترض أن لدينا bipartition القسم وأقصى تطابق matching . حدد digraph جديد H ، H.setOfNodes=G.setOfNodes ، الأقواس في H.setOfArcs هي اتحاد مجموعتين.

المجموعة الأولى هي أقواس a في matching ، مع التغيير الذي إذا كان a.fromNode in bipartition.firstPart a.toNode و a.toNode in bipartition.secondPart a.fromNode a.datum.inMatching=True a . a.datum.inMatching=True للإشارة إلى أنها مشتقة من أقواس في مطابقة .

المجموعة الثانية a أقواس ليست في matching ، مع التغيير الذي إذا a.datum.inMatching=False a.fromNode in bipartition.secondPart في a.toNode in bipartition.firstPart و a.fromNode a.toNode a.datum.inMatching=False ).

بعد ذلك ، قم بإجراء بحث أول عميق (DFS) بدءًا من كل عقدة n في bipartition.firstPart وهو ليس n == a.fromNode ولا n == a.toNodes لأي قوس a في matching . أثناء DFS ، تتم زيارة بعض العقد والبعض الآخر لا (قم بتخزين هذه المعلومات في حقل n.datum.visited ). الحد الأدنى لغطاء العقدة هو اتحاد العقد {a.fromNode for a in H.setOfArcs if ( (a.datum.inMatching) and (a.fromNode.datum.visited) ) } والعقد {a.fromNode for a in H.setOfArcs if (a.datum.inMatching) and (not a.toNode.datum.visited)} .

يمكن إثبات أن هذا يؤدي من الحد الأقصى للمطابقة إلى الحد الأدنى من غطاء العقدة عن طريق إثبات a.toNode ، واتخاذ بعض القوس الذي a المفترض أنه لم يتم a.fromNode والنظر في جميع الحالات الأربع فيما يتعلق بما إذا كان toNode fromNode ) إلى أي قوس في المطابقة matching تؤدي كل حالة إلى تناقض بسبب ترتيب زيارات DFS للعقد وحقيقة أن matching هي أقصى مطابقة .

لنفترض أن لدينا وظيفة لتنفيذ هذه الخطوات وإرجاع مجموعة العقد التي تشتمل على الحد الأدنى من غطاء العقدة عند إعطاء digraph G ، matching القصوى :

 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

مشكلة التخصيص الخطية

تتكون مشكلة التخصيص الخطي من إيجاد أقصى وزن مطابق في رسم بياني مرجح ثنائي الأجزاء.

يمكن التعبير عن مشاكل مثل تلك الموجودة في بداية هذا المنشور كمشكلة مهمة خطية . بالنظر إلى مجموعة من العمال ، ومجموعة من المهام ، ووظيفة تشير إلى ربحية تعيين عامل واحد لمهمة واحدة ، نريد تعظيم مجموع جميع المهام التي نقوم بها ؛ هذه مشكلة إحالة خطية .

افترض أن عدد المهام والعاملين متساوون ، على الرغم من أنني سأوضح أن هذا الافتراض سهل الإزالة. في التنفيذ ، أنا أمثل أوزان القوس بالسمة a.datum.weight للقوس a .

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

خوارزمية كوهن مونكرس

تحل خوارزمية Kuhn-Munkres مشكلة التخصيص الخطية . يمكن أن يستغرق التنفيذ الجيد وقتًا O(N^{4}) (حيث N هو عدد العقد في الرسم البياني الذي يمثل المشكلة). التطبيق الذي يسهل شرحه يأخذ O(N^{5}) (للإصدار الذي يعيد إنشاء DiGraphs ) و O(N^{4}) لـ (للإصدار الذي يحافظ على DiGraphs ). هذا مشابه لتطبيقين مختلفين لخوارزمية Edmonds-Karp .

بالنسبة لهذا الوصف ، فأنا أعمل فقط مع الرسوم البيانية الكاملة ثنائية الأجزاء (تلك التي يوجد فيها نصف العقد في جزء واحد من القسم الثنائي والنصف الآخر في الجزء الثاني). في العامل ، يعني دافع المهمة أن هناك عددًا كبيرًا من العمال مثل المهام.

يبدو هذا كشرط مهم (ماذا لو لم تكن هذه المجموعات متساوية!) ولكن من السهل إصلاح هذه المشكلة ؛ أتحدث عن كيفية القيام بذلك في القسم الأخير.

إصدار الخوارزمية الموصوفة هنا يستخدم المفهوم المفيد للأقواس ذات الوزن الصفري . لسوء الحظ ، لا يكون هذا المفهوم منطقيًا إلا عندما نحل تصغيرًا (إذا كان بدلاً من تعظيم أرباح تعيينات مهام العمال الخاصة بنا ، فإننا بدلاً من ذلك نقلل تكلفة هذه التعيينات إلى الحد الأدنى).

لحسن الحظ ، من السهل تحويل مشكلة التعيين الخطي القصوى إلى مشكلة تعيين خطي دنيا عن طريق a أوزان كل قوس إلى Ma.datum.weight حيث M=max({a.datum.weight for a in G.setOfArcs}) . سيكون حل مشكلة التعظيم الأصلية مطابقًا لحل مشكلة التقليل بعد تغيير أوزان القوس . لذا ، بالنسبة للبقية ، افترض أننا نجري هذا التغيير.

تحل خوارزمية Kuhn-Munkres مطابقة الحد الأدنى للوزن في رسم بياني ثنائي الجزء مرجح من خلال سلسلة من المطابقات القصوى في الرسوم البيانية ثنائية الأجزاء غير الموزونة. إذا وجدنا تطابقًا تامًا في التمثيل الرقمي لمسألة التخصيص الخطي ، وإذا كان وزن كل قوس في المطابقة صفرًا ، فقد وجدنا الحد الأدنى لمطابقة الوزن نظرًا لأن هذه المطابقة تشير إلى أن جميع العقد في الرسم البياني كانت يقابله قوس بأقل تكلفة ممكنة (لا يمكن أن تكون التكلفة أقل من 0 ، بناءً على التعريفات السابقة).

لا يمكن إضافة أقواس أخرى إلى المطابقة (لأن جميع العقد مطابقة بالفعل) ولا يجب إزالة أي أقواس من المطابقة لأن أي قوس بديل محتمل سيكون له على الأقل قيمة وزن كبيرة.

إذا وجدنا الحد الأقصى من المطابقة للرسم البياني الفرعي لـ G الذي يحتوي فقط على أقواس بوزن صفري ، ولم يكن تطابقًا تامًا ، فليس لدينا حل كامل (نظرًا لأن المطابقة ليست مثالية ). ومع ذلك ، يمكننا إنتاج digraph H جديد عن طريق تغيير أوزان الأقواس في G.setOfArcs بطريقة تظهر أقواسًا جديدة ذات وزن صفري والحل الأمثل لـ H هو نفس الحل الأمثل لـ G نظرًا لأننا نضمن إنتاج قوس بوزن صفري واحد على الأقل في كل تكرار ، فإننا نضمن أننا سنصل إلى مطابقة مثالية في ما لا يزيد عن | G.setOfNodes | ^ {2} = N ^ {2} مثل هذه التكرارات.

لنفترض أنه في قسم ثنائي القسم ، يحتوي bipartition bipartition.firstPart على عقد تمثل العمال ، بينما يمثل bipartition.secondPart العقد التي تمثل المهام.

تبدأ الخوارزمية بتوليد Digraph H جديد. H.setOfNodes = G.setOfNodes . يتم إنشاء بعض الأقواس في H من العقد n في bipartition.firstPart . تنشئ كل عقدة n قوسًا b في H.setOfArcs لكل قوس a في قسمين. bipartition.G.setOfArcs حيث a.fromNode = n أو a.toNode = n ، b=Arc(a.fromNode, a.toNode, a.datum.weight - z) حيث z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

يتم إنشاء المزيد من الأقواس في H من العقد n في bipartition.secondPart . تولد كل عقدة n قوسًا b في H.setOfArcs لكل قوس a في قسمين. bipartition.G.setOfArcs حيث a.fromNode = n أو a.toNode = n ، b=Arc(a.fromNode, a.toNode, ArcWeightDatum(a.datum.weight - z)) حيث z=min(x.datum.weight for x in G.setOfArcs if ( (x.fromNode == n) or (x.toNode == n) )) .

KMA: بعد ذلك ، قم بتشكيل digraph K جديد يتكون من أقواس الوزن الصفرية فقط من H ، والعقد الواقعة على تلك الأقواس . قم بتكوين قسمين على العقد في K ، ثم استخدم solve_mbm( bipartition ) bipartition على أقصى تطابق ( matching ) على K إذا كانت matching تمامًا في H ( أقواس matching موجودة على جميع العقد في H.setOfNodes ) H.setOfNodes فإن matching هي الحل الأمثل لمشكلة التخصيص الخطي .

خلاف ذلك ، إذا لم تكن matching مثالية ، فقم بإنشاء الحد الأدنى من غطاء العقدة لـ K باستخدام node_cover = get_min_node_cover(matching, bipartition(K)) . بعد ذلك ، حدد z=min({a.datum.weight for a in H.setOfArcs if a not in node_cover}) . حدد 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)} . يعمل الرمز != في التعبير السابق كعامل XOR. ثم arcs = arcs1.union(arcs2.union(arcs3)) . التالي ، H=DiGraph(nodes,arcs) . ارجع إلى التسمية KMA تستمر الخوارزمية حتى يتم إنتاج مطابقة كاملة هذه المطابقة هي أيضًا الحل لمشكلة التخصيص الخطي .

 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

هذا التنفيذ هو O(N^{5}) لأنه ينشئ حدًا أقصى جديدًا matching في كل تكرار ؛ على غرار التطبيقين السابقين لـ Edmonds-Karp ، يمكن تعديل هذه الخوارزمية بحيث تتعقب المطابقة وتكييفها بذكاء مع كل تكرار. عند القيام بذلك ، يصبح التعقيد O(N^{4}) . يمكن تشغيل إصدار أكثر تقدمًا وحداثة من هذه الخوارزمية (تتطلب بعض هياكل البيانات الأكثر تقدمًا) في O(N^{3}) . يمكن العثور على تفاصيل كل من التطبيق الأبسط أعلاه والتنفيذ الأكثر تقدمًا في هذا المنشور الذي حفز منشور المدونة هذا.

لا تعدل أي من العمليات على أوزان القوس التعيين النهائي الذي تعيده الخوارزمية. وإليك السبب: نظرًا لأن الرسوم البيانية للإدخال هي دائمًا رسوم بيانية ثنائية الأجزاء كاملة ، يجب أن يرسم الحل كل عقدة في قسم إلى عقدة أخرى في القسم الثاني ، عبر القوس بين هاتين العقدتين . لاحظ أن العمليات التي يتم إجراؤها على أوزان القوس لا تغير أبدًا الترتيب (مرتبة حسب الوزن) لحادث الأقواس على أي عقدة معينة.

وبالتالي ، عندما تنتهي الخوارزمية عند مطابقة ثنائية كاملة تامة ، يتم تعيين قوس بوزن صفري لكل عقدة ، نظرًا لأن الترتيب النسبي للأقواس من تلك العقدة لم يتغير أثناء الخوارزمية ، وبما أن القوس ذو الوزن الصفري هو أرخص قوس ممكن و يضمن التطابق الكامل الكامل بين الطرفين وجود قوس واحد لكل عقدة . هذا يعني أن الحل الناتج هو في الواقع نفس الحل من مشكلة التخصيص الخطي الأصلية دون أي تعديل لأوزان القوس .

تكليفات غير متوازنة

يبدو أن الخوارزمية محدودة للغاية نظرًا لأنها كما تم وصفها تعمل فقط على الرسوم البيانية ثنائية الأجزاء الكاملة (تلك التي تكون فيها نصف العقد في جزء واحد من القسمين والنصف الآخر في الجزء الثاني). في العامل ، يعني دافع المهمة أن هناك عددًا كبيرًا من العمال مثل المهام (يبدو أنه محدود للغاية).

ومع ذلك ، هناك تحول سهل يزيل هذا القيد. لنفترض أن عدد العاملين أقل من عدد المهام ، فنحن نضيف بعض العمال الوهميين (وهو ما يكفي لجعل الرسم البياني الناتج رسمًا بيانيًا كاملًا ثنائي الأجزاء ). 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:

هذا هو. 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 Engineering:

• علم بيانات الرسم البياني باستخدام Python / NetworkX