ข นตอนว ธ ฮอปครอฟท คาร พ อ งกฤษ Hopcroft Karp algorithm เป นข นตอนว ธ ท ม ข อม ลนำเข าเป นกราฟสองส วน และม ผลล พธ เป นจำ

ขั้นตอนวิธีฮอปครอฟท์-คาร์พ (อังกฤษ: Hopcroft–Karp algorithm) เป็นขั้นตอนวิธี ที่มีข้อมูลนำเข้าเป็นกราฟสองส่วน และมีผลลัพธ์เป็นจำนวนที่มากที่สุด นั่นคือเซ็ตของเส้นเชื่อมที่มากที่สุดที่เป็นไปได้โดยที่ไม่มีเส้นเชื่อมสองเส้นที่ต่างกันใด ๆ เชื่อมไปยังจุดเดียวกัน ใช้เวลาในการทำงานเป็น $O(m{\sqrt {n}})$ ใน, โดย $O$ คือ สัญกรณ์โอใหญ่, $m$ คือ จำนวนของเส้นเชื่อมในกราฟ, และ $n$ คือจำนวนจุดในกราฟ สำหรับ ใช้เวลาในการทำงานเป็น $O(n^{\frac {5}{2}})$ และสำหรับ ใช้เวลาในการทำงานเป็นเชิงเส้น

ขั้นตอนวิธีฮอปครอฟท์-คาร์พคิดค้นโดยและ เป็นขั้นตอนวิธีสำหรับการจับคู่เช่นเดียวกับขั้นตอนวิธีฮังกาเรียนและเอ็ดมอนส์ (1993) ขั้นตอนวิธีฮอปครอฟท์-คาร์พทำโดยการเพิ่มขนาดของการจับคู่ซ้ำ ๆ โดยการหาวิถีแต่งเติม ใช้การวนซ้ำ $O({\sqrt {n}})$ รอบ โดนหลักการเดียวกันนี้ยังใช้พัฒนาขั้นตอนวิธีที่ซับซ้อนขึ้นสำหรับการจับคู่ในกราฟที่ไม่ใช่กราฟสองส่วน โดยใช้เวลาในการทำงานเหมือนกับขั้นตอนวิธีฮอปครอฟท์-คาร์พ

วิถีแต่งเติม

แนวคิดพื้นฐานของขั้นตอนวิธีนี้ขึ้นอยู่กับวิถีแต่งเติม

จุดอิสระ คือ จุดที่ไม่เชื่อมต่อกับเส้นเชื่อมใด ๆ ในการจับคู่ $M$

วิถีแต่งเติม คือ วิถีที่เริ่มต้นจากจุดอิสระไปยังจุดอิสระ โดยวิถีนี้ จะผ่านเส้นเชื่อมทั้งที่มีการจับคู่อยู่แล้วและยังไม่มีการจับคู่สลับกันไป

$n$ คือ ขนาดของการจับคู่ $M$

$P$ คือ วิถีแต่งเติมที่สัมพันธ์กับ $M$

จะได้ว่า ของเซ็ตของเส้นเชื่อม $M\oplus P$ ทำให้เกิดการจับคู่ที่มีขนาด $n+1$ ดังนั้น จะใช้วิถีแต่งเติมเพื่อขยายขนาดของการจับคู่ได้

ในทางกลับกัน สมมติว่าการจับคู่ $M$ ไม่ใช่วิธีที่ดีที่สุด ให้ผลต่างสมมาตร $P=M\oplus M^{*}$ โดย $M^{*}$ คือการจับคู่ที่ดีที่สุด จะได้ $P$ คือวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน และจำนวนวิถีใน $P$ เท่ากับความแตกต่างของขนาดของ $M$ และ $M*$ ดังนั้น จะหยุดขั้นตอนวิธีนี้และจะได้การจับคู่ $M$ ที่ดีที่สุดเมื่อไม่สามารถหาวิถีแต่งเติมได้

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

ขั้นตอนวิธี

ให้ $U$ และ $V$ เป็นเซ็ตที่แบ่งกราฟสองส่วน $G$ ออกเป็นสองส่วน และให้เซ็ต $M$ แสดงการจับคู่ใด ๆ จาก $U$ ไปยัง $V$

ขั้นตอนวิธีนี้แบ่งการทำงานเป็นวัฏภาค โดยทุกๆวัฏภาคมีขั้นตอนดังนี้

ใช้การค้นหาตามแนวกว้างแบ่งจุดในกราฟเป็นชั้น โดยเริ่มต้นค้นหาจากจุดอิสระใน $U$ และถือว่าจุดที่เริ่มค้นหาเป็นชั้นแรก ในระดับแรกของการค้นหาตามแนวกว้างจะมีการท่องไปยังเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น (นั่นคือ $U$ ไม่มีการเชื่อมต่อกับเส้นเชื่อมที่มีการจับคู่ใดๆ) และในระดับต่อๆไปของการค้นหาตามแนวกว้าง การท่องไปในเส้นเชื่อมจะต้องทำระหว่างเส้นเชื่อมที่มีการจับคู่และเส้นเชื่อมที่ไม่มีการจับคู่ นั่นคือ เมื่อการค้นหาสิ้นสุดลง จากจุดใน $U$ จะท่องไปในเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น แต่จากจุดใน $V$ จะท่องไปในเส้นเชื่อมที่มีการจับคู่แล้วเท่านั้น การค้นหาจะสิ้นสุดเมื่อพบชั้นแรกที่มีจุดอิสระใน $V$ ที่ถูกเข้าถึงแล้วอย่างน้อยหนึ่งจุด กำหนดให้เป็นชั้น $k$
นำทุกๆจุดอิสระใน $V$ ที่ระดับชั้น $k$ ใส่ไปในเซ็ต $F$ นั่นคือ จุด $v$ จะถูกใส่ใน $F$ ก็ต่อเมื่อจุดนั้นถูกพบในวิถีแต่งเติมที่สั้นที่สุดซึ่งได้มาจากการค้นหาตามแนวกว้าง
ทำการหาจำนวนวิถีแต่งเติมความยาว $k$ ที่มากที่สุดที่ไม่ติดกัน โดยจาก $F$ ไปยังจุดอิสระใน $U$ โดยการใช้ชั้นจากการค้นหาตามแนวกว้างเพื่อเป็นแนวทางการค้นหา การค้นหาตามแนวลึกจะค้นไปยังจุดที่ยังไม่เคยพบในชั้นก่อนหน้า และในต้นไม้ของค้นหาตามแนวลึก จุดเชื่อมต่อใดๆในวิถีที่ได้จะเชื่อมต่อระหว่างเส้นเชื่อมที่ถูกจับคู่แล้วและเส้นเชื่อมที่ยังไม่ได้จับคู่เท่านั้น เมื่อพบวิถีแต่งเติมที่เริ่มจากจุดใน $F$ แล้ว จะทำการค้นหาตามแนวลึกใหม่ โดยทำจากจุดเริ่มต้นถัดไปใน $F$
ทุกๆวิถีที่ได้มาจะถูกนำไปเพิ่มขนาดของ $M$

ขั้นตอนวิธีนี้จะสิ้นสุดเมื่อไม่พบวิถีแต่งเติมจากการค้นหาตามแนวกว้างในวัฏภาคใดๆ

วิเคราะห์การทำงาน

แต่ละวัฏภาคประกอบด้วยการค้นหาตามแนวกว้างหนึ่งครั้งและการค้นหาตามแนวลึกหนึ่งครั้ง ดังนั้นในวัฏภาคหนึ่งๆจะใช้เวลาเชิงเส้น เพราะฉะนั้น สำหรับ ${\sqrt {n}}$ วัฏภาคแรก ในกราฟที่มี $n$ จุด และ $m$ เส้นเชื่อม จะใช้เวลาทั้งหมด $O(m{\sqrt {n}})$

โดยแสดงได้ว่า ในทุกๆวัฏภาค ความยาวของวิถีแต่งเติมที่สั้นที่สุดจะมีการเพิ่มความยาวขึ้นเสมอ นั่นคือ ในแต่ละวัฏภาค วิถีแต่งเติมอื่นๆที่เหลืออยู่ต้องมีความยาวมากกว่าความยาวปัจจุบันเสมอ เพราะฉะนั้นเมื่อ ${\sqrt {n}}$ วัฏภาคแรกในขั้นตอนวิธีสิ้นสุดลง วิถีแต่งเติมที่สั้นที่สุดจะมีเส้นเชื่อมอย่างน้อย ${\sqrt {n}}$ เส้นเชื่อม อย่างไรก็ตามระหว่างการจับคู่ที่ดีที่สุดและการจับคู่ $M$ ที่ได้มาจากแต่ละวัฏภาค จะก่อให้เกิดวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน นั่นคือ ถ้าแต่ละวิถีในเซ็ตมีความยาวอย่างน้อยเท่ากับ ${\sqrt {n}}$ แล้ว จะมีวิถีได้อย่างมากที่สุดจำนวน ${\sqrt {n}}$ วิถี และขนาดของการจับคู่ที่ดีที่สุดจะมีความแตกต่างจากขนาดของ $M$ ได้อย่างมากเท่ากับ ${\sqrt {n}}$ เส้นเชื่อม และเนื่องจากว่าทุกวัฏภาคของขั้นตอนวิธีนี้จะมีการเพิ่มขนาดของการจับคู่เสมอ ดังนั้นก่อนที่ขั้นตอนวิธีจะสิ้นสุด จะมีวัฏภาคเพิ่มได้อย่างมากที่สุดอีกจำนวน ${\sqrt {n}}$ วัฏภาค

จะได้ว่า ขั้นตอนวิธีนี้มีการทำงานอย่างมากที่สุด $2{\sqrt {n}}$ วัฏภาค ดังนั้น จะได้เวลาทั้งหมดในการทำงานคือ $O(m{\sqrt {n}})$ สำหรับกรณีแย่สุด

อย่างไรก็ตาม ในหลายๆกรณี เวลาที่ใช้โดยขั้นตอนวิธีนี้อาจจะเร็วกว่าในการวิเคราะห์กรณีแย่สุด เช่น ในสำหรับสองส่วนแบบ Bast et al. (2006) ได้แสดงว่า ในการจับคู่ที่ไม่ใช่การจับคู่ที่ดีที่สุด วิถีแต่งเติมที่ได้มีโอกาสสูงที่จะมีความยาวเป็นลอการิทึม (พัตนาจากผลของ Motwani (1994)) ดังนั้น สำหรับกราฟเหล่านี้ ขั้นตอนวิธีฮอปครอฟท์-คาร์พ จะมี $O(\log(n))$ วัฏภาคและจะมีเวลาในการทำงานเท่ากับ $O(m\log(n))$

เปรียบเทียบกับขั้นตอนวิธีจับคู่กราฟสองส่วนอื่นๆ

สำหรับขั้นตอนวิธีฮอปครอฟท์-คาร์พ เป็นขั้นตอนวิธีที่มีประสิทธิภาพดีที่สุดในกรณีแย่สุด แต่สำหรับกราฟซับซ้อนขั้นตอนวิธีโดย Alt et al. (1991) สามารถทำงานได้ดีกว่าเล็กน้อย คือ $O(n^{1.5}({\frac {m}{\log(n)}})^{0.5})$ โดยเป็นขั้นตอนวิธีที่มีพื้นฐานจากซึ่งหลังจากการจับคู่โดยขั้นตอนวิธีนี้แล้วจะสลับมาใช้วิธีฮอปครอฟท์-คาร์พ

มีผู้ทดลองเปรียบเทียบขั้นตอนวิธีจับคู่กราฟสองส่วน ผลลัพธ์ที่ได้ปรากฏว่าขั้นตอนวิธีฮอปครอฟท์-คาร์พไม่ดีเหมือนกับในทฤษฎี เมื่อเทียบกับแผนการทางกว้างและแผนการทางลึกเพื่อหาวิถีแต่งเติม และเทคนิกดัน-ติดป้ายซ้ำ

กราฟที่ไม่ใช่กราฟสองส่วน

การหาจำนวนสมาชิกจับคู่มากสุดในกราฟที่ไม่ใช่กราฟสองส่วน สามารถใช้แนวคิดเดียวกับการหาจำนวนมากสุดของวิถีแต่งเติมที่สั้นที่สุดได้ ดังนั้นจะได้ขั้นตอนวิธีที่มี $O({\sqrt {n}})$ วัฏภาค อย่างไรก็ตาม สำหรับกราฟที่ไม่ใช่กราฟสองส่วน การหาวิถีแต่งเติมในแต่ละวัฏภาคทำได้ยากและช้ากว่า Micali & Vazirani (1980) ได้แสดงถึงขั้นตอนวิธีในแต่ละวัฏภาคโดยใช้เวลาเชิงเส้นในกราฟที่ไม่ใช่กราฟสองส่วน ซึ่งใช้เวลาเท่ากับขั้นตอนวิธีฮอปครอฟท์-คาร์พ แต่เทคนิกที่ไมคาไล-วาซิรานีใช้นั้นมีความซับซ้อนและยังไม่ได้รับการพิสูจน์อย่างสมบูรณ์ นอกจากนี้ยังมีขั้นตอนวิธีที่อื่น ๆ อีก

รหัสเทียม

 1 /* 2 G = G₁ ∪ G₂ ∪ {จุดว่าง} 3 G₁ และ G₂ คือส่วนย่อยในกราฟสองส่วน และ จุดว่าง เป็นจุดพิเศษ 4 */ 5 6 ฟังก์ชัน ค้นหาตามแนวกว้าง() 7 สำหรับทุกๆจุด v ใน G₁ 8 ถ้า คู่ของ v เท่ากับ จุดว่าง 9 กำหนด ระยะทางของ v เป็น 0 10 เพิ่ม v ลงในแถวคอย 11 ไม่เช่นนั้น 12 กำหนด ระยะทางของ v เป็น ∞ 13 กำหนด ระยะทางของ จุดว่าง เป็น ∞ 14 ในขณะที่ แถวคอยไม่ว่าง 15 กำหนด v เป็น จุดหน้าสุดของแถวคอย และนำจุดหน้าสุดของแถวคอยออกไป 16 สำหรับทุกๆจุด u ที่มีเส้นเชื่อมกับ v 17 ถ้า ระยะทางของคู่ของ u เท่ากับ ∞ 18 กำหนด ระยะทางของคู่ของ u เป็น ระยะทางของ v + 1 29 เพิ่ม คู่ของ u ลงในแถวคอย 20 คืนค่า ระยะทางของจุดว่างเท่ากับ ∞ ใช่หรือไม่ 21 22 ฟังก์ชัน ค้นหาตามแนวลึก (v) 23 ถ้า v ไม่เท่ากับ จุดว่าง 24 สำหรับทุกๆจุด u ที่มีเส้นเชื่อมกับ v 25 ถ้า ระยะทางของคู่ของ u เท่ากับ ระยะทางของ v + 1 26 ถ้า ค้นหาตามแนวลึก(คู่ของ u) เป็นจริง 27 กำหนด คู่ของ u เป็น v 28 กำหนด คู่ของ v เป็น u 39 คืนค่า จริง 30 กำหนด ระยะทางของ v เป็น ∞ 31 คืนค่า เท็จ 32 คืนค่า จริง 33 34 ฟังก์ชัน ฮอปครอฟท์-คาร์พ 35 สำหรับทุกๆจุด v ใน G 36 กำหนด คู่ของ v เป็น จุดว่าง 37 กำหนด จำนวนการจับคู่ เป็น 0 38 ในขณะที่ ค้นหาตามแนวกว้าง() เป็นจริง 49 สำหรับทุกๆจุด v ใน G₁ 40 ถ้า คู่ของ v เท่ากับ จุดว่าง 41 ถ้า ค้นหาตามแนวลึก(v) เป็นจริง 42 กำหนด จำนวนการจับคู่ เป็น จำนวนการจับคู่ + 1 44 คืนค่า จำนวนการจับคู่

ดูเพิ่ม

อ้างอิง

Hopcroft, John E;Karp, Richard M (1973), An $n{\frac {5}{2}}$ algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2 (4): หน้า 225–231.
Edmonds (1993), "Paths, Trees and Flowers", Canadian J. Math 17: หน้า 449–467.
Ahuja, Magnanti & Orlin (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall, บท 12.3, bipartite cardinality matching problem, หน้า 469–470.
Bast et al. (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems 39 (1): หน้า 3–14.
Motwani (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM 41 (6): หน้า 1329–1356.
Alt et al. (1991), "Computing a maximum cardinality matching in a bipartite graph in time $\scriptstyle {\mathcal {O}}\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$ ", Information Processing Letters 37 (4): หน้า 237–240.
Chang & McCormick (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia.
Darby-Dowman (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University. As cited by Setubal (1996).
Setubal (1993), "New experimental results for bipartite matching", Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, หน้า 211–216.
Setubal (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas.
Micali & Vazirani (1980), An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, หน้า 17–27.
Blum (2001), A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs, Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn.

[1] Hopcroft, John E;Karp, Richard M (1973), An $n{\frac {5}{2}}$ algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing 2 (4): หน้า 225–231.

[2] Edmonds (1993), "Paths, Trees and Flowers", Canadian J. Math 17: หน้า 449–467.

[3] Ahuja, Magnanti & Orlin (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall, บท 12.3, bipartite cardinality matching problem, หน้า 469–470.

[4] Bast et al. (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems 39 (1): หน้า 3–14.

[5] Motwani (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM 41 (6): หน้า 1329–1356.

[6] Alt et al. (1991), "Computing a maximum cardinality matching in a bipartite graph in time $\scriptstyle {\mathcal {O}}\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$ ", Information Processing Letters 37 (4): หน้า 237–240.

[7] Chang & McCormick (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia.

[8] Darby-Dowman (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University. As cited by Setubal (1996).

[9] Setubal (1993), "New experimental results for bipartite matching", Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, หน้า 211–216.

[10] Setubal (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas.

[11] Micali & Vazirani (1980), An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, หน้า 17–27.

[12] Blum (2001), A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs, Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn.