การไหลสูงสุดและปัญหาการกำหนดเชิงเส้น

นี่คือปัญหา: ธุรกิจของคุณมอบหมายให้ผู้รับเหมาปฏิบัติตามสัญญา คุณตรวจสอบบัญชีรายชื่อของคุณและตัดสินใจว่าผู้รับเหมารายใดที่พร้อมสำหรับการสู้รบหนึ่งเดือน และคุณตรวจสอบสัญญาที่มีอยู่ของคุณเพื่อดูว่าสัญญาใดในสัญญาจ้างงานที่มีระยะเวลาหนึ่งเดือน เนื่องจากคุณทราบดีว่าผู้รับเหมาแต่ละรายสามารถปฏิบัติตามสัญญาแต่ละสัญญาได้มีประสิทธิภาพเพียงใด คุณจะมอบหมายผู้รับเหมาให้มีประสิทธิภาพสูงสุดโดยรวมในเดือนนั้นได้อย่างไร

นี่คือตัวอย่างของปัญหาการมอบหมาย และปัญหาสามารถแก้ไขได้ด้วยอัลกอริธึมแบบคลาสสิกของฮังการี

อัลกอริธึมของฮังการี (หรือที่เรียกว่าอัลกอริธึม Kuhn-Munkres) เป็นอัลกอริทึมเวลาพหุนามที่เพิ่มการจับคู่น้ำหนักสูงสุดในกราฟสองส่วนแบบถ่วงน้ำหนัก ที่นี่ ผู้รับเหมาและสัญญาสามารถสร้างแบบจำลองเป็นกราฟสองส่วน โดยมีประสิทธิภาพเป็นน้ำหนักของขอบระหว่างผู้รับเหมาและโหนดสัญญา

ในบทความนี้ คุณจะได้เรียนรู้เกี่ยวกับการใช้งานอัลกอริทึมของฮังการีที่ใช้อัลกอริทึม Edmonds-Karp เพื่อแก้ปัญหาการกำหนดเชิงเส้น นอกจากนี้ คุณจะได้เรียนรู้ว่าอัลกอริทึมของ Edmonds-Karp เป็นการดัดแปลงเล็กน้อยของวิธี Ford-Fulkerson อย่างไร และการเปลี่ยนแปลงนี้มีความสำคัญอย่างไร

ปัญหาการไหลสูงสุด

ปัญหาการไหลสูงสุดสามารถอธิบายได้อย่างไม่เป็นทางการว่าเป็นปัญหาของการเคลื่อนย้ายของเหลวหรือก๊าซบางส่วนผ่านเครือข่ายท่อจากแหล่งเดียวไปยังขั้วเดียว ทำได้โดยมีข้อสันนิษฐานว่าแรงดันในโครงข่ายเพียงพอที่จะทำให้แน่ใจว่าของเหลวหรือก๊าซจะไม่ค้างอยู่ในความยาวของท่อหรือข้อต่อท่อ (ตำแหน่งที่ท่อมาบรรจบกัน)

ด้วยการเปลี่ยนแปลงบางอย่างในกราฟ ปัญหาการมอบหมายจะกลายเป็นปัญหาการไหลสูงสุด

เบื้องต้น

แนวคิดที่จำเป็นในการแก้ปัญหาเหล่านี้เกิดขึ้นในสาขาวิชาคณิตศาสตร์และวิศวกรรมศาสตร์ บ่อยครั้งแนวคิดที่คล้ายคลึงกันมักเรียกกันโดยใช้ชื่อต่างกันและแสดงออกมาในรูปแบบต่างๆ (เช่น เมทริกซ์ความใกล้เคียงกัน เนื่องจากแนวคิดเหล่านี้ค่อนข้างลึกลับ จึงมีการเลือกว่าโดยทั่วไปแนวคิดเหล่านี้จะถูกกำหนดไว้อย่างไรสำหรับการตั้งค่าใดๆ

บทความนี้จะไม่ถือว่าความรู้ก่อนหน้าใด ๆ เกินกว่าทฤษฎีเซตเกริ่นนำเล็กน้อย

การใช้งานในโพสต์นี้แสดงถึงปัญหาในรูปแบบกราฟกำกับ (digraph)

DiGraphs

digraph มีสองแอตทริบิวต์คือ setOfNodes และ setOfArcs คุณลักษณะทั้งสองนี้เป็นชุด (คอลเลกชันที่ไม่เรียงลำดับ) ในบล็อคโค้ดของโพสต์นี้ จริงๆ แล้วฉันใช้ Frozenset ของ 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'])

ชุดของ ส่วนโค้ง ในได กราฟ แสดงถึงความสัมพันธ์แบบไบนารีบน โหนด ในได กราฟ การมีอยู่ของ ส่วนโค้ง a หมายความว่ามีความสัมพันธ์ระหว่าง a.fromNode และ a.toNode

ในกราฟแบบกำหนดทิศทาง (ตรงข้ามกับกราฟแบบไม่มีทิศทาง) การมีอยู่ของความสัมพันธ์ระหว่าง a.fromNode และ a.toNode ไม่ ได้ หมายความว่ามีความสัมพันธ์ที่คล้ายคลึงกันระหว่าง a.toNode และ a.fromNode

เนื่องจากในกราฟที่ไม่มีทิศทาง ความสัมพันธ์ที่แสดงออกมานั้นไม่จำเป็นต้องสมมาตรเสมอไป

DiGraphs

สามารถใช้ โหนด และ ส่วนโค้ง เพื่อกำหนดได กราฟ แต่เพื่อความสะดวก ในอัลกอริทึมด้านล่าง ได กราฟ จะถูกแสดงโดยใช้เป็นพจนานุกรม

นี่คือวิธีการที่สามารถแปลงการแสดงกราฟด้านบนเป็นการแทนพจนานุกรมที่คล้ายกับวิธีนี้:

 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

เมื่อบทความพูดถึงได กราฟ ที่แสดงโดยพจนานุกรม จะกล่าวถึง 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()

ในการกำหนดกราฟ บางครั้งผู้คนใช้คำว่า โหนด และ จุดยอด เพื่ออ้างถึงแนวคิดเดียวกัน เช่นเดียวกับเงื่อนไข ส่วนโค้ง และขอบ

การแสดงกราฟที่นิยมสองรูปแบบใน Python คือรูปแบบหนึ่งที่ใช้พจนานุกรมและอีกรูปแบบหนึ่งใช้วัตถุเพื่อแสดงกราฟ การเป็นตัวแทนในโพสต์นี้อยู่ระหว่างการแสดงแทนที่ใช้กันทั่วไปทั้งสองนี้

นี่คือการแสดงได กราฟ ของฉัน มีหลายคนที่ชอบมัน แต่อันนี้เป็นของฉัน

เดินและเส้นทาง

ให้ 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 โหนดปลายทาง ในได กราฟ 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

ตัดและตัด

การ cut ของได กราฟ ที่เชื่อมต่อ G เป็นเซ็ตย่อยของ ส่วนโค้ง จาก G.setOfArcs ซึ่งแบ่งชุดของ โหนด G.setOfNodes ใน G G เชื่อมต่อหากทุก โหนด n ใน G.setOfNodes และมี ส่วนโค้ง a น้อยหนึ่งส่วนใน G.setOfArcs เช่นนั้น n = a.fromNode หรือ n = a.toNode แต่ a.fromNode != a.toNode

 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 เป็น 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 if (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'])

เครือข่ายการไหล

คุณสามารถใช้ได กราฟ G เพื่อแสดงถึงเครือข่ายโฟลว์

กำหนดแต่ละ โหนด n โดยที่ n อยู่ใน G.setOfNodes n.datum ที่เป็น FlowNodeDatum :

 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 เรียกว่าข้อจำกัดความจุ

ตัดความจุ

ความสามารถ ในการตัดของ st cut stCut ที่มี โหนดต้นทาง s และ โหนดปลายทาง t ของ เครือข่ายโฟ ลว์ที่แสดงโดย 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) เป็น st cut ของ เครือข่ายโฟ ลว์ที่แสดงโดย digraph G

stCut คือการ ตัดความจุขั้นต่ำ ของ เครือข่ายโฟ ลว์ที่แสดงโดย G หากไม่มี st cut 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 โหนดต้นทาง G.setOfNodes s โหนดปลายทาง 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 สามารถแสดงโดย เครือข่ายการไหล ที่แสดงเป็นได กราฟ 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

กล่าวอีกนัยหนึ่ง โซลูชันการไหลสูงสุดที่เป็นไปได้ สามารถแสดงด้วยได กราฟ ซึ่ง:

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 Flow Value ของ H

ปล่อย:

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

ซึ่งหมายความว่า mfps เป็น สถานะตัวตายตัวแทน ของ maxFlowProblem ซึ่งหมายความว่า mfps นั้นเหมือนกับ maxFlowProblem โดยมีข้อยกเว้นว่าค่าของ a.flow สำหรับส่วนโค้ง a ใน maxFlowProblem.setOfArcs อาจแตกต่างจาก a.flow สำหรับส่วนโค้ง a ใน mfps.setOfArcs ชุดของ 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 Cut Flow

ให้ mfps แทน MaxFlowProblemState และให้ stCut เป็น mfps.G ของ 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 cut flow คือผลรวมของกระแสจากพาร์ติชั่นที่มี โหนดต้นทาง ไปยังพาร์ติชั่นที่มี โหนดปลายทาง ลบด้วยผลรวมของโฟลว์จากพาร์ติชั่นที่มี โหนดปลายทาง ไปยังพาร์ติชั่นที่มี โหนดต้นทาง

Max Flow, Min Cut

ให้ maxFlowProblem เป็นตัวแทน ของปัญหาการไหลสูงสุด และให้การแก้ปัญหา maxFlowProblem ถูกแสดงโดย เครือข่ายการไหล ที่แสดงเป็น digraph H

ให้ minStCut เป็นการ ตัดความจุขั้นต่ำ ของ เครือข่ายโฟ ลว์ที่แสดงโดย maxFlowProblem.G

เนื่องจากใน กระแสปัญหาการไหลสูงสุด มีต้นกำเนิดใน โหนดต้นทางเพียงโหนด เดียวและสิ้นสุดที่ โหนดปลายทาง เดียว และเนื่องจาก ข้อจำกัดด้านความจุและข้อจำกัดด้าน การ อนุรักษ์ เราทราบดีว่าโฟลว์ทั้งหมดที่เข้าสู่ maxFlowProblem.terminalNodeUid ต้องตัดผ่าน st cut ใดๆ โดยเฉพาะอย่างยิ่งต้องข้าม minStCut ซึ่งหมายความว่า:

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

การแก้ปัญหาการไหลสูงสุด

แนวคิดพื้นฐานสำหรับการแก้ปัญหาการ ไหลสูงสุด maxFlowProblem คือการเริ่มต้นด้วย โซลูชันการไหลสูงสุด ที่แสดงโดย digraph H จุดเริ่มต้นดังกล่าวสามารถเป็น H = strip_flows(maxFlowProblem.G) ภารกิจคือการใช้ H และโดยการปรับเปลี่ยนค่า a.datum.flow บางส่วนของส่วน โค้ง a ใน H.setOfArcs เพื่อสร้าง โซลูชันการไหลสูงสุด อื่นที่แสดงโดย digraph K โดยที่ K ยังไม่สามารถเป็นตัวแทน ของเครือข่ายการไหล ที่มี กระแสที่เป็นไปได้ และ get_flow_value(H, maxFlowProblem) < get_flow_value(K, maxFlowProblem) ตราบใดที่กระบวนการนี้ดำเนินต่อไป คุณภาพ ( get_flow_value(K, maxFlowProblem) ) ของ โซลูชันการไหลสูงสุด ที่พบล่าสุด ( K ) จะดีกว่า โซลูชันการไหลสูงสุด อื่นๆ ที่พบ หากกระบวนการถึงจุดที่รู้ว่าไม่มีการปรับปรุงอื่นใดที่เป็นไปได้ กระบวนการก็จะยุติลงและจะส่งคืน โซลูชันการไหลสูงสุด ที่เหมาะสมที่สุด

คำอธิบายข้างต้นเป็นเรื่องทั่วไปและข้ามการพิสูจน์หลายอย่าง เช่น กระบวนการดังกล่าวเป็นไปได้หรือไม่หรืออาจใช้เวลานานเท่าใด ฉันจะให้รายละเอียดเพิ่มเติมอีกสองสามข้อและอัลกอริทึม

The Max Flow, Min Cut Theorem

จากหนังสือ Flows in Networks โดย Ford และ Fulkerson คำกล่าวของ max flow, min cut theorem (Theorem 5.1) คือ:

สำหรับเครือข่ายใดๆ ค่าการไหลสูงสุดจาก s ถึง t จะเท่ากับความสามารถในการตัดขั้นต่ำของการตัดทั้งหมดที่แยกจาก s และ t

โดยใช้คำจำกัดความในโพสต์นี้ซึ่งแปลว่า:

วิธีแก้ปัญหา maxFlowProblem ที่แสดงโดย เครือข่ายการไหล ที่แสดงเป็น digraph H นั้นเหมาะสมที่สุดหาก:

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

ฉันชอบการพิสูจน์ทฤษฎีบทนี้และ Wikipedia มีอีกอันหนึ่ง

ทฤษฎีบทการไหลสูงสุดและการตัดขั้นต่ำ ใช้เพื่อพิสูจน์ความถูกต้องและความสมบูรณ์ของวิธี Ford-Fulkerson

ฉันจะให้การพิสูจน์ทฤษฎีบทในส่วนหลังการ เพิ่มเส้นทาง

Ford-Fulkerson Method และ Edmonds-Karp Algorithm

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 โดยที่ arc a อยู่ในเซตย่อย ถ้า a.fromNode = n และ a.toNode = u

• agg_n_to_u_cap(n,u,G_as_dict) คืนค่าผลรวมของ a.datum.flow สำหรับ ส่วนโค้ง ทั้งหมดในเซ็ตย่อยของ G.setOfArcs โดยที่ arc 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

• แต่ละ ส่วนโค้งของการไหลของพุ ชใน G_f.setOfArcs แสดงถึงการกระทำของการเพิ่มผลรวมของ x <= n_to_u_cap_sum - n_to_u_flow_sum ไหลไปยัง ส่วนโค้ง ในเซ็ตย่อยของ G.setOfArcs โดยที่ arc a อยู่ในเซตย่อย ถ้า a.fromNode = n และ a.toNode = u

• แต่ละ ส่วนโค้งของการไหลแบบดึง ใน G_f.setOfArcs แสดงถึงการกระทำของการลบทั้งหมด x <= n_to_u_flow_sum ไหลไปยัง ส่วนโค้ง ในเซ็ตย่อยของ G.setOfArcs โดยที่ arc 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 ของ ปัญหาการไหลสูงสุด maxFlowProblem ดังนั้น a โค้ง สุดท้ายบน augmentingPath จะต้องเป็นส่วน 'ดัน' และต้องมี a.toNode a.toNode == maxFlowProblem.terminalNode เส้นทางการเสริม ถูกกำหนดให้เป็นเส้นทางที่สิ้นสุดที่ โหนดปลายทาง ของ ปัญหาการไหลสูงสุด ซึ่งเป็น เส้นทางเสริม จากคำจำกัดความของ กราฟตกค้าง เป็นที่ชัดเจนว่า ส่วนโค้ง สุดท้ายใน เส้นทาง การเสริมบน กราฟที่เหลือ นั้นจะต้องเป็นส่วนโค้ง 'ดัน' เนื่องจาก ส่วน โค้ง 'ดึง' b ใน เส้นทาง การเสริมจะมี b.toNode == maxFlowProblem.terminalNode และ b.fromNode != maxFlowProblem.terminalNode จากนิยามของ path นอกจากนี้ จากคำจำกัดความของ เส้นทาง เป็นที่ชัดเจนว่า โหนดปลายทาง ถูกแก้ไขเพียงครั้งเดียวโดยวิธีการ augment ดังนั้น augment จะแก้ไข maxFlowProblem.terminalNode.flowIn เพียงครั้งเดียว และเพิ่มค่าของ maxFlowProblem.terminalNode.flowIn เนื่องจาก ส่วนโค้ง สุดท้ายใน augmentingPath จะต้องเป็น ส่วนโค้ง ที่ทำให้เกิดการแก้ไขใน maxFlowProblem.terminalNode.flowIn ระหว่าง augment จากคำจำกัดความของการ augment ตามที่ใช้กับ ส่วนโค้ง 'ดัน' maxFlowProblem.terminalNode.flowIn สามารถเพิ่มได้เท่านั้น ไม่ลดลง

หลักฐานบางอย่างจาก Sedgewick และ Wayne

หนังสือ Algorithms ฉบับที่สี่โดย Robert Sedgewich และ Kevin Wayne มีหลักฐานอันสั้นและน่าอัศจรรย์ (หน้า 892-894) ที่จะเป็นประโยชน์ ฉันจะสร้างมันขึ้นมาใหม่ที่นี่ แม้ว่าฉันจะใช้ภาษาที่เหมาะสมกับคำจำกัดความก่อนหน้านี้ ป้ายหลักฐานของฉันเหมือนกับในหนังสือ Sedgewick

ข้อเสนอ 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 โดยตรงจากคำจำกัดความของ ค่าการไหล st สมมติว่าเราต้องการย้าย โหนด n จาก s-partition ( get_first_part(stCut.cut, G) ) และไปที่ t-partition (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-partition (โฟลว์ที่เข้าสู่ โหนด n จาก t-partition ไม่ว่าทางตรงหรือทางอ้อมจะไม่ถูกนับในค่า stcut_flow เนื่องจากมันกำลังมุ่งหน้าไปผิดทาง ตามคำจำกัดความ) นอกจากนี้ การไหลออกจาก n ทั้งหมดจะไหลเข้าสู่ โหนดปลายทาง (พิสูจน์แล้วก่อนหน้านี้) (ทางตรงหรือทางอ้อม) ในที่สุด (ทางตรงหรือทางอ้อม) เมื่อเราย้าย โหนด n ไปยัง t-partition จะต้องเพิ่มโฟลว์ทั้งหมดที่ป้อน n จาก s-partition ไปยังค่า stcut_flow ใหม่ อย่างไรก็ตาม การไหลออกจาก n ทั้งหมดจะต้องถูกลบออกจากค่า stcut_flow ใหม่ ส่วนของโฟลว์ที่มุ่งหน้าไปยังพาร์ติชั่น t โดยตรงจะถูกหักออกเพราะตอนนี้โฟลว์นี้อยู่ภายในพาร์ติชั่น t ใหม่แล้ว และไม่นับเป็น stcut_flow ส่วนของโฟลว์จาก n ที่มุ่งหน้าไปยัง โหนด ใน s-partition จะต้องถูกลบออกจาก stcut_flow กัน หลังจาก n ถูกย้ายไปยัง t-partition โฟลว์เหล่านี้จะถูกนำจาก t-partition และไปยัง s-partition เป็นต้น จะต้องไม่ถูกนำมาพิจารณาใน stcut_flow เนื่องจากโฟลว์เหล่านี้จะถูกลบการไหลเข้าของ s-partition และต้องถูกลดลงด้วยผลรวมของโฟลว์เหล่านี้ และการไหลออกจาก s-partition ไปยัง t-partition (ซึ่งทั้งหมดไหลจาก จะต้องลงเอยด้วย) จะต้องลดปริมาณลงเท่าเดิม เนื่องจาก โหนด n อยู่ในสภาวะสมดุลก่อนกระบวนการ การอัปเดตจะเพิ่มค่าเดียวกันให้กับค่า stcut_flow ใหม่ในขณะที่ลบออก ซึ่งจะทำให้ ข้อเสนอ E เป็นจริงหลังจากการอัพเดต ความถูกต้องของ ข้อเสนอ E ตามมาจากการเหนี่ยวนำกับขนาดของพาร์ติชัน t

ต่อไปนี้คือตัวอย่าง เครือข่ายโฟลว์ บางส่วนที่จะช่วยให้เห็นภาพกรณีที่ไม่ชัดเจนน้อยลงซึ่งมี ข้อเสนอ E ในภาพ พื้นที่สีแดงแสดงถึงพาร์ติชั่น s พื้นที่สีน้ำเงินแสดงถึงพาร์ติชั่น t และ ส่วนโค้ง สีเขียวหมายถึง st cut ในภาพที่สอง การไหลระหว่าง โหนด A และ โหนด B เพิ่มขึ้นในขณะที่การไหลไปยัง โหนดปลายทาง t ไม่เปลี่ยนแปลง:

ข้อ พิสูจน์: ไม่มีค่า กระแสการตัด ใด ๆ ที่จะเกินความสามารถของการ ตัด ใด ๆ

ข้อเสนอ F. (การไหลสูงสุด ทฤษฎีบทตัดขั้นต่ำ): ให้ f เป็น กระแส st 3 เงื่อนไขต่อไปนี้เทียบเท่า:

1. มีการ ตัด st ที่มีความจุเท่ากับมูลค่าของการไหล f .

2. f คือการ ไหลสูงสุด

3. ไม่มี เส้นทางเสริม เกี่ยวกับ f

เงื่อนไข 1 หมายถึงเงื่อนไข 2 โดยผลสืบเนื่อง เงื่อนไขที่ 2 หมายถึงเงื่อนไขที่ 3 เนื่องจากการมีอยู่ของเส้นทางเสริมหมายถึงการมีอยู่ของโฟลว์ที่มีค่ามากกว่า ซึ่งขัดแย้งกับค่าสูงสุดของ f เงื่อนไข 3 หมายถึงเงื่อนไข 1: ให้ C_s เป็นชุดของ โหนด ทั้งหมดที่สามารถเข้าถึงได้จาก s ด้วย เส้นทางการเติม ใน กราฟที่เหลือ ให้ C_t เป็นส่วน โค้ง ที่เหลือ จากนั้น t ต้องอยู่ใน C_t (ตามสมมติฐานของเรา) ส่วนโค้ง ที่ข้ามจาก C_s ไปยัง C_t จะสร้างการ ตัดแบบ st ซึ่งมีเพียง ส่วนโค้ง 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 วิธีนี้คือการค้นหา เส้นทาง การเสริมต่อไปและใช้การ augment กับ maxFlowSolution ล่าสุดซึ่งมาพร้อมกับโซลูชันที่ดีกว่า จนกว่าจะไม่มี เส้นทาง การเสริมอีกต่อไป หมายความว่า โซลูชันการไหลสูงสุด ล่าสุด เหมาะสมที่สุด

จาก 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 จากโมดูลคอลเลกชันหลาม

ในการตอบคำถามที่ 2 ข้างต้น ฉันจะถอดความข้อพิสูจน์อื่นจาก Sedgewick และ Wayne: Proposition G จำนวน เส้นทาง การเสริมที่จำเป็นในอัลกอริธึม Edmonds-Karp ที่มี โหนด N และ ส่วนโค้ง A มากที่สุดคือ NA/2 หลักฐาน: เส้นทาง การเสริมทุกเส้นมี ส่วนโค้ง คอขวด - ส่วนโค้ง ที่ถูกลบออกจาก กราฟที่เหลือ เพราะมันสอดคล้องกับ ส่วนโค้ง 'ดัน' ที่เติมความจุหรือ ส่วนโค้ง 'ดึง' ซึ่งการไหลจะกลายเป็น 0 แต่ละครั้ง arc กลายเป็นคอขวด arc ความยาวของ เส้นทางเสริม ใด ๆ ที่ผ่านไปจะต้องเพิ่มขึ้นเป็น 2 เท่า เนื่องจากแต่ละ โหนด ใน เส้นทาง อาจปรากฏขึ้นเพียงครั้งเดียวหรือไม่เลยก็ได้ (จากคำจำกัดความของ เส้นทาง ) เนื่องจาก เส้นทาง ถูก สำรวจจากเส้นทางที่สั้นที่สุดไปยัง เส้นทาง ที่ยาวที่สุด ซึ่งหมายความว่าต้องมีการเข้าชมโหนดอย่างน้อยหนึ่ง โหนด โดยเส้นทางถัดไปที่ผ่าน โหนด คอขวดโดยเฉพาะ ซึ่งหมายถึง ส่วนโค้ง เพิ่มเติม 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 ได้รับการปฏิบัติเหมือนเป็น strings และ uid ถึง nodes สำหรับโค้ดนี้ ให้ 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

ต่อไปนี้คือการแสดงภาพวิธีที่อัลกอริธึมนี้แก้ปัญหา เครือข่ายการไหล ตัวอย่างจากด้านบน การแสดงภาพแสดงขั้นตอนตามที่สะท้อนในได กราฟ G ซึ่งแสดงถึง เครือข่ายโฟ ลว์ที่เป็นปัจจุบันที่สุด และตามที่แสดงใน กราฟที่เหลือ ของเครือข่ายโฟลว์นั้น เส้นทาง การเติมใน กราฟที่เหลือ จะแสดงเป็นเส้นทางสีแดง และได กราฟ ที่แสดงถึงปัญหา ชุดของ โหนด และ ส่วนโค้ง ที่ได้รับผลกระทบจาก เส้นทาง การเสริมที่กำหนดจะถูกเน้นด้วยสีเขียว ในแต่ละกรณี ฉันจะเน้นส่วนต่างๆ ของกราฟที่จะมีการเปลี่ยนแปลง (สีแดงหรือสีเขียว) แล้วแสดงกราฟหลังการเปลี่ยนแปลง (เป็นสีดำเท่านั้น)

ต่อไปนี้คือการแสดงภาพอีกวิธีหนึ่งว่าอัลกอริธึมนี้แก้ปัญหา เครือข่ายโฟ ลว์ตัวอย่างต่างๆ ได้อย่างไร สังเกตว่าอันนี้ใช้ตัวเลขจริงและมี ส่วนโค้ง หลายส่วนที่มีค่า fromNode และ toNode กัน

**โปรดทราบด้วยว่าเนื่องจากส่วนโค้งที่มีการ 'ดึง' ResidualDatum อาจเป็นส่วนหนึ่งของเส้นทางการเพิ่ม โหนดที่ได้รับผลกระทบใน DiGraph ของเครือข่าย Flown _อาจไม่อยู่บนเส้นทางใน G! .

กราฟสองส่วน

สมมติว่าเรามี digraph G , G เป็น bipartite หากเป็นไปได้ที่จะแบ่งพาร์ติชัน โหนด ใน G.setOfNodes เป็นสองชุด ( part_1 และ part_2 ) เพื่อให้ ส่วนโค้ง ใด ๆ ใน G.setOfArcs a ไป ไม่ได้ ที่ a.fromNode ใน part_1 และ a.toNode ใน part_1 นอกจาก นี้ยังไม่สามารถเป็นจริงได้ ว่า a.fromNode ใน part_2 และ a.toNode ใน part_2

กล่าวอีกนัยหนึ่ง G เป็น สองฝ่าย หากสามารถแบ่งออกเป็นสองชุดของ โหนด เพื่อให้ทุก ส่วนโค้ง ต้องเชื่อมต่อ โหนด ในชุดหนึ่งกับ โหนด ในอีกชุดหนึ่ง

การทดสอบสองฝ่าย

สมมติว่าเรามีได กราฟ G เราต้องการทดสอบว่าเป็น แบบสองส่วน หรือไม่ เราสามารถทำได้ใน O(|G.setOfNodes|+|G.setOfArcs|) โดยการระบายสีกราฟเป็นสองสี

อันดับแรก เราต้องสร้างได กราฟ ใหม่ H กราฟนี้จะมีชุด โหนด เหมือนกับ G แต่จะมี ส่วนโค้ง มากกว่า G ทุก ส่วนโค้ง a ใน G จะสร้าง 2 ส่วนโค้ง ใน 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)

การจับคู่และการจับคู่สูงสุด

สมมติว่าเรามีได กราฟ G และ matching เป็นส่วนย่อยของ ส่วนโค้ง จาก G.setOfArcs matching คือการจับคู่ถ้าสำหรับสอง ส่วนโค้ง a และ b ใน matching : 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 ที่ สมบูรณ์แบบ ถ้าทุก ๆ สำหรับ โหนด n ใน G.setOfArcs มี ส่วนโค้ง ใน a matching โดยที่ a.fromNode == n or a.toNode == n

การจับคู่สองฝ่ายสูงสุด

การ จับคู่แบบสองฝ่ายสูงสุด คือการ จับคู่สูงสุด บน digraph G ซึ่งเป็น แบบสองส่วน

เนื่องจาก G เป็น ไบพาร์ไท ต์ ปัญหาในการค้นหาการ จับคู่แบบสองฝ่ายสูงสุด สามารถเปลี่ยนเป็น ปัญหาการไหลสูงสุด ที่แก้ไขได้ด้วยอัลกอริธึม Edmonds-Karp จากนั้นจึงกู้คืน การจับคู่แบบไบพาร์ไท ต์สูงสุดจากวิธีแก้ปัญหาไปยัง ปัญหาการไหลสูงสุด

ให้ bipartition เป็น bipartition ของ G

ในการทำเช่นนี้ ฉันต้องสร้างได กราฟ ใหม่ ( H ) พร้อม โหนด ใหม่ ( H.setOfNodes ) และส่วน โค้ง ใหม่บางส่วน ( H.setOfArcs ) H.setOfNodes มี โหนดทั้งหมด ใน G.setOfNodes และอีกสอง โหนด , s ( โหนดต้นทาง ) และ t ( โหนดเทอร์มินัล )

H.setOfArcs จะมีหนึ่ง ส่วนโค้ง สำหรับแต่ละ G.setOfArcs หาก ส่วนโค้ง a อยู่ใน G.setOfArcs และ a.fromNode อยู่ใน bipartition.firstPart และ a.toNode อยู่ใน bipartition.secondPart ให้รวม a ใน H (เพิ่ม FlowArcDatum(1,0) )

หาก a.fromNode อยู่ใน bipartition.secondPart และ a.toNode อยู่ใน bipartition.firstPart ให้รวม Arc(a.toNode,a.fromNode,FlowArcDatum(1,0)) ใน H.setOfArcs

คำจำกัดความของ กราฟสองส่วน ช่วยให้แน่ใจว่าไม่มี ส่วนโค้ง เชื่อมต่อ โหนดใดๆ โดยที่โหนด ทั้ง สองอยู่ในพาร์ติชั่นเดียวกัน H.setOfArcs ยังมี ส่วนโค้ง จาก โหนด s ยังแต่ละ โหนด ใน bipartition.firstPart ในที่สุด H.setOfArcs มี ส่วนโค้ง แต่ละ โหนด ใน bipartition.secondPart ถึง node t a.datum.capacity = 1 สำหรับทุก a ใน H.setOfArcs

ขั้นแรกให้แบ่ง โหนด ใน G.setOfNodes สองชุดที่ไม่ปะติดปะต่อกัน ( part1 และ part2 ) เพื่อให้ไม่มี ส่วนโค้ง ใน G.setOfArcs จากชุดหนึ่งไปยังชุดเดียวกัน (พาร์ติชั่นนี้เป็นไปได้เพราะ G เป็น bipartite ) ถัดไป เพิ่ม ส่วนโค้ง ทั้งหมดใน G.setOfArcs ซึ่งนำจาก part1 ถึง part2 ลงใน H.setOfArcs จากนั้นสร้าง โหนดต้นทาง เดียว 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

ฝาครอบโหนดขั้นต่ำ

ฝาครอบโหนดในได กราฟ G คือชุดของ โหนด ( cover ) จาก G.setOfNodes ซึ่งสำหรับ a โค้ง ใดๆ ของ G.setOfArcs จะต้องเป็นจริง: (a.fromNode in cover) or (a.toNode in cover)

โหนดที่ครอบน้อยที่สุดคือชุด โหนด ที่เล็กที่สุดในกราฟที่ยังคงเป็น โหนดครอบ ทฤษฎีบทของ Konig ระบุว่าใน กราฟสองส่วน ขนาดของการ จับคู่สูงสุด บนกราฟนั้นเท่ากับขนาดของ ฝาครอบโหนดที่เล็กที่สุด และแสดงให้เห็นว่า ฝาครอบโหนด สามารถกู้คืนจากการ จับคู่สูงสุดได้ อย่างไร :

สมมติว่าเรามี bipartition bipartition และค่าที่ matching สูงสุด กำหนดได กราฟ ใหม่ H , H.setOfNodes=G.setOfNodes ส่วนโค้ง ใน H.setOfArcs เป็นการรวมกันของสองชุด

ชุดแรกเป็น ส่วนโค้ง a ใน matching โดยการเปลี่ยนแปลงที่หาก a.fromNode in bipartition.firstPart และ a.toNode in bipartition.secondPart แล้ว a.fromNode และ a.toNode จะถูกสลับใน ส่วนโค้ง ที่สร้างขึ้น ให้ ส่วนโค้ง ดังกล่าว a.datum.inMatching=True แอตทริบิวต์เพื่อระบุว่าได้มาจาก ส่วนโค้ง ในการ จับคู่

ชุดที่สองเป็น ส่วนโค้ง a ไม่ matching โดยมีการเปลี่ยนแปลงว่าหาก 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 ที่ไม่น่าจะครอบคลุม และพิจารณาทั้งสี่กรณีว่า a.fromNode และ a.toNode เป็นของ (ไม่ว่าจะเป็น toNode หรือ fromNode ) ไปยัง ส่วนโค้ง ใด ๆ ใน การจับ คู่ที่ matching แต่ละกรณีนำไปสู่ความขัดแย้งอันเนื่องมาจากลำดับที่ DFS เยี่ยมชม โหนด และข้อเท็จจริงที่ว่าการ matching เป็นการ จับคู่สูงสุด

สมมติว่าเรามีฟังก์ชันเพื่อดำเนินการตามขั้นตอนเหล่านี้และส่งคืนชุดของ โหนด ที่ประกอบด้วย โหนดที่ครอบน้อยที่สุด เมื่อกำหนดได กราฟ 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

อัลกอริทึม 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 แก้ปัญหา การจับคู่น้ำหนักขั้นต่ำในกราฟสองส่วนแบบถ่วงน้ำหนัก ด้วยลำดับการ จับคู่สูงสุด ใน กราฟสองส่วนแบบ ไม่ถ่วงน้ำหนัก หาก a เราพบการ จับคู่ที่สมบูรณ์แบบ บนการแสดงได กราฟ ของ ปัญหาการกำหนดเชิงเส้น และหากน้ำหนักของ ส่วนโค้ง ทุกส่วนในการ จับคู่ เป็นศูนย์ เราก็พบการ จับคู่น้ำหนักขั้นต่ำ แล้ว เนื่องจากการจับคู่นี้แสดงให้เห็นว่า โหนด ทั้งหมดในได กราฟ นั้นเป็น จับคู่ โดย ส่วนโค้ง ที่มีต้นทุนต่ำที่สุด (ไม่มีต้นทุนต่ำกว่า 0 ตามคำจำกัดความก่อนหน้า)

ไม่สามารถเพิ่ม ส่วนโค้ง อื่น ๆ ให้กับการ จับคู่ ได้ (เนื่องจาก โหนด ทั้งหมดตรงกันแล้ว) และไม่ควรลบ ส่วนโค้ง ออกจากการ จับคู่ เนื่องจาก ส่วนโค้ง ทดแทนใดๆ ที่เป็นไปได้จะมีค่าน้ำหนักอย่างน้อยเท่ากับค่าน้ำหนัก

หากเราพบการ จับคู่สูงสุด ของกราฟย่อยของ G ซึ่งมี ส่วนโค้งน้ำหนักเป็นศูนย์ เท่านั้น และไม่ใช่การ จับคู่ที่สมบูรณ์แบบ เราไม่มีวิธีแก้ปัญหาที่สมบูรณ์ (เนื่องจากการ จับคู่ ไม่ สมบูรณ์แบบ ) อย่างไรก็ตาม เราสามารถสร้างได กราฟ H ใหม่ได้โดยการเปลี่ยนน้ำหนักของ ส่วนโค้ง ใน G.setOfArcs ในลักษณะที่ ส่วนโค้ง น้ำหนัก 0 ใหม่ปรากฏขึ้น และวิธีแก้ปัญหาที่ดีที่สุดของ H จะเหมือนกับวิธีแก้ปัญหาที่ดีที่สุดของ G เนื่องจากเรารับประกันว่ามีการสร้าง ส่วนโค้งของน้ำหนักเป็นศูนย์ อย่างน้อยหนึ่งส่วนในการทำซ้ำแต่ละครั้ง เรารับประกันว่าเราจะได้รับการ จับคู่ที่สมบูรณ์แบบ ในการทำซ้ำดังกล่าวไม่เกิน |G.setOfNodes|^{2}=N^{2}

สมมติว่าใน bipartition bipartition , bipartition.firstPart มี โหนดที่ เป็นตัวแทนของคนงาน และ bipartition.secondPart แสดงถึง โหนด ที่แสดงถึงงาน

อัลกอริทึมเริ่มต้นด้วยการสร้างได กราฟ 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: ต่อไป สร้างได กราฟ ใหม่ K ซึ่งประกอบด้วย ส่วนโค้งน้ำหนักเป็นศูนย์ จาก H และ โหนด ที่เกิดขึ้นบน ส่วนโค้ง เหล่านั้น สร้างสองพาร์ติชั่นบน โหนด ใน K จากนั้นใช้ solve_mbm( bipartition ) bipartition รับการ จับคู่สูงสุด ( matching ) บน K หาก matching เป็นการ จับคู่ที่สมบูรณ์แบบ ใน H ( ส่วนโค้ง ใน matching เกิดขึ้น กับ โหนด ทั้งหมดใน 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