The basic algorithms for minimum co

The basic algorithms for minimum cost flow can be
divided into two classes: those that maintain feasible
solutions and strive toward optimality and those that
maintain infeasible solutions that satisfy optimality
conditions and strive toward feasibility (for details see
[1]). Algorithms from the first class are: the cyclecanceling
algorithm and the out-of-kilter algorithm. The
cycle-canceling algorithm maintains a feasible flow at
every iteration, augments flow along negative cycle in
the residual network and terminates when there is no
more negative cycle in the residual network, which
means (from Theorem 2) that the flow is a minimum
cost flow. The out-of-kilter algorithm maintains a
feasible flow at every iteration and augments flow along
shortest path in order to satisfy the optimality
conditions. Algorithms from the second class are: the
successive shortest path algorithm and primal-dual
algorithm. The successive shortest path algorithm
maintains a pseudoflow that satisfies the optimality
conditions and augments flow along shortest path from
excess nodes to deficit nodes in the residual network in
order to convert the pseudoflow into an optimal flow.
The primal-dual algorithm also maintains a pseudoflow
that satisfies the optimality conditions and solves
maximum flow problems in order to convert the
pseudoflow into an optimal flow.

ผลลัพธ์ (ไทย) 1:

อัลกอริทึมพื้นฐานสำหรับการไหลของต้นทุนที่ต่ำสามารถแบ่งออกเป็นสองประเภท: ที่รักษาไปได้แก้ปัญหา และมุ่งมั่นต่อ optimality และผู้ที่รักษา infeasible โซลูชั่นที่ตอบสนอง optimalityเงื่อนไข และมุ่งมั่นต่อความเป็นไปได้ (สำหรับดูรายละเอียด[1]) . อัลกอริทึมจากมีชั้น: cyclecanceling การอัลกอริทึมและอัลกอริทึมออกของหลุด ๆ การอัลกอริทึมการยกเลิกวงจรรักษาการไหลเป็นไปได้ที่ซ้ำทุก augments ไหลตามวงจรลบเครือข่ายเหลือ และสิ้นสุดลงเมื่อมีไม่มีเพิ่มเติมลบวงจรเครือข่ายเหลือ ซึ่งหมายถึง (จากทฤษฎีบทที่ 2) ที่ว่า การไหลเป็นต่ำสุดการไหลของต้นทุน อัลกอริทึมออกของหลุด ๆ รักษาไหลเป็นไปได้ที่ทุกคำซ้ำและ augments ไหลไปตามเส้นทางที่สั้นที่สุดเพื่อตอบสนองการ optimalityเงื่อนไข มีอัลกอริทึมจากชั้นสอง: การต่อเนื่องขั้นตอนเส้นทางที่สั้นที่สุดและสองปฐมอัลกอริทึม อัลกอริทึมเส้นทางที่สั้นที่สุดต่อเนื่องรักษา pseudoflow ที่ตอบสนองการ optimalityเงื่อนไขและ augments ไหลไปตามเส้นทางที่สั้นที่สุดจากขาดดุลโหนดในเครือข่ายเหลือในโหนส่วนเกินลำดับการแปลง pseudoflow ที่เป็นการไหลที่เหมาะสมอัลกอริทึมแบบปฐมยังรักษาความ pseudoflowที่ตอบสนองเงื่อนไข optimality และแก้ปัญหาการไหลสูงสุดเพื่อแปลงการpseudoflow เป็นการไหลที่เหมาะสม

ผลลัพธ์ (ไทย) 2:

ขั้นตอนวิธีการขั้นพื้นฐานสำหรับการไหลของค่าใช้จ่ายขั้นต่ำที่สามารถ
แบ่งออกเป็นสองชั้นเรียน: ผู้ที่รักษาความเป็นไปได้ใน
การแก้ปัญหาและมุ่งมั่นที่มีต่อความเหมาะสมและผู้ที่
รักษาโซลูชั่นที่ตอบสนองความเป็นไปไม่ได้ optimality
เงื่อนไขและมุ่งมั่นที่มีต่อความเป็นไปได้ (สำหรับรายละเอียดดู
[1]) อัลกอริทึมจากชั้นแรกคือ: cyclecanceling
ขั้นตอนวิธีการและขั้นตอนวิธีการออกจาก kilter
อัลกอริทึมวงจรยกเลิกยังคงไหลไปได้ที่
ทุกย้ำ augments ไหลไปตามวงจรเชิงลบใน
เครือข่ายที่เหลือและยุติเมื่อไม่มี
วงจรเชิงลบมากขึ้นในเครือข่ายที่เหลือซึ่ง
หมายถึง (จากทฤษฏี 2) ที่ไหลเป็นขั้นต่ำ
ค่าใช้จ่าย ไหล. ขั้นตอนวิธีการออกจาก kilter รักษา
ไหลไปได้ทุกที่ซ้ำและ augments ไหลไปตาม
เส้นทางที่สั้นที่สุดเพื่อตอบสนองความ optimality
เงื่อนไข อัลกอริทึมจากชั้นที่สองคือ:
ขั้นตอนวิธีเส้นทางที่สั้นที่สุดและปฐม-คู่ต่อเนื่อง
ขั้นตอนวิธีการ อัลกอริทึมเส้นทางที่สั้นที่สุดต่อเนื่อง
รักษา pseudoflow ที่ตอบสนองความ optimality ที่
เงื่อนไขและ augments ไหลเส้นทางพร้อมที่สั้นที่สุดจาก
โหนดเกินไปยังต่อมน้ำขาดดุลอยู่ในเครือข่ายที่เหลือใน
เพื่อแปลง pseudoflow เข้าไปในกระแสที่ดีที่สุด.
อัลกอริทึม Primal-คู่ยังรักษา pseudoflow
ว่า ตอบสนองเงื่อนไข optimality และแก้
ปัญหาการไหลสูงสุดเพื่อแปลง
pseudoflow เข้าไปในกระแสที่ดีที่สุด

ผลลัพธ์ (ไทย) 3:

ขั้นตอนวิธีพื้นฐานสำหรับการไหลของค่าใช้จ่ายขั้นต่ำ สามารถแบ่งออกเป็นสองชนชั้น ผู้รักษาเป็นไปได้โซลูชั่นและ มุ่งมั่นสู่คุณภาพ และผู้ที่รักษาที่โซลูชั่นที่ตอบสนองคุณภาพเงื่อนไขและมุ่งมั่นต่อความเป็นไปได้ ( สำหรับรายละเอียดดู[ 1 ] ) ขั้นตอนวิธีจากชั้นแรก คือ cyclecancelingขั้นตอนวิธีอัลกอริทึมและออกจาก kilter . ที่ยกเลิกวิธีการรักษาที่เป็นไปได้ของวัฏจักรทุกรูป augments , ไหลไปตามวัฏจักรในทางลบส่วนที่เหลือของเครือข่ายและสิ้นสุดลงเมื่อไม่มีวงจรเชิงลบมากขึ้นในเครือข่ายตกค้าง ซึ่งหมายความว่า ( จากทฤษฎีบท 2 ) ที่ไหลน้อยการไหลของค่าใช้จ่าย ออกของขั้นตอนวิธี kilter ยังคงเป็นเป็นไปได้ที่ทุกและการทำซ้ำ augments ไหลตามเส้นทางที่สั้นที่สุดเพื่อตอบสนองคุณภาพเงื่อนไข ขั้นตอนวิธีจากชั้น สอง คือเส้นทางสั้นที่สุดอย่างหนึ่งของขั้นตอนวิธีแบบต่อเนื่องขั้นตอนวิธี เส้นทางสั้นที่สุด แบบต่อเนื่องรักษา pseudoflow คุณภาพที่น่าพอใจเงื่อนไขและ augments ไหลตามเส้นทางที่สั้นที่สุดจากเกินดุลโหนดโหนดในเครือข่ายตกค้างในเพื่อแปลง pseudoflow ในการไหลที่เหมาะสมที่สุดขั้นตอนวิธีแบบดั้งเดิมก็ยังคง pseudoflowที่ satisfies เงื่อนไขความเหมาะที่สุดและแก้ปัญหาการไหลสูงสุดเพื่อที่จะแปลงpseudoflow ในการไหลที่เหมาะสมที่สุด