ผู้ใช้:Thanabhat.jo/ขั้นตอนวิธีฮอปครอฟท์-คาร์พ
ขั้นตอนวิธีฮอปครอฟท์-คาร์พ เป็นขั้นตอนวิธี ที่มีข้อมูลนำเข้าเป็นกราฟสองส่วน และมีผลลัพธ์เป็นจำนวนการจับคู่ที่มากที่สุด นั่นคือเซ็ตของเส้นเชื่อมที่มากที่สุดที่เป็นไปได้โดยที่ไม่มีเส้นเชื่อมสองเส้นที่ต่างกันใดๆ เชื่อมไปยังจุดเดียวกัน ใช้เวลาในการทำงานเป็น O(m√n) ในกรณีแย่สุด, โดย "O" คือ สัญกรณ์โอใหญ่, m คือ จำนวนของเส้นเชื่อมในกราฟ, และ n คือจำนวนจุดในกราฟ สำหรับกราฟซับซ้อน ใช้เวลาในการทำงานเป็น O(n5/2) และสำหรับกราฟแบบสุ่ม ใช้เวลาในการทำงานเป็นเชิงเส้น
ขั้นตอนวิธีฮอปครอฟท์-คาร์พคิดค้นโดยจอห์น ฮอปครอฟท์และริชาร์ด คาร์พ เป็นขั้นตอนวิธีสำหรับการจับคู่เช่นเดียวกับขั้นตอนวิธีฮังกาเรียนและขั้นตอนวิธีของเอดมันด์ ขั้นตอนวิธีฮอปครอฟท์-คาร์พทำโดยการเพิ่มขนาดของการจับคู่ซ้ำๆโดยการหาวิถีแต่งเติม ใช้การวนซ้ำ O(√n) รอบ โดนหลักการเดียวกันนี้ยังใช้พัฒนาขั้นตอนวิธีที่ซับซ้อนขึ้นสำหรับการจับคู่ในกราฟที่ไม่ใช่กราฟสองส่วน โดยใช้เวลาในการทำงานเหมือนกับขั้นตอนวิธีฮอปครอฟท์-คาร์พ
วิถีแต่งเติม[แก้]
แนวคิดพื้นฐานของขั้นตอนวิธีนี้ขึ้นอยู่กับวิถีแต่งเติม
จุดอิสระ คือ จุดที่ไม่เชื่อมต่อกับเส้นเชื่อมใดๆ ในการจับคู่ M
วิถีแต่งเติม คือ วิถีที่เริ่มต้นจากจุดอิสระไปยังจุดอิสระ โดยวิถีนี้ จะผ่านเส้นเชื่อมทั้งที่มีการจับคู่อยู่แล้วและยังไม่มีการจับคู่สลับกันไป
n คือ ขนาดของการจับคู่ M
P คือ วิถีแต่งเติมที่สัมพันธ์กับ M
จะได้ว่า ผลต่างสมมาตรของเซ็ตของเส้นเชื่อม M ⊕ P ทำให้เกิดการจับคู่ที่มีขนาด n + 1 ดังนั้น จะใช้วิถีแต่งเติมเพื่อขยายขนาดของการจับคู่ได้
ในทางกลับกัน สมมติว่าการจับคู่ M ไม่ใช่วิธีที่ดีที่สุด ให้ผลต่างสมมาตร P = M ⊕ M* โดย M* คือการจับคู่ที่ดีที่สุด จะได้ P คือวิถีแต่งเติมหลายๆวิถีที่ไม่ต่อเนื่องกัน และจำนวนวิถีใน P เท่ากับความแตกต่างของขนาดของ M และ M* ดังนั้น จะหยุดขั้นตอนวิธีนี้และจะได้การจับคู่ M ที่ดีที่สุดเมื่อไม่สามารถหาวิถีแต่งเติมได้
วิถีแต่งเติมในปัญหาการจับคู่ มีลักษณะคล้ายกับวิถีแต่งเติมในปัญหาการไหลมากสุด นั่นคือวิถีแต่งเติมจะเพิ่มขนาดของการไหล โดยสามารถเปลี่ยนแปลงปัญหาการจับคู่กราฟสองส่วนเป็นปัญหาการไหลมากสุดได้ เช่น การเปลี่ยวิถีทดแทนในปัญหาการจับคู่เป็นวิถีแต่งเติมในปัญหาการไหล[1] การนำเทคนิคที่ใช้ในขั้นตอนวิธีฮอปครอฟท์-คาร์พ ไปใช้ในข่ายงานการไหล รู้จักกันในชื่อขั้นตอนวิธีของดีนิซ
ขั้นตอนวิธี[แก้]
ให้ U และ V เป็นเซ็ตที่แบ่งกราฟสองส่วน G ออกเป็นสองส่วน และให้เซ็ต M แสดงการจับคู่ใดๆจาก U ไปยัง V
ขั้นตอนวิธีนี้แบ่งการทำงานเป็นวัฏภาค โดยทุกๆวัฏภาคมีขั้นตอนดังนี้
- ใช้การค้นหาตามแนวกว้างแบ่งจุดในกราฟเป็นชั้น โดยเริ่มต้นค้นหาจากจุดอิสระใน U และถือว่าจุดที่เริ่มค้นหาเป็นชั้นแรก ในระดับแรกของการค้นหาตามแนวกว้างจะมีการท่องไปยังเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น (นั่นคือ U ไม่มีการเชื่อมต่อกับเส้นเชื่อมที่มีการจับคู่ใดๆ) และในระดับต่อๆไปของการค้นหาตามแนวกว้าง การท่องไปในเส้นเชื่อมจะต้องทำระหว่างเส้นเชื่อมที่มีการจับคู่และเส้นเชื่อมที่ไม่มีการจับคู่ นั่นคือ เมื่อการค้นหาสิ้นสุดลง จากจุดใน U จะท่องไปในเส้นเชื่อมที่ไม่มีการจับคู่เท่านั้น แต่จากจุดใน V จะท่องไปในเส้นเชื่อมที่มีการจับคู่แล้วเท่านั้น การค้นหาจะสิ้นสุดเมื่อพบชั้นแรกที่มีจุดอิสระใน V ที่ถูกเข้าถึงแล้วอย่างน้อยหนึ่งจุด กำหนดให้เป็นชั้น k
- นำทุกๆจุดอิสระใน V ที่ระดับชั้น k ใส่ไปในเซ็ต F นั่นคือ จุด v' จะถูกใส่ใน F ก็ต่อเมื่อจุดนั้นถูกพบในวิถีแต่งเติมที่สั้นที่สุดซึ่งได้มาจากการค้นหาตามแนวกว้าง
- ทำการหาจำนวนวิถีแต่งเติมความยาว k ที่มากที่สุดที่ไม่ติดกัน โดยการค้นหาตามแนวลึกจาก F ไปยังจุดอิสระใน U โดยการใช้ชั้นจากการค้นหาตามแนวกว้างเพื่อเป็นแนวทางการค้นหา การค้นหาตามแนวลึกจะค้นไปยังจุดที่ยังไม่เคยพบในชั้นก่อนหน้า และในต้นไม้ของค้นหาตามแนวลึก จุดเชื่อมต่อใดๆในวิถีที่ได้จะเชื่อมต่อระหว่างเส้นเชื่อมที่ถูกจับคู่แล้วและเส้นเชื่อมที่ยังไม่ได้จับคู่เท่านั้น เมื่อพบวิถีแต่งเติมที่เริ่มจากจุดใน F แล้ว จะทำการค้นหาตามแนวลึกใหม่ โดยทำจากจุดเริ่มต้นถัดไปใน F
- ทุกๆวิถีที่ได้มาจะถูกนำไปเพิ่มขนาดของ M
ขั้นตอนวิธีนี้จะสิ้นสุดเมื่อไม่พบวิถีแต่งเติมจากการค้นหาตามแนวกว้างในวัฏภาคใดๆ
วิเคราะห์การทำงาน[แก้]
แต่ละวัฏภาคประกอบด้วยการค้นหาตามแนวกว้างหนึ่งครั้งและการค้นหาตามแนวลึกหนึ่งครั้ง ดังนั้นในวัฏภาคหนึ่งๆจะใช้เวลาเชิงเส้น เพราะฉะนั้น สำหรับ √n วัฏภาคแรก ในกราฟที่มี n จุด และ m เส้นเชื่อม จะใช้เวลาทั้งหมด O(m √n)
โดยแสดงได้ว่า ในทุกๆวัฏภาค ความยาวของวิถีแต่งเติมที่สั้นที่สุดจะมีการเพิ่มความยาวขึ้นเสมอ นั่นคือ ในแต่ละวัฏภาค วิถีแต่งเติมอื่นๆที่เหลืออยู่ต้องมีความยาวมากกว่าความยาวปัจจุบันเสมอ เพราะฉะนั้นเมื่อ √n วัฏภาคแรกในขั้นตอนวิธีสิ้นสุดลง วิถีแต่งเติมที่สั้นที่สุดจะมีเส้นเชื่อมอย่างน้อย √n เส้นเชื่อม อย่างไรก็ตามผลต่างสมมาตรระหว่างการจับคู่ที่ดีที่สุดและการจับคู่ M ที่ได้มาจากแต่ละวัฏภาค จะก่อให้เกิดวิถีแต่งเติมหลาายๆวิถีที่ไม่ต่อเนื่องกัน นั่นคือ ถ้าแต่ละวิถีในเซ็ตมีความยาวอย่างน้อยเท่ากับ √n แล้ว จะมีวิถีได้อย่างมากที่สุดจำนวน √n วิถี และขนาดของการจับคู่ที่ดีที่สุดจะมีความแตกต่างจากขนาดของ M ได้อย่างมากเท่ากับ √n เส้นเชื่อม และเนื่องจากว่าทุกวัฏภาคของขั้นตอนวิธีนี้จะมีการเพิ่มขนาดของการจับคู่เสมอ ดังนั้นก่อนที่ขั้นตอนวิธีจะสิ้นสุด จะมีวัฏภาคได้อย่างมากที่สุดจอีกจำนวน √n วัฏภาค
จะได้ว่า ขั้นตอนวิธีนี้มีการทำงานอย่างมากที่สุด 2√n วัฏภาค ดังนั้น จะได้เวลาทั้งหมดในการทำงานคือ O(m √n) สำหรับกรณีแย่สุด
อย่างไรก็ตาม ในหลายๆกรณี เวลาที่ใช้โดยขั้นตอนวิธีนี้อาจจะเร็วกว่าในการวิเคราะห์กรณีแย่สุด เช่น ในกรณีเฉลี่ยสำหรับกราฟกระจายสองส่วนแบบกราฟสุ่ม Bast et al. (2006) (พัตนาจากผลของ Motwani 1994 ) ได้แสดงว่า ในการจับคู่ที่ไม่ใช่การจับคู่ที่ดีที่สุด วิถีแต่งเติมที่ได้มีโอกาสสูงที่จะมีความยาวเป็นลอการิทึม ดังนั้น สำหรับกราฟเหล่านี้ ขั้นตอนวิธีฮอปครอฟท์-คาร์พ จะมี O(log n) วัฏภาคและจะมีเวลาในการทำงานเท่ากับ O(m log n)
เปรียบเทียบกับขั้นตอนวิธีจับคู่กราฟสองส่วนอื่นๆ[แก้]
สำหรับกราฟกระจายขั้นตอนวิธีฮอปครอฟท์-คาร์พ เป็นขั้นตอนวิธีที่มีประสิทธิภาพดีที่สุดในกรณีแย่สุด แต่สำหรับกราฟซับซ้อนขั้นตอนวิธีโดย Alt et al. (1991) สามารทำงานได้ดีกว่าเล็กน้อย คือ O(n1.5(m/log n)0.5) โดยเป็นขั้นตอนวิธีที่มีพื้นฐานจากขั้นตอนวิธีการไหลมากสุดดัน-ติดป้ายซ้ำซึ่งหลังจากการจับคู่โดยขั้นตอนวิธีนี้แล้วจะสลับมาใช้วิธีฮอปครอฟท์-คาร์พ
มีผู้ทดลองเปรียบเทียบขั้นตอนวิธีจับคู่กราฟสองส่วน ผลลัพธ์ที่ได้ปรากฏว่าขั้นตอนวิธีฮอปครอฟท์-คาร์พไม่ดีเหมือนกับในทฤษฎี เมื่อเทียบกับแผนการทางกว้างและแผนการทางลึกเพื่อหาวิถีแต่งเติม และเทคนิกดัน-ติดป้ายซ้ำ[2][3][4][5]
กราฟที่ไม่ใช่กราฟสองส่วน[แก้]
การหาจำนวนสมาชิกจับคู่มากสุดในกราฟที่ไม่ใช่กราฟสองส่วน สามารถใช้แนวคิดเดียวกับการหาจำนวนมากสุดของวิถีแต่งเติมที่สั้นที่สุดได้ ดังนั้นจะได้ขั้นตอนวิธีที่มี O(√n) วัฏภาค อย่างไรก็ตาม สำหรับกราฟที่ไม่ใช่กราฟสองส่วน การหาวิถีแต่งเติมในแต่ละวัฏภาคทำได้ยากและช้ากว่า Micali & Vazirani (1980) ได้แสดงถึงขั้นตอนวิธีในแต่ละวัฏภาคโดยใช้เวลาเชิงเส้นในกราฟที่ไม่ใช่กราฟสองส่วน ซึ่งใช้เวลาเท่ากับขั้นตอนวิธีฮอปครอฟท์-คาร์พ แต่เทคนิกที่ไมคาไล-วาซิรานีใช้นั้นมีความซับซ้อนและยังไม่ได้รับการพิสูจน์อย่างสมบูรณ์ นอกจากนี้ยังมีขั้นตอนวิธีที่อื่นๆอีก [6]
รหัสเทียม[แก้]
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 คืนค่า จำนวนการจับคู่
ดูเพิ่ม[แก้]
- ทฤษฎีกราฟ
- อภิธานศัพท์ทฤษฎีกราฟ
- กราฟสองส่วน
- การจับคู่
- วิถีแต่งเติม
- ปัญหาการไหลมากสุด
- การค้นหาตามแนวกว้าง
- การค้นหาตามแนวลึก
- ผลต่างสมมาตร
- ขั้นตอนวิธีฮังกาเรียน
- ขั้นตอนวิธีของเอดมันด์
- ขั้นตอนวิธีของดีนิซ
- กราฟกระจาย
- กราฟสุ่ม
อ้างอิง[แก้]
- ↑ Ahuja, Magnanti & Orlin (1993) , Network Flows: Theory, Algorithms and Applications, Prentice-Hall, บท 12.3, bipartite cardinality matching problem, หน้า 469–470.
- ↑ 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. As cited by Setubal (1996) .
- ↑ 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, pp. 211–216. As cited by Setubal (1996) .
- ↑ Setubal (1996) , Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas.
- ↑ 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.