วิทยาศาสตร์ข้อมูลและฐานข้อมูล

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



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

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



การจับคู่ Bipartite



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



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

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

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



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

รอบคัดเลือก

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



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

การนำไปใช้ในโพสต์นี้แสดงถึงปัญหาเป็นกราฟที่กำหนด (digraph)



DiGraphs

ถึง Digraph มีสอง คุณลักษณะ , setOfNodes และ setOfArcs . คุณลักษณะทั้งสองนี้คือ ชุด (คอลเลกชันที่ไม่มีการเรียงลำดับ) ในบล็อกโค้ดของโพสต์นี้ฉันใช้ Python’s Frozenset แต่รายละเอียดนั้นไม่สำคัญเป็นพิเศษ

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

(หมายเหตุ: นี่และโค้ดอื่น ๆ ทั้งหมดในบทความนี้เขียนด้วย Python 3.6)



โหนด

ถึง โหนด n ประกอบด้วยสองคุณลักษณะ:

x.uid != y.uid
  • n.datum: สิ่งนี้แสดงถึงออบเจ็กต์ข้อมูลใด ๆ
Node = namedtuple('Node', ['uid','datum'])

Arcs

อัน ส่วนโค้ง 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 มีอยู่

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

DiGraphs

โหนด และ ส่วนโค้ง สามารถใช้เพื่อกำหนดไฟล์ Digraph แต่เพื่อความสะดวกในอัลกอริทึมด้านล่างก 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()

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

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

นี่เป็นของฉัน Digraph การเป็นตัวแทน มีหลายคนที่ชอบ แต่อันนี้เป็นของฉัน

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

ให้ S_Arcs เป็นที่แน่นอน ลำดับ (คอลเลกชันที่สั่งซื้อ) จาก ส่วนโค้ง ใน Digraph 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 ก เดิน บน 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

การตัดและการตัด

ถึง ตัด cut ของก เชื่อมต่อ Digraph 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 เป็น ตัด ของ 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 เรียกว่า ตัด x-y ถ้า (x in get_first_part(cut, G)) and (y in get_second_part(cut, G) ) and (x != y). เมื่อ โหนด x ใน ตัด x-y cut คือ โหนดต้นทาง และ โหนด y ใน ตัด x-y คือ โหนดเทอร์มินัล แล้วนี่ ตัด เรียกว่า ตัด s-t .

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

เครือข่ายกระแส

คุณสามารถใช้ไฟล์ Digraph 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 เรียกว่า a ข้อ จำกัด ในการอนุรักษ์ .

เงื่อนไขที่ 2 เรียกว่า a ข้อ จำกัด ด้านความจุ .

ตัดความจุ

ความสามารถในการตัด ของ ตัด s-t 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) ถั่ว ตัด s-t ของก เครือข่ายการไหล แสดงโดย Digraph G.

stCut คือ ตัดกำลังการผลิตขั้นต่ำ ของ เครือข่ายการไหล แสดงโดย G ถ้าไม่มีอย่างอื่น ตัด s-t stCutCompetitor ในเรื่องนี้ เครือข่ายการไหล ดังนั้น:

cut_capacity(stCut, 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 .

แล้ว 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) ขณะข้าม (อื่น ๆ ) โหนด ( ข้อ จำกัด ในการอนุรักษ์ ).

ความแตกต่างใน c corp และ s corp

ตั้งแต่ก ปัญหาการไหลสูงสุด มีเพียงไฟล์เดียว โหนดต้นทาง s และหนึ่งเดียว โหนดเทอร์มินัล t, ขั้นตอนทั้งหมดที่ 'สร้าง' ที่ s จะต้องถูก 'ทำลาย' ที่ t หรือ เครือข่ายการไหล ทำ ไม่ มี กระแสที่เป็นไปได้ (ที่ ข้อ จำกัด ในการอนุรักษ์ จะถูกละเมิด)

ปล่อย Digraph H เป็นตัวแทนของ โซลูชันการไหลสูงสุดที่เป็นไปได้ ; ค่าข้างต้นเรียกว่า s-t Flow มูลค่า ของ H.

ปล่อย:

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

ซึ่งหมายความว่า mfps คือ รัฐผู้สืบทอด ของ maxFlowProblem ซึ่งหมายความว่า mfps เป็นเหมือนอย่างมาก maxFlowProblem ยกเว้นค่าของ a.flow สำหรับ arcs a ใน maxFlowProblem.setOfArcs อาจแตกต่างจาก a.flow สำหรับ arcs 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 s-t flow') return flow_to_t

นี่คือภาพของ mfps พร้อมกับที่เกี่ยวข้อง maxFlowProb. แต่ละ ส่วนโค้ง a ในภาพมีป้ายกำกับป้ายเหล่านี้คือ a.datum.flowFrom / a.datum.flowTo แต่ละป้าย โหนด n ในภาพมีป้ายกำกับและป้ายกำกับเหล่านี้คือ n.uid {n.datum.flowIn / a.datum.flowOut}

การแสดงภาพกระแสสูงสุด

s-t ตัดกระแส

ให้ 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

s-t ตัดกระแส คือผลรวมของกระแสจากพาร์ติชันที่มีไฟล์ โหนดต้นทาง ไปยังพาร์ติชันที่มีไฟล์ โหนดเทอร์มินัล ลบผลรวมของโฟลว์จากพาร์ติชันที่มี โหนดเทอร์มินัล ไปยังพาร์ติชันที่มีไฟล์ โหนดต้นทาง .

Max Flow, Min Cut

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

ให้ minStCut เป็น ตัดกำลังการผลิตขั้นต่ำ ของ เครือข่ายการไหล แสดงโดย maxFlowProblem.G.

เพราะว่าใน ปัญหาการไหลสูงสุด โฟลว์เกิดขึ้นเพียงครั้งเดียว โหนดต้นทาง และสิ้นสุดในครั้งเดียว โหนดเทอร์มินัล และเนื่องจากไฟล์ ข้อ จำกัด ด้านความจุ และ ข้อ จำกัด ในการอนุรักษ์ เรารู้ว่ากระแสทั้งหมดเข้า maxFlowProblem.terminalNodeUid ต้องข้ามใด ๆ ตัด s-t โดยเฉพาะอย่างยิ่งต้องข้าม 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)) ของสิ่งที่พบล่าสุด โซลูชันการไหลสูงสุด (K) ดีกว่าเป็นไหน ๆ โซลูชันการไหลสูงสุด ที่ได้พบ หากกระบวนการไปถึงจุดที่รู้ว่าไม่มีการปรับปรุงอื่น ๆ เป็นไปได้กระบวนการสามารถยุติและจะส่งคืนไฟล์ เหมาะสมที่สุด โซลูชันการไหลสูงสุด .

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

กระแสสูงสุดทฤษฎีบทตัดขั้นต่ำ

จากหนังสือ กระแสในเครือข่ายโดย Ford และ Fulkerson , คำสั่งของ การไหลสูงสุดทฤษฎีบทตัดขั้นต่ำ (ทฤษฎีบท 5.1) คือ:

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

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

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

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

ฉันชอบ หลักฐานนี้ ของทฤษฎีบทและวิกิพีเดียมี อีกอัน .

การไหลสูงสุดทฤษฎีบทตัดขั้นต่ำ ใช้เพื่อพิสูจน์ความถูกต้องและสมบูรณ์ของไฟล์ วิธีการของ 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 แสดงถึงการกระทำบางอย่างที่สามารถทำได้บนไฟล์ Digraph 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 แสดงถึงไฟล์ ส่วนโค้ง ติดป้าย 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 แสดงถึงไฟล์ ส่วนโค้ง ติดป้าย 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 ที่ไหน ส่วนโค้ง a อยู่ในส่วนย่อยถ้า a.fromNode = n และ 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) ถ้า 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) ถ้า H ไม่ใช่ เหมาะสมที่สุด .

นี่คือเหตุผล: สำหรับไฟล์ เพิ่มเส้นทาง augmentingPath ที่จะมีอยู่ในไฟล์ Digraph การเป็นตัวแทนของ กราฟที่เหลือ G_f ของก ปัญหาการไหลสูงสุด maxFlowProblem สุดท้ายแล้ว ส่วนโค้ง a บน augmentingPath ต้องเป็น 'push' ส่วนโค้ง และต้องมี a.toNode == maxFlowProblem.terminalNode. อัน เพิ่มเส้นทาง ถูกกำหนดให้เป็นสิ่งที่สิ้นสุดที่ไฟล์ โหนดเทอร์มินัล ของ ปัญหาการไหลสูงสุด ซึ่งเป็นไฟล์ เพิ่มเส้นทาง . จากคำจำกัดความของ กราฟที่เหลือ เป็นที่ชัดเจนว่าสุดท้าย ส่วนโค้ง ใน เพิ่มเส้นทาง ที่ กราฟที่เหลือ ต้องเป็น 'push' ส่วนโค้ง เพราะ 'ดึง' ใด ๆ ส่วนโค้ง b ใน เพิ่มเส้นทาง จะมี b.toNode == maxFlowProblem.terminalNode และ b.fromNode != maxFlowProblem.terminalNode จากคำจำกัดความของ เส้นทาง . นอกจากนี้จากคำจำกัดความของ เส้นทาง เป็นที่ชัดเจนว่า โหนดเทอร์มินัล ถูกแก้ไขเพียงครั้งเดียวโดย augment วิธี. ดังนั้น augment แก้ไข maxFlowProblem.terminalNode.flowIn เพียงครั้งเดียวและจะเพิ่มมูลค่าของ maxFlowProblem.terminalNode.flowIn เพราะสุดท้าย ส่วนโค้ง ใน augmentingPath ต้องเป็นไฟล์ ส่วนโค้ง ซึ่งทำให้เกิดการแก้ไขใน maxFlowProblem.terminalNode.flowIn ระหว่าง augment. จากความหมายของ augment ตามที่ใช้กับ 'push' ส่วนโค้ง , ที่ maxFlowProblem.terminalNode.flowIn สามารถเพิ่มขึ้นไม่ลดลง

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

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

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

Corollary: ไม่ s-t ตัดกระแส ค่าสามารถเกินขีดความสามารถใด ๆ ตัด s-t .

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

  1. มีไฟล์ ตัด s-t ซึ่งมีความจุเท่ากับค่าของการไหล f

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

  3. ไม่มี เพิ่มเส้นทาง ด้วยความเคารพ f.

เงื่อนไขที่ 1 หมายถึงเงื่อนไข 2 โดยคอร์โรลลารี เงื่อนไข 2 หมายถึงเงื่อนไขที่ 3 เนื่องจากการมีอยู่ของเส้นทางการขยายหมายถึงการมีอยู่ของโฟลว์ที่มีค่ามากขึ้นซึ่งขัดแย้งกับค่าสูงสุดของ f เงื่อนไขที่ 3 หมายถึงเงื่อนไขที่ 1: ให้ C_s เป็นชุดของทั้งหมด โหนด ที่สามารถเข้าถึงได้จาก s ด้วย เพิ่มเส้นทาง ใน กราฟที่เหลือ . ให้ C_t เป็นส่วนที่เหลือ ส่วนโค้ง แล้ว t ต้องอยู่ใน C_t (ตามสมมติฐานของเรา) ส่วนโค้ง ข้ามจาก C_s ถึง C_t จากนั้นสร้างไฟล์ ตัด s-t ซึ่งมีเฉพาะ ส่วนโค้ง a โดยที่ a.datum.capacity = a.datum.flow หรือ a.datum.flow = 0.0. หากเป็นอย่างอื่นแล้วไฟล์ โหนด เชื่อมต่อด้วยไฟล์ ส่วนโค้ง ที่มีกำลังการผลิตคงเหลือถึง C_s จะอยู่ในชุด C_s ตั้งแต่นั้นมาจะมีไฟล์ เพิ่มเส้นทาง จาก s เป็นเช่นนั้น โหนด . การไหลข้าม ตัด s-t เท่ากับ s-t cut’s ความจุ (ตั้งแต่ ส่วนโค้ง จาก C_s ถึง C_t มีการไหลเท่ากับความจุ) และค่าของ s-t ไหล (โดย โจทย์ E ).

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

Corollary (คุณสมบัติเชิงปริพันธ์): เมื่อความจุเป็นจำนวนเต็มจะมีโฟลว์สูงสุดที่มีมูลค่าเป็นจำนวนเต็มและอัลกอริทึมของ Ford-Fulkerson พบ

หลักฐาน: แต่ละ เพิ่มเส้นทาง เพิ่มการไหลด้วยจำนวนเต็มบวกค่าต่ำสุดของความจุที่ไม่ได้ใช้ใน 'push' ส่วนโค้ง และกระแสใน 'ดึง' ส่วนโค้ง ซึ่งทั้งหมดนี้เป็นจำนวนเต็มบวกเสมอ

สิ่งนี้แสดงให้เห็นถึง วิธีการของ 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 จากโมดูลคอลเลกชัน python .

เพื่อตอบคำถาม 2 ข้างต้นฉันจะถอดความหลักฐานอื่นจาก Sedgewick และ Wayne : ข้อเสนอช. จำนวน การเพิ่มเส้นทาง จำเป็นในไฟล์ เอ็ดมันด์ - คาร์ป อัลกอริทึมด้วย N โหนด และ A ส่วนโค้ง มากที่สุด NA/2. หลักฐาน: ทุกๆ เพิ่มเส้นทาง มี คอขวด ส่วนโค้ง - ก ส่วนโค้ง ที่ถูกลบออกจากไฟล์ กราฟที่เหลือ เนื่องจากสอดคล้องกับ 'push' ส่วนโค้ง ที่เต็มไปด้วยความจุหรือ 'ดึง' ส่วนโค้ง ซึ่งกระแสจะกลายเป็น 0 แต่ละครั้งที่ ส่วนโค้ง กลายเป็นคอขวด ส่วนโค้ง ความยาวใด ๆ เพิ่มเส้นทาง จะต้องเพิ่มขึ้นโดยปัจจัย 2 เนื่องจากแต่ละอย่าง โหนด ใน เส้นทาง อาจปรากฏเพียงครั้งเดียวหรือไม่ปรากฏเลย (จากคำจำกัดความของ เส้นทาง ) ตั้งแต่ เส้นทาง กำลังสำรวจจากระยะสั้นที่สุด เส้นทาง ยาวที่สุดนั่นหมายความว่าอย่างน้อยก็อีกอย่างหนึ่ง โหนด จะต้องไปตามเส้นทางถัดไปที่ผ่านคอขวดโดยเฉพาะ โหนด นั่นหมายถึงอีก 2 ส่วนโค้ง บนเส้นทางก่อนที่เราจะมาถึง โหนด . ตั้งแต่ เพิ่มเส้นทาง มีความยาวมากที่สุด N แต่ละ ส่วนโค้ง ได้มากที่สุด N/2 การเพิ่มเส้นทาง และจำนวน การเพิ่มเส้นทาง มากที่สุด NA/2.

อัลกอริทึม Edmonds-Karp ดำเนินการใน O(NA^2). ถ้ามากที่สุด NA/2 เส้นทาง จะถูกสำรวจระหว่างอัลกอริทึมและการสำรวจแต่ละขั้นตอน เส้นทาง ด้วย BFS คือ N+A จากนั้นคำที่สำคัญที่สุดของผลิตภัณฑ์และด้วยเหตุนี้ความซับซ้อนของ asymptotic คือ 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) เนื่องจากสร้างไฟล์ โซลูชันการไหลสูงสุด และใหม่ก กราฟที่เหลือ ทุกครั้ง (แทนที่จะแก้ไขที่มีอยู่ Digraphs เมื่ออัลกอริทึมก้าวหน้าขึ้น) เพื่อไปสู่ความจริง O(NA^2) วิธีแก้ปัญหาอัลกอริทึมต้องรักษาทั้ง Digraph เป็นตัวแทนของ สถานะปัญหาการไหลสูงสุด และที่เกี่ยวข้อง กราฟที่เหลือ . ดังนั้นอัลกอริทึมต้องหลีกเลี่ยงการทำซ้ำ ส่วนโค้ง และ โหนด โดยไม่จำเป็นและอัปเดตค่าและค่าที่เกี่ยวข้องในไฟล์ กราฟที่เหลือ เท่าที่จำเป็นเท่านั้น

เพื่อเขียนได้เร็วขึ้น เอดมันด์คาร์ป อัลกอริทึมฉันเขียนโค้ดใหม่หลายชิ้นจากด้านบน ฉันหวังว่าการใช้รหัสที่สร้างไฟล์ Digraph เป็นประโยชน์ในการทำความเข้าใจสิ่งที่เกิดขึ้น ในอัลกอริทึมที่รวดเร็วฉันใช้เทคนิคใหม่ ๆ และโครงสร้างข้อมูล Python ที่ฉันไม่ต้องการอธิบายรายละเอียด ฉันจะบอกว่า a.fromNode และ a.toNode ตอนนี้ถือว่าเป็นสตริงและ uids to โหนด . สำหรับรหัสนี้ให้ 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 s-t 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 เป็นตัวแทนที่ทันสมัยที่สุด เครือข่ายการไหล และตามที่สะท้อนให้เห็นในไฟล์ กราฟที่เหลือ ของเครือข่ายโฟลว์นั้น เพิ่มเส้นทาง ใน กราฟที่เหลือ จะแสดงเป็นเส้นทางสีแดงและ Digraph แทนปัญหาชุดของ โหนด และ ส่วนโค้ง ได้รับผลกระทบจากการกำหนด เพิ่มเส้นทาง จะเน้นด้วยสีเขียว ในแต่ละกรณีฉันจะเน้นส่วนของกราฟที่จะเปลี่ยน (เป็นสีแดงหรือสีเขียว) จากนั้นจึงแสดงกราฟหลังการเปลี่ยนแปลง (เพียงแค่เป็นสีดำ)

การแสดงภาพกระแสสูงสุด

การแสดงภาพกระแสสูงสุด (ส่วนที่เหลือ)

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

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

กราฟ Bipartite

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

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

การทดสอบ Bipartite

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

ขั้นแรกเราต้องสร้างไฟล์ Digraph 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)

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

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

ถึง การจับคู่สูงสุด matching คือ การจับคู่ที่สมบูรณ์แบบ ถ้าทุกๆ โหนด n ใน G.setOfArcs มีไฟล์ ส่วนโค้ง a ใน matching ที่ไหน a.fromNode == n or a.toNode == n.

การจับคู่ Bipartite สูงสุด

ถึง การจับคู่สองฝ่ายสูงสุด คือ การจับคู่สูงสุด สิบก Digraph G ซึ่งเป็น สองฝ่าย .

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

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

ในการดำเนินการนี้ฉันต้องสร้างไฟล์ Digraph (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 ถึง โหนด t. a.datum.capacity = 1 สำหรับทุกคน a ใน H.setOfArcs.

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

ฝาปิดโหนดน้อยที่สุด

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

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

สมมติว่าเรามีไฟล์ bipartition bipartition และ การจับคู่สูงสุด matching. กำหนดไฟล์ Digraph 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 คือ การจับคู่สูงสุด .

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

อัลกอริทึม Kuhn-Munkres แก้ปัญหา ปัญหาการกำหนดเชิงเส้น . การนำไปใช้ที่ดีสามารถใช้ O(N^{4}) เวลา (โดยที่ N คือจำนวน โหนด ใน Digraph เป็นตัวแทนของปัญหา) การใช้งานที่ง่ายต่อการอธิบายใช้เวลา O(N^{5}) (สำหรับเวอร์ชันที่สร้างใหม่ DiGraphs ) และ O(N^{4}) สำหรับ (สำหรับเวอร์ชันที่มีไฟล์ DiGraphs ). สิ่งนี้คล้ายกับการใช้งาน เอ็ดมันด์ - คาร์ป อัลกอริทึม

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

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

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

โชคดีที่เลี้ยวง่าย ปัญหาการกำหนดเส้นตรงสูงสุด เป็น ปัญหาการกำหนดเส้นตรงขั้นต่ำ โดยการตั้งค่า ส่วนโค้ง a น้ำหนักถึง M-a.datum.weight ที่ไหน M=max({a.datum.weight for a in G.setOfArcs}). การแก้ปัญหาแบบเดิม การเพิ่มปัญหา จะเหมือนกับโซลูชัน การลดปัญหา หลังจาก ส่วนโค้ง น้ำหนักมีการเปลี่ยนแปลง ดังนั้นสำหรับส่วนที่เหลือสมมติว่าเราทำการเปลี่ยนแปลงนี้

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

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

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

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

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 ในการทำซ้ำแต่ละครั้ง คล้ายกับการใช้งานสองครั้งก่อนหน้านี้ของ เอ็ดมันด์ - คาร์ป อัลกอริทึมนี้สามารถแก้ไขได้เพื่อให้ติดตามการจับคู่และปรับให้เข้ากับการทำซ้ำแต่ละครั้งอย่างชาญฉลาด เมื่อเสร็จแล้วความซับซ้อนจะกลายเป็น O(N^{4}) อัลกอริทึมรุ่นขั้นสูงและใหม่กว่านี้ (ต้องการโครงสร้างข้อมูลขั้นสูงเพิ่มเติม) สามารถรันใน O(N^{3}) สามารถดูรายละเอียดของการใช้งานที่ง่ายกว่าข้างต้นและการใช้งานขั้นสูงได้ที่ โพสต์นี้ ซึ่งกระตุ้นให้โพสต์บล็อกนี้

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

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

การมอบหมายงานที่ไม่สมดุล

ดูเหมือนว่าอัลกอริทึมจะค่อนข้าง จำกัด เนื่องจากตามที่อธิบายไว้จะทำงานบนเท่านั้น กราฟสองฝ่ายที่สมบูรณ์ (ผู้ที่ครึ่งหนึ่ง โหนด อยู่ในส่วนหนึ่งของไฟล์ bipartition และอีกครึ่งหนึ่งในส่วนที่สอง) ในคนงานแรงจูงใจในการทำงานหมายความว่ามีคนงานมากพอ ๆ กับงาน (ดูเหมือนค่อนข้าง จำกัด )

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

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

ความเสี่ยงจากอัตราแลกเปลี่ยนประเภทใดที่สำคัญ

ตัวอย่างการกำหนดเชิงเส้น

สุดท้ายมาดูตัวอย่างรหัสที่ฉันใช้อยู่ ฉันจะแก้ไขปัญหาตัวอย่างจาก ที่นี่ . เรามีงาน 3 อย่าง: เราต้องทำ ทำความสะอาดห้องน้ำ , กวาดพื้น และ ล้างหน้าต่าง .

คนงานที่มีให้ใช้คือ อลิซ , บ๊อบ , ชาร์ลี และ ไดแอน . คนงานแต่ละคนให้ค่าจ้างที่เราต้องการต่องาน นี่คือค่าจ้างต่อคนงาน:

ทำความสะอาดห้องน้ำ กวาดพื้น ล้างหน้าต่าง
อลิซ $ 2 $ 3 $ 3
บ๊อบ $ 3 $ 2 $ 3
ชาร์ลี $ 3 $ 3 $ 2
ไดแอน $ 9 $ 9 $ 1

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

ทำความสะอาดห้องน้ำ กวาดพื้น ล้างหน้าต่าง ไม่ทำอะไร
อลิซ $ 2 $ 3 $ 3 $ 0
บ๊อบ $ 3 $ 2 $ 3 $ 0
ชาร์ลี $ 3 $ 3 $ 2 $ 0
ไดแอน $ 9 $ 9 $ 1 $ 0

สมมติว่าปัญหาถูกเข้ารหัสเป็นไฟล์ Digraph แล้ว kuhn_munkres( bipartition(G) ) จะแก้ปัญหาและส่งคืนงาน ตรวจสอบได้ง่ายว่าการมอบหมายงานที่เหมาะสมที่สุด (ต้นทุนต่ำสุด) จะมีราคา $ 5

นี่คือภาพของโซลูชันที่โค้ดด้านบนสร้างขึ้น:

การแสดงภาพกระแสสูงสุด

การแสดงภาพกระแสสูงสุด (ส่วนที่เหลือ)

อย่างนั้นแหละ. ตอนนี้คุณรู้ทุกสิ่งที่คุณจำเป็นต้องรู้เกี่ยวกับปัญหาการกำหนดเชิงเส้นแล้ว

คุณสามารถค้นหาโค้ดทั้งหมดได้จากบทความนี้บน GitHub .

Zero Downtime Jenkins การปรับใช้อย่างต่อเนื่องกับ Terraform บน AWS

เทคโนโลยี

Zero Downtime Jenkins การปรับใช้อย่างต่อเนื่องกับ Terraform บน AWS
สำรวจ Bear Case ของ Cryptocurrency Bubble

สำรวจ Bear Case ของ Cryptocurrency Bubble

กระบวนการทางการเงิน