นี่คือปัญหา: บริษัท ของคุณมอบหมายให้ผู้รับเหมาทำตามสัญญา คุณดูรายชื่อของคุณและตัดสินใจว่าจะมีผู้รับเหมารายใดบ้างสำหรับสัญญาระยะยาวหนึ่งเดือนและตรวจสอบสัญญาที่มีอยู่ของคุณเพื่อดูว่าสัญญาใดบ้างสำหรับการมอบหมายงานตลอดทั้งเดือน เนื่องจากคุณทราบดีว่าผู้รับเหมาแต่ละรายสามารถปฏิบัติตามสัญญาแต่ละฉบับได้อย่างมีประสิทธิภาพคุณจะมอบหมายผู้รับเหมาเพื่อเพิ่มประสิทธิผลโดยรวมในเดือนนั้นได้อย่างไร
นี่คือตัวอย่างของปัญหาการมอบหมายและปัญหานี้สามารถแก้ไขได้ด้วยคลาสสิก อัลกอริทึมฮังการี .
อัลกอริทึมฮังการี (หรือที่เรียกว่าอัลกอริทึม Kuhn-Munkres) เป็นอัลกอริธึมเวลาแบบพหุนามซึ่งเพิ่มน้ำหนักให้สูงสุดบนกราฟสองส่วนที่ถ่วงน้ำหนัก ที่นี่ผู้รับเหมาและสัญญาสามารถสร้างแบบจำลองเป็นกราฟสองฝ่ายโดยมีประสิทธิภาพเป็นน้ำหนักของขอบระหว่างผู้รับเหมาและโหนดสัญญา
ในบทความนี้คุณจะได้เรียนรู้เกี่ยวกับการใช้อัลกอริทึมฮังการีที่ใช้ไฟล์ อัลกอริทึม Edmonds-Karp เพื่อแก้ปัญหาการกำหนดเส้นตรง นอกจากนี้คุณยังจะได้เรียนรู้ว่าอัลกอริทึม Edmonds-Karp เป็นการปรับเปลี่ยนเล็กน้อยของไฟล์ ฟอร์ด - ฟุลเคอร์สัน และความสำคัญของการปรับเปลี่ยนนี้
ปัญหาการไหลสูงสุดสามารถอธิบายได้อย่างไม่เป็นทางการว่าเป็นปัญหาของการเคลื่อนย้ายของเหลวหรือก๊าซบางส่วนผ่านเครือข่ายของท่อจากแหล่งเดียวไปยังขั้วเดียว สิ่งนี้ทำได้โดยสมมติว่าความดันในเครือข่ายเพียงพอที่จะทำให้แน่ใจได้ว่าของเหลวหรือก๊าซไม่สามารถอยู่ในความยาวของท่อหรือข้อต่อท่อใด ๆ (สถานที่ที่มีความยาวต่างกันของท่อ)
เมื่อทำการเปลี่ยนแปลงบางอย่างกับกราฟปัญหาการจัดสรรอาจกลายเป็นปัญหาการไหลสูงสุด
แนวคิดที่จำเป็นในการแก้ปัญหาเหล่านี้เกิดขึ้นในหลายสาขาวิชาคณิตศาสตร์และวิศวกรรมโดยมากแนวคิดที่คล้ายกันมักรู้จักกันในชื่อที่แตกต่างกันและแสดงออกในรูปแบบที่แตกต่างกัน เนื่องจากแนวคิดเหล่านี้ค่อนข้างลึกลับจึงมีตัวเลือกว่าโดยทั่วไปแล้วแนวคิดเหล่านี้จะถูกกำหนดอย่างไรสำหรับการตั้งค่าใด ๆ
บทความนี้จะไม่ถือว่าความรู้เดิมใด ๆ นอกเหนือไปจากทฤษฎีเซตเบื้องต้นสั้น ๆ
การนำไปใช้ในโพสต์นี้แสดงถึงปัญหาเป็นกราฟที่กำหนด (digraph)
ก digrafo มีสอง คุณลักษณะ , setOfNodes ย setOfArcs . คุณลักษณะทั้งสองนี้คือ ชุด (คอลเลกชันที่ยุ่งเหยิง) ในบล็อกโค้ดในโพสต์นี้ฉันใช้ Python Frozenset แต่รายละเอียดนั้นไม่สำคัญเป็นพิเศษ
DiGraph = namedtuple('DiGraph', ['setOfNodes','setOfArcs'])
(หมายเหตุ: โค้ดนี้และโค้ดอื่น ๆ ทั้งหมดในบทความนี้เขียนด้วย Python 3.6)
ก โหนด n
ประกอบด้วยสองคุณลักษณะ:
n.uid
: ก ตัวระบุที่ไม่ซ้ำกัน .
ซึ่งหมายความว่าสำหรับสองโหนด x
และ y
,
x.uid != y.uid
n.datum
: สิ่งนี้แสดงถึงออบเจ็กต์ข้อมูลใด ๆNode = namedtuple('Node', ['uid','datum'])
ก ส่วนโค้ง a
ประกอบด้วยสามคุณลักษณะ:
a.fromNode
: นี่คือไฟล์ โหนด ตามที่กำหนดไว้ข้างต้น
a.toNode
: นี่คือไฟล์ โหนด ตามที่กำหนดไว้ข้างต้น
a.datum
: สิ่งนี้แสดงถึงออบเจ็กต์ข้อมูลใด ๆ
Arc = namedtuple('Arc', ['fromNode','toNode','datum'])
ชุดของ คันธนู ที่ Digraph แสดงถึงความสัมพันธ์แบบไบนารีใน โหนด ที่ Digraph . การดำรงอยู่ของ ส่วนโค้ง a
หมายความว่ามีความสัมพันธ์ระหว่าง a.fromNode
และ a.toNode
.
ในกราฟกำกับ (ตรงข้ามกับกราฟที่ไม่มีทิศทาง) การมีอยู่ของความสัมพันธ์ระหว่าง a.fromNode
และ a.toNode
ไม่ บ่งบอกถึงความสัมพันธ์ที่คล้ายกันระหว่าง a.toNode
และ a.fromNode
มีอยู่
คืออุตสาหกรรมดนตรีที่กำลังเติบโต
เนื่องจากในกราฟที่ไม่มีทิศทางความสัมพันธ์ที่แสดงออกมานั้นไม่จำเป็นต้องสมมาตร
โหนด ย คันธนู สามารถใช้เพื่อกำหนดไฟล์ Digraph แต่เพื่อความสะดวกในอัลกอริทึมต่อไปนี้ก 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) y (len(get_first_part(cut, G).intersect(get_second_part(cut, G))) == 0)
cut
เรียกว่า ตัด x-y ถ้า (x in get_first_part(cut, G)) y (y in get_second_part(cut, G) ) y (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
พวกเขายังเป็นจำนวนจริงที่เป็นบวก
s corp vs llc chart
สำหรับแต่ละโหนด โหนด 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
มี กระแสที่เป็นไปได้ ใช่:
แต่ละ โหนด n
ใน G.setOfNodes
ยกเว้น โหนดต้นทาง ย โหนดเทอร์มินัล : n.datum.flowIn = n.datum.flowOut
.
แต่ละ ส่วนโค้ง a
ใน G.setOfNodes
: a.datum.capacity <= a.datum.flow
.
เงื่อนไขที่ 1 เรียกว่า การกักกันการอนุรักษ์ .
เงื่อนไขที่ 2 เรียกว่า การกักเก็บความจุ .
ความสามารถในการตัด ของก ตัด 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
ใช่:
-
strip_flows(maxFlowProblem.G) == strip_flows(H)
.
-
H
คือ เครือข่ายการไหล และมี กระแสที่เป็นไปได้ .
ถ้านอกเหนือจาก 1 และ 2:
- ไม่มีใครอื่นได้ เครือข่ายการไหล แสดงโดย Digraph
K
เป็น strip_flows(G) == strip_flows(K)
และ find_node_by_uid(t.uid,G).flowIn .
แล้ว H
มันยังเป็นทางออก เหมาะสมที่สุด สำหรับ maxFlowProblem
.
กล่าวอีกนัยหนึ่งก โซลูชันการไหลสูงสุดที่เป็นไปได้ สามารถแสดงด้วยไฟล์ Digraph , ที่:
-
มันเหมือนกับ Digraph G
ของที่เกี่ยวข้อง ปัญหาการไหลสูงสุด ยกเว้นโฟลว์ n.datum.flowIn
, n.datum.flowOut
และกระแส a.datum.flow
ใด ๆ ของ โหนด ย คันธนู พวกเขาอาจจะแตกต่างกัน
-
แสดงถึง เครือข่ายการไหล มีอะไรผิดปกติ กระแสที่เป็นไปได้ .
และสามารถแสดงถึงไฟล์ โซลูชันการไหลสูงสุดที่ดีที่สุด ถ้านอกจากนี้:
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
เป็นตัวแทนของ โซลูชันการไหลสูงสุดที่เป็นไปได้ ; ค่าข้างต้นเรียกว่า ค่าการไหล s-t ของ 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}

กระแสเฉือน
ให้ 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 คือผลรวมของโฟลว์ของพาร์ติชันที่มีไฟล์ โหนดต้นทาง สำหรับพาร์ติชันที่มีไฟล์ โหนดเทอร์มินัล ลบผลรวมของโฟลว์ของพาร์ติชันที่มี โหนดเทอร์มินัล สำหรับพาร์ติชันที่มีไฟล์ โหนดต้นทาง .
การไหลสูงสุดเฉือนต่ำสุด
อะไร 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 y 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'
-
คู่ n, u
ไม่สร้าง คันธนู ใน G_f
ถ้าไม่มี ส่วนโค้ง a
ใน G.setOfArcs
เช่น a.fromNode = n
และ a.toNode = u
.
-
คู่ n, u
สร้างไฟล์ ส่วนโค้ง a
ใน G_f.setOfArcs
ที่ไหน a
แสดงถึง ส่วนโค้ง ระบุว่าเป็น การไหลของแรงกระตุ้น จาก n
ก u
a = Arco (n, u, datum = ResidualNode (n_to_u_cap_sum - n_to_u_flow_sum))
ถ้า n_to_u_cap_sum> n_to_u_flow_sum
.
-
คู่ n, u
สร้างไฟล์ ส่วนโค้ง a
ใน G_f.setOfArcs
ที่ไหน a
แสดงถึง ส่วนโค้ง ระบุว่าเป็น ดึงกระแสส่วนโค้ง ของ n
ก u
a = Arco (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
ต้องเป็น ส่วนโค้ง 'ดัน' และต้องมี a.toNode == maxFlowProblem.terminalNode
. ก เส้นทางการเสริม ถูกกำหนดให้เป็นการสิ้นสุดในไฟล์ โหนดเทอร์มินัล ของ ปัญหาการไหลสูงสุด ซึ่งเป็นไฟล์ เส้นทางการเสริม . จากคำจำกัดความของ กราฟที่เหลือ เป็นที่ชัดเจนว่าสุดท้าย ส่วนโค้ง ใน วิธีการเพิ่มขึ้น ในนั้น กราฟที่เหลือ ต้องเป็น ส่วนโค้ง 'ดัน' เพราะไหน ๆ ส่วนโค้ง 'ดึง' 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 (get_first_part(stCut.cut, G)
) และบนพาร์ติชัน (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 (สตรีมเข้า โหนด n
เนื่องจากพาร์ติชัน t ทำโดยตรงหรือโดยอ้อมจากนั้นจะไม่ถูกนับในค่า stcut_flow
เพราะมันไปในทิศทางที่ไม่ถูกต้องตามคำจำกัดความ) สังเกตว่าโฟลว์ทั้งหมดที่เป็นส่วนหนึ่งของ stcut_flow
ที่เข้าสู่ โหนด n
ป้อนจากพาร์ติชัน s (โฟลว์ที่เข้าสู่ไฟล์ โหนด n
จากพาร์ติชัน t ไม่ได้นับโดยตรงหรือโดยอ้อมในค่า stcut_flow
เพราะคุณกำลังมุ่งหน้าไปผิดทางตามคำจำกัดความ)
นอกจากนี้กระแสทั้งหมดที่ออกไป n
ในที่สุดก็จะไหล (โดยตรงหรือโดยอ้อม) ไปที่ โหนดเทอร์มินัล (แสดงไว้ด้านบน) เมื่อเราย้ายไฟล์ โหนด n
ในพาร์ติชัน t กระแสทั้งหมดเข้า n
ต้องเพิ่มจากพาร์ติชัน s เป็นค่าใหม่ stcut_flow
; อย่างไรก็ตามกระแสทั้งหมดที่ออกไป n
จะต้องหักออกจากค่าใหม่ stcut_flow
; ส่วนของโฟลว์ที่ตรงไปยังพาร์ติชัน t จะถูกลบออกเนื่องจากโฟลว์นี้อยู่ภายในพาร์ติชันใหม่ t และไม่นับเป็น stcut_flow
ส่วนของการไหลจากตำแหน่ง n
ใน โหนด จากพาร์ติชัน s จะต้องถูกลบด้วย stcut_flow
: After n
ย้ายไปยังพาร์ติชัน t โฟลว์เหล่านี้จะถูกนำมาจากตำแหน่งพาร์ติชัน t ในพาร์ติชัน s ดังนั้นจึงไม่ควรนำมาพิจารณาใน stcut_flow
เนื่องจากโฟลว์เหล่านี้กำจัดอินพุตในพาร์ติชัน s และต้องลดลงด้วยผลรวมของ โฟลว์เหล่านี้และการไหลออกจากพาร์ติชัน s ไปยังพาร์ติชัน -t (โดยที่โฟลว์ทั้งหมดจาก st ต้องยุติ) ต้องลดลงด้วยจำนวนที่เท่ากัน ในฐานะที่เป็น โหนด n
อยู่ในสภาวะสมดุลก่อนกระบวนการการอัปเดตจะเพิ่มค่าเดียวกันให้กับค่าใหม่ stcut_flow
เมื่อลบออกให้ออกจาก โจทย์ E ล้างหลังจากอัพเกรด ความถูกต้องของไฟล์ โจทย์ E จากนั้นเราดำเนินการต่อในการเหนี่ยวนำกับขนาดของพาร์ติชัน t
นี่คือตัวอย่างบางส่วนของ เครือข่ายการไหล เพื่อช่วยให้เห็นภาพกรณีที่ชัดเจนน้อยกว่าที่ไฟล์ ข้อเสนอ E มันช่วย; ในภาพพื้นที่สีแดงระบุพาร์ติชัน s พื้นที่สีน้ำเงินแสดงถึงพาร์ติชัน t และ คันธนู สีเขียวหมายถึงก ตัด s-t **. ในภาพที่สองการไหลระหว่าง ** โหนด ถึงและ โหนด B เพิ่มขึ้นในขณะที่ไหลเข้า โหนดเทอร์มินัล t ไม่เปลี่ยนแปลง


Corollary: ไม่มีค่าของ กระแสเฉือน s-t อาจเกินความจุของ ตัด s-t .
ข้อเสนอ F. (การไหลสูงสุดและทฤษฎีบทการตัดขั้นต่ำ): ให้ f
เป็นกระแส เซนต์ . เงื่อนไข 3 ข้อต่อไปนี้เทียบเท่า:
-
มีการตัด เซนต์ ซึ่งมีความจุเท่ากับมูลค่าการไหล f
-
f
คือ การไหลสูงสุด .
-
นั่นไม่ใช่ วิธีการเพิ่มขึ้น ด้วยความเคารพ 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
. ถ้าไม่เช่นนั้นไฟล์ โหนด เชื่อมต่อโดย ส่วนโค้ง ด้วยกำลังการผลิตคงเหลือ a C_s
จะอยู่ในชุด C_s
ตั้งแต่นั้นมาจะมี ติดตามเพิ่มขึ้น จาก s
ยัง โหนด . การไหลผ่าน ตัด s-t เท่ากับความจุของ ตัด s-t (ตั้งแต่ คันธนู ของ C_s
ก C_t
มีการไหลเท่ากับความจุ) และค่าของ ไหล s-t (โดย โจทย์ E ).
คำแถลงของทฤษฎีบทนี้ การไหลสูงสุดตัดขั้นต่ำ หมายถึงข้อความข้างต้นของ กระแสในเครือข่าย .
Corollary (คุณสมบัติของปริพันธ์): เมื่อความจุเป็นจำนวนเต็มจะมีสตรีมค่าจำนวนเต็มสูงสุดและอัลกอริทึมของ Ford-Fulkerson พบ
ทดสอบ: ทุกๆ วิธีการเพิ่มขึ้น เพิ่มการไหลด้วยจำนวนเต็มบวกซึ่งเป็นค่าต่ำสุดของความจุที่ไม่ได้ใช้ในส่วนโค้ง ผลักดัน และไหลเข้าโค้ง แรงฉุด ซึ่งทั้งหมดนี้เป็นจำนวนเต็มบวกเสมอ
c corp vs s corp 2018
สิ่งนี้แสดงให้เห็นถึงคำอธิบายของวิธีการ ฟอร์ด - ฟุลเคอร์สัน จาก CLRS . วิธีการคือหาไปเรื่อย ๆ เพิ่มเส้นทาง และสมัคร augment
สุดท้าย maxFlowSolution
หาวิธีแก้ปัญหาที่ดีกว่าไม่มีอีกแล้ว เพิ่มเส้นทาง ซึ่งหมายความว่าสุดท้าย โซลูชันการไหลสูงสุด มันคือ เหมาะสมที่สุด .
จาก Ford-Fulkerson a Edmonds-Karp
คำถามที่เหลือเกี่ยวกับมติของ ปัญหาการไหลสูงสุด พวกเขาคือ:
-
ควรสร้างอย่างไร เส้นทางการเสริม เหรอ?
-
วิธีนี้จะสิ้นสุดหรือไม่ถ้าเราใช้จำนวนจริงไม่ใช่จำนวนเต็ม?
-
ใช้เวลานานแค่ไหนกว่าจะเสร็จ (ถ้ามี)?
อัลกอริทึม 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
ย คันธนู มากที่สุด NA/2
. ทดสอบ: ทุกๆ เส้นทางการเสริม มีโบว์คอ ส่วนโค้ง - ก ส่วนโค้ง ซึ่งถูกลบออกจาก กราฟที่เหลือ เพราะมันเข้ากันได้ดีกับส่วนโค้ง ผลักดัน ที่เติมเต็มความจุหรือส่วนโค้ง แรงฉุด ซึ่งกระแสจะกลายเป็น 0 แต่ละครั้ง a ส่วนโค้ง กลายเป็นคอขวด ส่วนโค้ง ความยาวใด ๆ เส้นทางการเสริม โดยควรเพิ่มขึ้นโดยปัจจัย 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)
ในขณะที่สร้างไฟล์ โซลูชันการไหลสูงสุด และใหม่ กราฟที่เหลือ ทุกครั้ง (แทนที่จะแก้ไขไฟล์ digraphs ที่มีอยู่ เมื่ออัลกอริทึมดำเนินไป) เพื่อมาถึงแนวทางแก้ไข O(NA^2)
จริงอัลกอริทึมต้องเก็บทั้ง digrafo สิ่งที่แสดงถึง สถานะปัญหาการไหลสูงสุด และกราฟคงเหลือ ** ที่เกี่ยวข้อง . ดังนั้นอัลกอริทึมควรหลีกเลี่ยงการทำซ้ำ ** arcs โดยไม่จำเป็น ย โหนด และอัปเดตค่าและค่าที่เกี่ยวข้องในไฟล์ กราฟที่เหลือ เมื่อจำเป็นเท่านั้น
ในการเขียนอัลกอริทึม เอดมันด์คาร์ป เร็วขึ้นฉันเขียนข้อมูลโค้ดหลายรายการจากด้านบน ฉันหวังว่าจะอ่านรหัสที่สร้างไฟล์ digrafo การทำความเข้าใจสิ่งที่เกิดขึ้นเป็นประโยชน์ ในอัลกอริทึมที่รวดเร็วฉันใช้เทคนิค 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
นี่คือการแสดงให้เห็นว่าอัลกอริทึมนี้แก้ปัญหาตัวอย่างอย่างไร เครือข่ายการไหล จากข้างบน. การแสดงภาพแสดงขั้นตอนที่สะท้อนในไฟล์ digrafo G
เป็นตัวแทนของเครือข่ายการไหล ล่าสุด และสะท้อนให้เห็นอย่างไรในไฟล์ กราฟที่เหลือ ของเครือข่ายโฟลว์นั้น วิธีการเพิ่มขึ้น ที่ กราฟที่เหลือ จะแสดงเป็นเส้นทางสีแดงและ digrafo ซึ่งแสดงถึงปัญหาชุดของ โหนด ย คันธนู ได้รับผลกระทบจากการตาย เส้นทางเสริม จะเน้นด้วยสีเขียว ในแต่ละกรณีฉันจะเน้นส่วนของแผนภูมิที่จะเปลี่ยน (สีแดงหรือสีเขียว) จากนั้นจึงแสดงแผนภูมิหลังการเปลี่ยนแปลง (สีดำเท่านั้น)


นี่คือการแสดงภาพอีกครั้งว่าอัลกอริทึมนี้แก้ตัวอย่างที่แตกต่างกันอย่างไร เครือข่ายการไหล . สังเกตว่าสิ่งนี้ใช้จำนวนจริงและมีหลายตัว คันธนู ด้วยค่าเดียวกัน fromNode
และ toNode
.
โปรดทราบว่าเนื่องจาก Arcs ที่มี 'pull' ResidualDatum สามารถเป็นส่วนหนึ่งของ Rising Path ได้โหนดที่ได้รับผลกระทบใน Flow Network Diagram_can จะไม่อยู่บนเส้นทาง G!
กราฟิกสองฝ่าย
สมมติว่าเรามีไฟล์ digrafo 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
มันคือ bipartition ถ้าแบ่งออกเป็นสองชุดได้ โหนด ในลักษณะที่แต่ละ ส่วนโค้ง ต้องเชื่อมต่อไฟล์ โหนด ในชุดเป็นโหนด ในชุดอื่น ๆ
การทดสอบ Bipartite
สมมติว่าเรามีไฟล์ digrafo G
เราต้องการทดสอบว่าเป็น bipartition . เราสามารถทำได้ใน O(|G.setOfNodes|+|G.setOfArcs|)
ด้วยสีโลภของแผนภูมิสองสี
ขั้นแรกเราต้องสร้างไฟล์ digrafo 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)
การจับคู่และการจับคู่สูงสุด
สมมติว่าเรามีไฟล์ digrafo G
และ matching
เป็นส่วนย่อยของ คันธนู ของ G.setOfArcs
. matching
คือ การจับคู่ ใช่สำหรับสองคน digrafo 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
.
การรวมกันแบบ Bi-Partitioned สูงสุด
ก ชุดค่าผสมสองพาร์ติชันสูงสุด คือ ชุดค่าผสมสูงสุด ใน digrafo G
มันคืออะไร แบ่งสองพาร์ติชัน .
ตั้งแต่ G
มันคือ แบ่งสองพาร์ติชัน ปัญหาในการค้นหาไฟล์ ชุดค่าผสมสูงสุดสองฝ่าย สามารถเปลี่ยนเป็นไฟล์ ปัญหาการไหลสูงสุด แก้ไขได้ด้วยอัลกอริทึม โดย Edmonds-Karp แล้วก็ การมีเพศสัมพันธ์แบบสองฝ่ายสูงสุด สามารถกู้คืนจากการแก้ปัญหาเป็น ปัญหาการไหลสูงสุด .
ให้ bipartition
เป็น bipartition ของ G
.
สำหรับสิ่งนี้ฉันต้องสร้างไฟล์ digrafo (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 en cubierta) o (a.toNode en cubierta)
.
ฝาปิดโหนดขั้นต่ำคือชุดที่เล็กที่สุดของ โหนด ในกราฟที่ยังคงเป็น ฝาครอบโหนด . ทฤษฎีบทของเคอนิกระบุว่าบนกราฟ แบ่งสองพาร์ติชัน ขนาดของไฟล์ การจับคู่สูงสุด ในกราฟนั้นจะเท่ากับขนาดของไฟล์ ฝาครอบโหนดขั้นต่ำ และแนะนำวิธีการกู้คืนฝาครอบโหนดจากไฟล์ การจับคู่สูงสุด :
สมมติว่าเรามีไฟล์ bipartition bipartition
และ การจับคู่สูงสุด matching
. กำหนดไฟล์ digrafo H
, H.setOfNodes=G.setOfNodes
, คันธนู ใน H.setOfArcs
พวกมันคือการรวมกันของสองชุด
ชุดแรกของ คันธนู a
ใน matching
โดยมีการเปลี่ยนแปลงว่าถ้า a.fromNode in bipartition.firstPart
และ a.toNode en bipartition.secondPart
แล้ว a.fromNode
และ a.toNode
มีการแลกเปลี่ยนในรูปแบบ สร้าง acro พวกเขาให้เช่นนั้น คันธนู แอตทริบิวต์ a.datum.inMatching = True
เพื่อระบุว่าได้มาจาก คันธนู ใน เหตุบังเอิญ .
ชุดที่สองคือ คันธนู a
ไม่อยู่ใน matching
โดยมีการเปลี่ยนแปลงถ้า a.fromNode en bipartition.secondPart
และ a.toNode en 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 para a en H.setOfArcs si ((a.datum.inMatching) y (a.fromNode.datum.visited))}
และโหนด {a.fromNode para a en H.setOfArcs si (a.datum.inMatching) y (no a.toNode.datum.visited)}
.
สิ่งนี้สามารถแสดงให้เห็นว่าขับจากไฟล์ การจับคู่สูงสุด ถึงก ฝาครอบโหนดขั้นต่ำ โดยก พิสูจน์โดยความขัดแย้ง ใช้เวลา ส่วนโค้ง a
ซึ่งคาดคะเนไม่ครอบคลุมและพิจารณาทั้งสี่กรณีว่า a.fromNode
และ a.toNode
เป็นของ (ไม่ว่าจะเป็น toNode
หรือ fromNode
) กับใด ๆ ส่วนโค้ง ใน เหตุบังเอิญ matching
. แต่ละกรณีนำไปสู่ความขัดแย้งเนื่องจากลำดับที่ DFS เข้าชม โหนด และความจริงที่ว่า matching
คือ การจับคู่สูงสุด .
สมมติว่าเรามีฟังก์ชันในการดำเนินการตามขั้นตอนเหล่านี้และส่งคืนชุดของ โหนด ที่ประกอบด้วย ฝาครอบโหนดขั้นต่ำ เมื่อเขาได้รับ digrafo 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
คือจำนวน โหนด ที่ digrafo เป็นตัวแทนของปัญหา) การใช้งานที่ง่ายต่อการอธิบายใช้เวลา O (N ^ {5})
(สำหรับเวอร์ชันที่สร้างใหม่ ดิคราฟอส ) และ O (N ^ {4})
สำหรับ (สำหรับเวอร์ชันที่เก็บไฟล์ ดิคราฟอส ). ซึ่งคล้ายกับการใช้อัลกอริทึมที่แตกต่างกันสองแบบ เอ็ดมันด์ - คาร์ป .
สำหรับคำอธิบายนี้ฉันใช้งานกับกราฟิกสองฝ่ายเต็มรูปแบบเท่านั้น (ซึ่งเป็นครึ่งหนึ่งของไฟล์ โหนด อยู่ในส่วนหนึ่งของไฟล์ bipartition และอีกครึ่งหนึ่งในส่วนที่สอง) ในคนงานแรงจูงใจในการทำงานหมายความว่ามีคนงานมากพอ ๆ กับงาน
ดูเหมือนว่าจะเป็นเงื่อนไขที่สำคัญ (จะเป็นอย่างไรหากเซตเหล่านี้ไม่เท่ากัน) แต่ปัญหานี้แก้ไขได้ง่าย ฉันพูดถึงวิธีการทำในส่วนสุดท้าย
เวอร์ชันของอัลกอริทึมที่อธิบายไว้ที่นี่ใช้แนวคิดที่เป็นประโยชน์ของ คันธนูน้ำหนักเป็นศูนย์ . น่าเสียดายที่แนวคิดนี้เหมาะสมเมื่อเราแก้ปัญหาไฟล์ การย่อขนาด (หากแทนที่จะเพิ่มประโยชน์สูงสุดของการมอบหมายงานให้กับพนักงานของเราเราจะลดค่าใช้จ่ายของงานดังกล่าวให้น้อยที่สุดแทน)
ตัวอย่างแมชชีนเลิร์นนิงใน python
โชคดีที่การแปลงไฟล์ ปัญหาการกำหนดเส้นตรงสูงสุด ใน ปัญหาการกำหนดเส้นตรงน้อยที่สุด การสร้างน้ำหนักแต่ละตัวของ ส่วนโค้ง a
ใน M-a.datum.weight
ที่ไหน M=max({a.datum.weight for a in G.setOfArcs})
. วิธีแก้ปัญหาการเพิ่มประสิทธิภาพสูงสุด ต้นฉบับจะเหมือนกับโซลูชัน ลดปัญหาให้เหลือน้อยที่สุดหลังจากเปลี่ยนน้ำหนักแล้ว ของ Arc . ส่วนที่เหลือสมมติว่าเราทำการเปลี่ยนแปลงนี้
อัลกอริทึม Kuhn-Munkres แก้ น้ำหนักน้ำหนักขั้นต่ำในแผนภูมิแบ่งสองส่วนแบบถ่วงน้ำหนัก ตามลำดับของ การแข่งขันสูงสุด ในกราฟิก ไม่ถ่วงน้ำหนัก สองฝ่าย. ถ้าเราหาเจอ คู่ที่สมบูรณ์แบบ ใน การเป็นตัวแทนของ digraph ของปัญหาการกำหนดเส้นตรงและถ้าน้ำหนักของแต่ละข้อ ส่วนโค้ง ใน เหตุบังเอิญ เป็นศูนย์ดังนั้นเราจึงพบไฟล์ น้ำหนักน้ำหนักขั้นต่ำ เนื่องจากความบังเอิญนี้ชี้ให้เห็นว่าทั้งหมด โหนด ที่ ดิคราฟอส ได้รับ จับคู่ สำหรับ ส่วนโค้ง ด้วยต้นทุนที่ต่ำที่สุดเท่าที่จะเป็นไปได้ (ไม่มีค่าใช้จ่ายใด ๆ สามารถน้อยกว่า 0 ตามคำจำกัดความก่อนหน้านี้)
ไม่มีอื่น ๆ คันธนู สามารถเพิ่มลงในไฟล์ เหตุบังเอิญ (เนื่องจากทั้งหมด โหนด จับคู่แล้ว) และไม่ คันธนู ต้องลบออกจากไฟล์ บังเอิญ เนื่องจากการทดแทนที่เป็นไปได้ ส่วนโค้ง จะมีค่าน้ำหนักมากเป็นอย่างน้อย
หากเราพบไฟล์ การจับคู่สูงสุด ของ subgrafo ของ G
ที่มีเท่านั้น คันธนูน้ำหนักเป็นศูนย์ และมันไม่ใช่ คู่ที่สมบูรณ์แบบ เราไม่มีวิธีแก้ปัญหาที่สมบูรณ์ (ตั้งแต่ การรวมกัน มันไม่ใช่ สมบูรณ์แบบ ). อย่างไรก็ตามเราสามารถผลิตไฟล์ digrafo H
การเปลี่ยนน้ำหนักของ คันธนู ใน G.setOfArcs
เพื่อให้น้ำหนัก 0 ใหม่ปรากฏขึ้น คันธนู และทางออกที่ดีที่สุดของ 'H' ก็เหมือนกับโซลูชันที่เหมาะสมที่สุดของ 'G' เนื่องจากเรารับประกันว่าอย่างน้อยหนึ่ง โบว์น้ำหนักเป็นศูนย์ เกิดขึ้นในการทำซ้ำแต่ละครั้งเรารับประกันว่าเราจะไปถึงไฟล์ คู่ที่สมบูรณ์แบบ ในเวลาไม่เกิน | G.setOfNodes | 2 = N 2 ในการทำซ้ำดังกล่าว
สมมติว่าในไฟล์ bipartition bipartition
, bipartition.firstPart
ประกอบด้วย โหนด เป็นตัวแทนของคนงานและ bipartition.secondPart
มันแสดงถึง โหนด ซึ่งในขณะเดียวกันก็แสดงถึงหลักฐาน
อัลกอริทึมเริ่มต้นด้วยการสร้างไฟล์ digrafo 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: จากนั้นสร้างไฟล์ digrafo 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 . อัลกอริทึมจะดำเนินต่อไปจนถึง ส่วนผสมที่ลงตัว . คือ การรวมกัน ยังเป็นวิธีแก้ปัญหา ปัญหาการกำหนดเชิงเส้น .
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 น้ำหนักส่วนโค้งเป็นศูนย์ เนื่องจากลำดับญาติของ คันธนู ของอะไร โหนด ไม่มีการเปลี่ยนแปลงระหว่างอัลกอริทึมและตั้งแต่ไฟล์ โบว์น้ำหนักเป็นศูนย์ มันคือธนู ถูกที่สุด และ การเติมเต็ม bipartite ที่สมบูรณ์แบบ รับรองว่ามี ส่วนโค้ง แต่ละ โหนด . ซึ่งหมายความว่าโซลูชันที่สร้างขึ้นนั้นเหมือนกับวิธีการแก้ปัญหา การทำแผนที่เชิงเส้นดั้งเดิม โดยไม่มีการปรับเปลี่ยนน้ำหนักของ ส่วนโค้ง .
การจัดสรรที่ไม่สมดุล
ดูเหมือนว่าอัลกอริทึมจะค่อนข้าง จำกัด เนื่องจากตามที่อธิบายไว้จะทำงานเฉพาะใน กราฟิกสองฝ่ายเต็มรูปแบบ (ซึ่งเป็นครึ่งหนึ่งของ โหนด อยู่ในส่วนหนึ่งของไฟล์ bipartition และอีกครึ่งหนึ่งในส่วนที่สอง) ในคนงานแรงจูงใจในการทำงานหมายความว่ามีคนงานมากพอ ๆ กับที่มีงาน (ดูเหมือนค่อนข้าง จำกัด )
อย่างไรก็ตามมีการเปลี่ยนแปลงที่ง่ายที่จะลบข้อ จำกัด นี้ สมมติว่ามีคนงานน้อยกว่างานเราเพิ่มคนงานจำลอง (เพียงพอที่จะสร้างกราฟผลลัพธ์ a กราฟิกสองฝ่ายเต็มรูปแบบ ). ผู้ปฏิบัติงานแต่ละคนมี ส่วนโค้ง ได้รับคำสั่งจากผู้ปฏิบัติงานในแต่ละงาน แต่ละคนเหล่านี้ ส่วนโค้ง มีน้ำหนัก 0 (การวางในการแข่งขันไม่ได้ให้ประโยชน์เพิ่มเติมใด ๆ ) หลังจากนี้เปลี่ยนกราฟคือ กราฟิกสองฝ่ายเต็มรูปแบบ ที่เราแก้ได้ ไม่มีการเริ่มงานที่มอบหมายให้กับผู้ปฏิบัติงานที่สมมติขึ้น
สมมติว่ามีงานมากกว่าคนงาน เราได้เพิ่มงานดัมมี่บางอย่าง (เพียงพอที่จะสร้างกราฟผลลัพธ์ a กราฟสองพาร์ติชันแบบเต็ม ). งานสมมติแต่ละงานมี ส่วนโค้ง ได้รับคำสั่งจากคนงานแต่ละคนไปยังงานที่สมมติขึ้น แต่ละคนเหล่านี้ ส่วนโค้ง มีน้ำหนักเป็น 0 (การวางไว้ในการแข่งขันไม่ได้ให้ประโยชน์เพิ่มเติมใด ๆ ) หลังจากนี้เปลี่ยนกราฟคือ กราฟสองพาร์ติชันแบบเต็ม ที่เราแก้ได้ คนงานที่ได้รับมอบหมายให้ทำภารกิจสมมติจะไม่ถูกว่าจ้างในช่วงเวลาดังกล่าว
ตัวอย่างการกำหนดเส้นตรง
ในที่สุดเราจะทำตัวอย่างกับรหัสที่ฉันใช้อยู่ ฉันจะแก้ไขตัวอย่างปัญหาจาก ที่นี่ . เรามีงาน 3 อย่าง: เราต้องการ ทำความสะอาดห้องน้ำ , กวาดพื้น , ย ล้างหน้าต่าง .
คนงานที่มีอยู่คือ อลิซ , บ๊อบ , ชาร์ลี ย ไดแอน . พนักงานแต่ละคนให้เงินเดือนที่ต้องการต่องาน นี่คือค่าจ้างต่อคนงาน:
ทำความสะอาดห้องน้ำ กวาดพื้น ล้างหน้าต่าง อลิซ $ 2 $ 3 $ 3 บ๊อบ $ 3 $ 2 $ 3 ชาร์ลี $ 3 $ 3 $ 2 ไดแอน $ 9 $ 9 $ 1
ถ้าเราอยากจ่ายเงินน้อยที่สุด แต่ยังทำงานให้ลุล่วงได้ใครควรทำงานอะไร เริ่มต้นด้วยการป้อนงานจำลองสำหรับ digraph ที่แสดงถึงปัญหาสองฝ่าย
ทำความสะอาดห้องน้ำ กวาดพื้น ล้างหน้าต่าง ไม่ทำอะไร อลิซ $ 2 $ 3 $ 3 $ 0 บ๊อบ $ 3 $ 2 $ 3 $ 0 ชาร์ลี $ 3 $ 3 $ 2 $ 0 ไดแอน $ 9 $ 9 $ 1 $ 0
สมมติว่าปัญหาถูกเข้ารหัสเป็นไฟล์ digrafo แล้ว kuhn_munkres( bipartition(G) )
จะแก้ปัญหาและส่งคืนงาน ง่ายต่อการตรวจสอบว่าการจัดสรรที่เหมาะสมที่สุด (ต้นทุนต่ำสุด) จะมีราคา $ 5
นี่คือภาพของโซลูชันที่โค้ดด้านบนสร้างขึ้น:


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