ขั้นตอนวิธีฮอปครอฟท์-คาร์พ

ขั้นตอนวิธีฮอปครอฟท์-คาร์พ  เป็นขั้นตอนวิธี ที่มีข้อมูลนำเข้าเป็นกราฟสองส่วน และมีผลลัพธ์เป็นจำนวนการจับคู่ที่มากที่สุด นั่นคือเซ็ตของเส้นเชื่อมที่มากที่สุดที่เป็นไปได้โดยที่ไม่มีเส้นเชื่อมสองเส้นที่ต่างกันใด ๆ เชื่อมไปยังจุดเดียวกัน ใช้เวลาในการทำงานเป็น <math>O(m\sqrt n)</math> ในกรณีแย่สุด, โดย <math>O</math> คือ สัญกรณ์โอใหญ่, <math>m</math> คือ จำนวนของเส้นเชื่อมในกราฟ, และ <math>n</math> คือจำนวนจุดในกราฟ สำหรับกราฟซับซ้อน ใช้เวลาในการทำงานเป็น <math>O(n^{\frac{5}{2}})</math> และสำหรับกราฟแบบสุ่ม ใช้เวลาในการทำงานเป็นเชิงเส้น
ขั้นตอนวิธีฮอปครอฟท์-คาร์พคิดค้นโดยจอห์น ฮอปครอฟท์และริชาร์ด คาร์พ เป็นขั้นตอนวิธีสำหรับการจับคู่เช่นเดียวกับขั้นตอนวิธีฮังกาเรียนและ#เปลี่ยนทาง ขั้นตอนวิธีฮอปครอฟท์-คาร์พทำโดยการเพิ่มขนาดของการจับคู่ซ้ำ ๆ โดยการหาวิถีแต่งเติม ใช้การวนซ้ำ <math>O(\sqrt n)</math> รอบ โดนหลักการเดียวกันนี้ยังใช้พัฒนาขั้นตอนวิธีที่ซับซ้อนขึ้นสำหรับการจับคู่ในกราฟที่ไม่ใช่กราฟสองส่วน โดยใช้เวลาในการทำงานเหมือนกับขั้นตอนวิธีฮอปครอฟท์-คาร์พ
วิถีแต่งเติม.
แนวคิดพื้นฐานของขั้นตอนวิธีนี้ขึ้นอยู่กับ"วิถีแต่งเติม"
"จุดอิสระ" คือ จุดที่ไม่เชื่อมต่อกับเส้นเชื่อมใด ๆ ในการจับคู่ <math>M</math>
"วิถีแต่งเติม" คือ วิถีที่เริ่มต้นจากจุดอิสระไปยังจุดอิสระ โดยวิถีนี้ จะผ่านเส้นเชื่อมทั้งที่มีการจับคู่อยู่แล้วและยังไม่มีการจับคู่สลับกันไป
<math>n</math> คือ ขนาดของการจับคู่ <math>M</math>
<math>P</math> คือ วิถีแต่งเติมที่สัมพันธ์กับ <math>M</math>
จะได้ว่า ผลต่างสมมาตรของเซ็ตของเส้นเชื่อม <math>M \oplus P</math> ทำให้เกิดการจับคู่ที่มีขนาด <math>n+1</math> ดังนั้น จะใช้วิถีแต่งเติมเพื่อขยายขนาดของการจับคู่ได้
ในทางกลับกัน สมมติว่าการจับคู่ <math>M</math> ไม่ใช่วิธีที่ดีที่สุด ให้ผลต่างสมมาตร <math>P = M \oplus M^*</math> โดย <math>M^*</math> คือการจับคู่ที่ดีที่สุด จะได้ <math>P</math> คือวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน และจำนวนวิถีใน <math>P</math> เท่ากับความแตกต่างของขนาดของ <math>M</math> และ <math>M*</math> ดังนั้น จะหยุดขั้นตอนวิธีนี้และจะได้การจับคู่ <math>M</math> ที่ดีที่สุดเมื่อไม่สามารถหาวิถีแต่งเติมได้
วิถีแต่งเติมในปัญหาการจับคู่ มีลักษณะคล้ายกับวิถีแต่งเติมในปัญหาการไหลมากสุด นั่นคือวิถีแต่งเติมจะเพิ่มขนาดของการไหล โดยสามารถเปลี่ยนแปลงปัญหาการจับคู่กราฟสองส่วนเป็นปัญหาการไหลมากสุดได้ เช่น การเปลี่ยนวิถีทดแทนในปัญหาการจับคู่เป็นวิถีแต่งเติมในปัญหาการไหล การนำเทคนิคที่ใช้ในขั้นตอนวิธีฮอปครอฟท์-คาร์พ ไปใช้ในข่ายงานการไหล รู้จักกันในชื่อขั้นตอนวิธีของดีนิซ
ขั้นตอนวิธี.
ให้ <math>U</math> และ <math>V</math>เป็นเซ็ตที่แบ่งกราฟสองส่วน <math>G</math> ออกเป็นสองส่วน และให้เซ็ต <math>M</math> แสดงการจับคู่ใด ๆ จาก <math>U</math> ไปยัง <math>V</math>
ขั้นตอนวิธีนี้แบ่งการทำงานเป็นวัฏภาค โดยทุกๆวัฏภาคมีขั้นตอนดังนี้
ขั้นตอนวิธีนี้จะสิ้นสุดเมื่อไม่พบวิถีแต่งเติมจากการค้นหาตามแนวกว้างในวัฏภาคใดๆ
วิเคราะห์การทำงาน.
แต่ละวัฏภาคประกอบด้วยการค้นหาตามแนวกว้างหนึ่งครั้งและการค้นหาตามแนวลึกหนึ่งครั้ง ดังนั้นในวัฏภาคหนึ่งๆจะใช้เวลาเชิงเส้น เพราะฉะนั้น สำหรับ <math>\sqrt n</math> วัฏภาคแรก ในกราฟที่มี <math>n</math> จุด และ<math>m</math> เส้นเชื่อม จะใช้เวลาทั้งหมด <math>O(m \sqrt n)</math>
โดยแสดงได้ว่า ในทุกๆวัฏภาค ความยาวของวิถีแต่งเติมที่สั้นที่สุดจะมีการเพิ่มความยาวขึ้นเสมอ นั่นคือ ในแต่ละวัฏภาค วิถีแต่งเติมอื่นๆที่เหลืออยู่ต้องมีความยาวมากกว่าความยาวปัจจุบันเสมอ เพราะฉะนั้นเมื่อ <math>\sqrt n</math> วัฏภาคแรกในขั้นตอนวิธีสิ้นสุดลง วิถีแต่งเติมที่สั้นที่สุดจะมีเส้นเชื่อมอย่างน้อย <math>\sqrt n</math> เส้นเชื่อม อย่างไรก็ตามผลต่างสมมาตรระหว่างการจับคู่ที่ดีที่สุดและการจับคู่ <math>M</math> ที่ได้มาจากแต่ละวัฏภาค จะก่อให้เกิดวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน นั่นคือ ถ้าแต่ละวิถีในเซ็ตมีความยาวอย่างน้อยเท่ากับ <math>\sqrt n</math> แล้ว จะมีวิถีได้อย่างมากที่สุดจำนวน <math>\sqrt n</math> วิถี และขนาดของการจับคู่ที่ดีที่สุดจะมีความแตกต่างจากขนาดของ <math>M</math> ได้อย่างมากเท่ากับ <math>\sqrt n</math> เส้นเชื่อม และเนื่องจากว่าทุกวัฏภาคของขั้นตอนวิธีนี้จะมีการเพิ่มขนาดของการจับคู่เสมอ ดังนั้นก่อนที่ขั้นตอนวิธีจะสิ้นสุด จะมีวัฏภาคเพิ่มได้อย่างมากที่สุดอีกจำนวน <math>\sqrt n</math> วัฏภาค
จะได้ว่า ขั้นตอนวิธีนี้มีการทำงานอย่างมากที่สุด <math>2\sqrt n</math> วัฏภาค ดังนั้น จะได้เวลาทั้งหมดในการทำงานคือ <math>O(m\sqrt n)</math> สำหรับกรณีแย่สุด
อย่างไรก็ตาม ในหลายๆกรณี เวลาที่ใช้โดยขั้นตอนวิธีนี้อาจจะเร็วกว่าในการวิเคราะห์กรณีแย่สุด เช่น ในกรณีเฉลี่ยสำหรับกราฟกระจายสองส่วนแบบกราฟสุ่ม #เปลี่ยนทาง ได้แสดงว่า ในการจับคู่ที่ไม่ใช่การจับคู่ที่ดีที่สุด วิถีแต่งเติมที่ได้มีโอกาสสูงที่จะมีความยาวเป็นลอการิทึม (พัตนาจากผลของ #เปลี่ยนทาง) ดังนั้น สำหรับกราฟเหล่านี้ ขั้นตอนวิธีฮอปครอฟท์-คาร์พ จะมี <math>O(\log(n))</math> วัฏภาคและจะมีเวลาในการทำงานเท่ากับ <math>O(m\log(n))</math>
เปรียบเทียบกับขั้นตอนวิธีจับคู่กราฟสองส่วนอื่นๆ.
สำหรับกราฟกระจายขั้นตอนวิธีฮอปครอฟท์-คาร์พ เป็นขั้นตอนวิธีที่มีประสิทธิภาพดีที่สุดในกรณีแย่สุด แต่สำหรับกราฟซับซ้อนขั้นตอนวิธีโดย #เปลี่ยนทาง สามารถทำงานได้ดีกว่าเล็กน้อย คือ <math>O(n^{1.5}(\frac{m}{\log(n)})^{0.5})</math> โดยเป็นขั้นตอนวิธีที่มีพื้นฐานจากขั้นตอนวิธีการไหลมากสุดดัน-ติดป้ายซ้ำซึ่งหลังจากการจับคู่โดยขั้นตอนวิธีนี้แล้วจะสลับมาใช้วิธีฮอปครอฟท์-คาร์พ
มีผู้ทดลองเปรียบเทียบขั้นตอนวิธีจับคู่กราฟสองส่วน ผลลัพธ์ที่ได้ปรากฏว่าขั้นตอนวิธีฮอปครอฟท์-คาร์พไม่ดีเหมือนกับในทฤษฎี เมื่อเทียบกับแผนการทางกว้างและแผนการทางลึกเพื่อหาวิถีแต่งเติม และเทคนิกดัน-ติดป้ายซ้ำ
กราฟที่ไม่ใช่กราฟสองส่วน.
การหาจำนวนสมาชิกจับคู่มากสุดในกราฟที่ไม่ใช่กราฟสองส่วน สามารถใช้แนวคิดเดียวกับการหาจำนวนมากสุดของวิถีแต่งเติมที่สั้นที่สุดได้ ดังนั้นจะได้ขั้นตอนวิธีที่มี <math>O(\sqrt n)</math> วัฏภาค อย่างไรก็ตาม สำหรับกราฟที่ไม่ใช่กราฟสองส่วน การหาวิถีแต่งเติมในแต่ละวัฏภาคทำได้ยากและช้ากว่า #เปลี่ยนทาง ได้แสดงถึงขั้นตอนวิธีในแต่ละวัฏภาคโดยใช้เวลาเชิงเส้นในกราฟที่ไม่ใช่กราฟสองส่วน ซึ่งใช้เวลาเท่ากับขั้นตอนวิธีฮอปครอฟท์-คาร์พ แต่เทคนิกที่ไมคาไล-วาซิรานีใช้นั้นมีความซับซ้อนและยังไม่ได้รับการพิสูจน์อย่างสมบูรณ์ นอกจากนี้ยังมีขั้นตอนวิธีที่อื่น ๆ อีก 
รหัสเทียม.
 1 /*
 3 G1 และ G2 คือส่วนย่อยในกราฟสองส่วน และ "จุดว่าง" เป็นจุดพิเศษ
 4 */
 5
 6 ฟังก์ชัน ค้นหาตามแนวกว้าง
 7 สำหรับทุกๆจุด "v" ใน G1
 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" ใน G1
 40 ถ้า "คู่ของ v" เท่ากับ "จุดว่าง"
 41 ถ้า ค้นหาตามแนวลึก("v") เป็นจริง
 42 กำหนด "จำนวนการจับคู่" เป็น "จำนวนการจับคู่ + 1"
 44 คืนค่า จำนวนการจับคู่