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

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

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

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

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

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

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

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

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

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

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

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

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

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

วิเคราะห์การทำงาน 
แต่ละวัฏภาคประกอบด้วยการค้นหาตามแนวกว้างหนึ่งครั้งและการค้นหาตามแนวลึกหนึ่งครั้ง ดังนั้นในวัฏภาคหนึ่งๆจะใช้เวลาเชิงเส้น เพราะฉะนั้น สำหรับ  วัฏภาคแรก ในกราฟที่มี  จุด และ เส้นเชื่อม จะใช้เวลาทั้งหมด 

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

จะได้ว่า ขั้นตอนวิธีนี้มีการทำงานอย่างมากที่สุด  วัฏภาค ดังนั้น จะได้เวลาทั้งหมดในการทำงานคือ  สำหรับกรณีแย่สุด

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

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

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

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

รหัสเทียม 
  1 /*
  2   G = G1 ∪ G2 ∪ {จุดว่าง}
  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     คืนค่า จำนวนการจับคู่

ดูเพิ่ม 
 ทฤษฎีกราฟ
 อภิธานศัพท์ทฤษฎีกราฟ
 กราฟสองส่วน
 ปัญหาการไหลมากสุด
 การค้นหาตามแนวกว้าง
 ขั้นตอนวิธีฮังกาเรียน
 ขั้นตอนวิธีของดีนิซ

อ้างอิง 

ขั้นตอนวิธีกราฟ
การจับคู่