ปัญหาการแต่งงานที่มีเสถียรภาพ
ปัญหาการแต่งงานที่มีเสถียรภาพ (อังกฤษ: stable marriage problem) คือปัญหาในวิชาคณิตศาสตร์ เศรษฐศาสตร์ และวิทยาการคอมพิวเตอร์ ที่เกี่ยวข้องกับการจับคู่ที่เสถียรระหว่างสมาชิกของกลุ่มสองกลุ่มที่มีขนาดเท่าๆ กัน โดยที่สมาชิกแต่ละคนมีลำดับความต้องการคู่ของตัวเอง ความเสถียรในที่นี้หมายถึง ในผลของการจับคู่ จะต้องไม่มีสถานการณ์ที่มีสมาชิกคู่หนึ่งจากแต่ละกลุ่ม ต่างฝ่ายต่างต้องการที่จะจับคู่กันเองมากกว่าคู่ที่ได้รับในผลของการจับคู่นั้น
ปัญหานี้เรียกกันทั่วไปว่าปัญหาการแต่งงานที่มีเสถียรภาพ จากวิธีอธิบายปัญหาทางคณิตศาสตร์ที่ใช้ตัวอย่างเป็นการจับคู่แต่งงานระหว่างฝ่ายชายและฝ่ายหญิง ในบทความของเดวิด เกล และ ลอยด์ แชปลีย์
ปัญหาการจับคู่และอัลกอริทึมของเกลและแชปลีย์ ได้รับการนำมาใช้วางระบบจับคู่หลายอย่าง เช่น การรับนักเรียนในสถาบันการศึกษา การจับคู่ระหว่างนักศึกษาแพทย์กับโรงพยาบาล เป็นต้น
ที่มาของปัญหา
[แก้]ในค.ศ. 1962 เดวิด เกล และ ลอยด์ แชปลีย์ นักคณิตศาสตร์ และนักเศรษฐศาสตร์ชาวอเมริกัน ได้ทำการพิสูจน์ว่า ทุกๆ ครั้งที่มีจำนวนของฝ่ายชาย และฝ่ายหญิงเท่ากัน จะสามารถแก้ปัญหาการแต่งงานที่มีเสถียรภาพได้เสมอ โดยพวกเขาได้ทำการเสนอขั้นตอนวิธี ที่ชื่อว่า ขั้นตอนวิธีของเกล-แชปลีย์เพื่อแก้ปัญหาดังกล่าว [1]
ผลเฉลยของปัญหาที่คิดค้นโดย เดวิด เกล และ ลอยด์ แชปลีย์
[แก้]ขั้นตอนวิธีของเกล-แชพลีย์ จะใช้วงวนสำหรับการดำเนินการตามขั้นตอนวิธี โดยที่ฝ่ายชายที่ยังไม่ได้ทำ"การหมั้น"กับฝ่ายหญิง ทำการเลือกฝ่ายหญิงที่ตนหมายปองมากที่สุด และเป็นคนที่เขายังไม่ได้เลือกมาก่อน โดยที่ฝ่ายหญิงแต่ละคนนั้นทำการพิจารณาเลือกฝ่ายชายที่ทำการเลือกเธอแต่ละคน และบอกว่าผู้ใดที่เธอพึงพอใจมากที่สุด โดยการ ตอบตกลง สำหรับคนที่เธอเลือก และ ปฏิเสธ กับทุกคนที่เธอไม่ได้เลือก จากนั้นฝ่ายหญิงจะตอบรับ"การหมั้น"จากฝ่ายชายที่ตนเลือกไว้ชั่วคราว ซึ่งจะสามารถคิดเป็นขั้นตอนวิธีได้ดังนี้
ในการวนซ้ำครั้งแรกนั้น จะประกอบไปด้วยขั้นตอนดังนี้
- ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด
- ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่เธอหมายปองมากที่สุดด้วยการหมั้นชั่วคราว และ ปฏิเสธ กับฝ่ายชายคนอื่น ๆ ที่เธอไม่ได้หมายปอง
ในการวนซ้ำรอบถัด ๆ มา จะประกอบไปด้วยขั้นตอนดังนี้
- ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด ที่ยังไม่ได้เลือกมาก่อนในรอบก่อนหน้านี้ โดยไม่ต้องคำนึงถึงว่าฝ่ายหญิงจะมีคู่หมั้นอยู่แล้ว
- ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่ที่เธอหมายปองมากที่สุด และปฏิเสธคนที่เหลือ (รวมทั้งฝ่ายชายที่ตนทำการหมั้นไว้ชั่วคราวด้วย ถ้าเธอพึงพอใจฝ่ายชายที่เลือกเธอรอบนี้มากกว่าคู่หมั้นชั่วคราวของเธอ)
ขั้นตอนวิธี
[แก้]ข้อมูลนำเข้า และผลลัพธ์
[แก้]- ข้อมูลนำเข้า: เซตของผู้ชาย n คน และผู้หญิง n คน โดยที่แต่ละคนมิรายชื่อของบุคคลที่ตนหมายปอง
- ผลลัพธ์ : เซตของคู่สมรสที่มีเสถียรภาพ ระหว่างฝ่ายชายและฝ่ายหญิง
รหัสเทียม(Pseudo Code)
[แก้]การทำงาน การจับคู่ที่มีเสถียรภาพ 1: เริ่มต้นให้ ฝ่ายชายทุกคน และฝ่ายหญิงทุกคนเป็นโสด 2: ขณะที่ มีฝ่ายชายที่ยังเป็นโสด 3: เลือกฝ่ายชายที่ยังไม่ได้จับคู่เป็น M และฝ่ายหญิงคนแรกที่อยู่ในรายการของเขาเป็น W 4: ลบ W จากรายการของเขา เพื่อไม่ให้ถูกเลือกอีกเป็นครั้งที่สอง 5: ถ้า W หมั้นอยู่แล้ว ให้ทำ 6: ถ้า W หมายปอง M มากกว่าคู่หมั้นชั่วคราวของตน P ให้ทำ 7: ตั้งค่าให้ W ถอนหมั้นกับ P และ P เป็นโสด 8: ตั้งค่าให้ M หมั้นชั่วคราวกับ W 9: มิเช่นนั้น ให้ทำ 10: M ยังคงเป็นโสดเช่นเดิม เนื่องจาก W พอใจที่จะอยู่กับ P มากกว่า 11: จบการทำงานของเงื่อนไขรอง 12: มิเช่นนั้น ให้ทำ 13: ตั้งค่าให้ W หมั้นชั่วคราวกับ M 14: จบการทำงานของเงื่อนไขหลัก 15: จบการทำงานของวงวน 16: จบการทำงาน
ตัวอย่างการอธิบายขั้นตอนวิธี
[แก้]กำหนดให้รายการที่รับมาเป็นดังนี้
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
รอบที่ 1 (รอบแรก)
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
รอบที่ 2
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
รอบที่ 3
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
รอบที่ 4
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
รอบที่ 5
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
เสร็จสิ้นการเลือกคู่สมรส
จากตารางจะพบว่าไม่มีสมาชิกของฝ่ายชายและฝ่ายหญิงใด ที่ยังไม่มีคู่หมั้น จึงได้คำตอบของปัญหาการแต่งงานที่มีเสถียรภาพ ดังนี้ |
ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า
- ทุกคนจะได้ทำการสมรส เนื่องจาก ฝ่ายชายแต่ละคนจะมีรายชื่อของฝ่ายหญิงที่ตนหมายปองครบทุกคน ดังนั้นจะไม่มีฝ่ายหญิงคนใดเลยที่ไม่ถูกเลือก โดยฝ่ายชาย จึงเป็นไปไม่ได้ที่จะทั้งฝ่ายหญิงและฝ่ายชายเป็นโสดพร้อมกันในที่สุด
- การสมรสมีเสถียรภาพ เนื่องจากการที่ฝ่ายหญิงมีสิทธิ์ที่จะเลือกฝ่ายชายที่ตนเองหมายปองด้วยเช่นกัน สมมติเช่น ถ้าหากเกิดสถานการณ์ที่ฝ่ายหญิงมีคู่หมั้นชั่วคราวอยู่แล้ว แต่ว่ามีฝ่ายชายที่หมายปองตนและตนนั้นก็พึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราวของตน ฝ่ายหญิงมีสิทธิ์ที่จะถอนหมั้น และทำการหมั้นกับฝ่ายชายคนใหม่ที่ตนพึงพอใจมากกว่าได้ ดังนั้นจึงรับประกันได้ว่าฝ่ายหญิงจะได้แต่งงานกับฝ่ายชายที่ตนพึงพอใจมากที่สุด จึงทำให้การสมรสมีเสภียรภาพ
วิเคราะห์ประสิทธิภาพการทำงาน
[แก้]ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น
สมมติฐาน :
[แก้]- สมมติฐานที่ 1: ฝ่ายชายขอแต่งงานกับฝ่ายหญิงด้วยลำดับความพึงพอใจที่ลดลงจากมากไปน้อย
- สมมติฐานที่ 2: ฝ่ายหญิงที่ทำการหมั้นไปแล้วครั้งหนึ่ง จะไม่มีทางที่จะไร้คู่สมรสเพราะเธอจะไม่ถอนหมั้นก็ต่อเมื่อไม่เจอฝ่ายชายที่เลือกตนและตนพึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราว
การแก้ปัญหาแบบถึก (Brute-force) :
[แก้]- เวลาที่ใช้ในการทำงานในกรณีแย่สุดที่ใช้การตรวจสอบรายชื่อทั้งหมด เป็น (เวลาที่ใช้ในการตรวจสอบเสถียรภาพของการจับคู่) เท่ากับ Θ
การพิสูจน์ความถูกต้อง :
[แก้]1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น จากการทำงานของวงวน
- พิสูจน์: จากรายชื่อที่หมายปองทั้งหมดของฝ่ายชายมีจำนวนรูปแบบที่เป็นไปได้ รูปแบบ ดังนั้น วงวนจะทำงานเป็นจำนวนครั้งมากที่สุดเท่ากับ ครั้ง
2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน
- พิสูจน์โดยหาข้อขัดแย้ง
- สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
- จะพบ มีนางสาวเอ ไม่มีคู่เช่นกันแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
- จากสมมติฐานที่ 2 แสดงว่านางสาวเอ ไม่มีฝ่ายชายคนไหนเลยที่ปรารถนาจะแต่งงานด้วยเลย
- แต่จากปัญหานี้ ฝ่ายชายทุกคนจะทำการเลือกฝ่ายหญิงทุกคน ตามลำดับความพึงพอใจ ดังนั้น นายหนึ่ง ทำการเลือกนางสาวเอ แล้ว
- ดังนั้นจึงเป็นไปไม่ได้ที่จะมีฝ่ายชายหรือฝ่ายหญิงคนใด ไม่มีคู่
- สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ
- พิสูจน์โดยหาข้อขัดแย้ง
- สมมติให้ การจับคู่คู่หนึ่งระหว่างนายหนึ่ง กับนางสาวเอ ขาดเสถียรภาพ ในขณะที่พวกเขาเสนอรายชื่อของกันและกันในรายชื่อที่หมายปอง
- กรณีที่ 1: นายหนึ่งไม่เคยขอแต่งงานกับนางสาวเอ
- นายหนึ่งขอแต่งานกับนางสาวเอในที่สุด (จากการลดลำดับความพึงพอใจในรายชื่อที่หมายปองของฝ่ายชาย)
- การจับคู่ระหว่าง นายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
- กรณีที่ 2: นายหนึ่งขอแต่งงานกับนางสาวเอไปแล้ว
- นางสาวเอ ปฏิเสธการขอแต่งงานของนายหนึ่ง (ทั้งกรณีที่นายหนึ่งไม่ดีกว่าคู่หมั้นชั่วคราวของนาวสาวเอ และกรณีที่เลือกนายหนึ่ง ไปแล้ว แต่เจอคนที่ดีกว่าในภายหลัง)
- แสดงว่านางสาวเอก็เสนอรายชื่อของนายหนึ่ง ในรายชื่อที่หมายปองไว้แล้ว เพียงแต่ต้องการคนที่ดีกว่าเท่านั้น
- การจับคู่ระหว่างนายหนึ่ง กับ นางสาวเอ มีเสถียรภาพ
- กรณีที่ 1: นายหนึ่งไม่เคยขอแต่งงานกับนางสาวเอ
- สมมติให้ การจับคู่คู่หนึ่งระหว่างนายหนึ่ง กับนางสาวเอ ขาดเสถียรภาพ ในขณะที่พวกเขาเสนอรายชื่อของกันและกันในรายชื่อที่หมายปอง
สรุป :
[แก้]- ขั้นตอนวิธีของเกล-แชปลีย์ รับประกันว่าจะสามารถหาคู่สมรสที่มีเสถียรภาพได้เสมอ ๆ สำหรับฝ่ายชาย และฝ่ายหญิงที่มีจำนวนเท่ากัน
- เวลาและเนื้อที่ที่ใช้สำหรับขั้นตอนวิธีของเกล-แชปลีย์ เป็น Ο
ตัวอย่างการประยุกต์ใช้งาน
[แก้]มีการนำขั้นตอนวิธีของ เกล-แชปลีย์ ไปประยุกต์ใช้อย่างกว้างขวาง ยกตัวอย่างเช่น การคัดเลือกนักเรียนชั้นประถมศึกษาเพื่อเข้าศึกษาต่อในโรงเรียนระดับมัธยมศึกษาของประเทศสิงคโปร์ [2] การคัดเลือกนักเรียนชั้นมัธยมศึกษาเพื่อเข้าศึกษาต่อในมหาวิทยาลัยของประเทศอังกฤษ [3] ตัวอย่างอื่น ๆ เช่น การเลือกโรงพยาบาลที่จะฝึกงานสำหรับนักศึกษาแพทย์ การเลือกเพื่อนร่วมห้องในหอพักนิสิตนักศึกษาในมหาวิทยาลัย เป็นต้น
ปัญหาที่เกี่ยวข้อง
[แก้]- การจับคู่กราฟสองส่วน (Bipartite matching) กล่าวคือ ปัญหาการแต่งงานที่มีเสถียรภาพนี้เป็นตัวอย่างหนึ่งของการจับคู่กราฟสองส่วนโดยทั่วไปในเรื่องของทฤษฏีกราฟ
- ปัญหาการจัดตารางช่วงเวลา (Interval scheduling problem) เป็นตัวอย่างหนึ่งของขั้นตอนวิธีแบบละโมภ
- การจัดตาราช่วงเวลาแบบถ่วงน้ำหนัก (Weighted interval scheduling) ซึ่งเป็นตัวอย่างหนึ่งของปัญหาการจัดตารางช่วงเวลา โดยให้มีหอประชุมขนาดใหญ่ และมีการจัดกิจกรรมต่าง ๆ ที่จะต้องจัดตารางเวลาในการใช้หอประชุมแห่งนี้ โดยกิจกรรมต่าง ๆ นั้นมีเวลาที่เริ่มของกิจกรม และเวลาที่จบของกิจกรรมนั้น ๆ ซึ่งปัญหานี้เกี่ยวข้องกันโดยที่เราจะต้องจัดการตารางเวลาให้มีกิจกรรมจัดขึ้นมากที่สุดในช่วงเวลาที่กำหนด
- เซตอิสระ (Independent Set) โดยให้มีกราฟ G ที่มีปมเป็น V และเส้นเชื่อมเป็น E โดยเราจะสามารถบอกได้ว่า เซตของปม S จะเป็นเซตอิสระ ถ้าไม่มีสองปอมใด ๆ ที่มีเส้นเชื่อมซึ่งกันและกัน ซึ่งการหาเซตอิสระที่ใหญ่ที่สุดในกราฟ G จะเป็นส่วนหนึ่งของปัญหาเอ็นพีบริบูรณ์ (NP-Complete)
- การแข่งขันหาทำเลที่ตั้งสิ่งอำนวยความสะดวก (Competitive Facility Location) เป็นเกมที่มีผู้เล่นตั้งแต่ 2 คนขึ้นไป ทำการเดินและเลือกที่ตั้งที่ทำให้ตนมีคะแนนมากที่สุด โดยกลยุทธ์ที่จะสามารถทำให้ชนะในเกมนี้คือการเลือกจุดเริ่มต้นของที่ตั้ง และการตัดสินใจในการเลือกเดินของผู้เล่นในตาก่อนหน้านี้ ซึ่งเกมนี้เป็นตัวอย่างหนึ่งของปัญหาพีเสปซบริบูรณ์
อ้างอิง
[แก้]- ↑ Harry Mairson: "The Stable Marriage Problem", The Brandeis Review 12, 1992 (online).
- ↑ Chung-Piaw Teo,Jay Sethuraman, Wee-Peng Tan,Gale-Shapley Stable Marriage Problem Revisited: Strategic Issues and Applications, Management science, 2001 ([1]).
- ↑ D.G. McVITIEɫ̩ and L. B. WILSON, The Application of the Stable Marriage Assignment to University Admissions, Operational Research Quarterly(1970-1977), 1970 ([2]).
แหล่งข้อมูลอื่น
[แก้]- เอกสารประกอบการสอนของ SMP เก็บถาวร 2011-09-28 ที่ เวย์แบ็กแมชชีน
- โค้ดของโรเซตต้า
- การออกแบบขั้นตอนวิธี [ลิงก์เสีย]
- บทนำของปัญหาการแต่งงานที่มีเสถียรภาพ เก็บถาวร 2016-06-23 ที่ เวย์แบ็กแมชชีน
- โปรแกรมแสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพ
- โปรแกรมจำลองสถานการณ์แสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพแบบมีฝ่ายชาย 4 คน และฝ่ายหญิง 4 คน
- โปรแกรมจำลองสถานการณ์แสดงการแก้ปัญหาการแต่งงานที่มีเสถียรภาพแบบมีฝ่ายชาย 15 คน และฝ่ายหญิง 15 คน
- ปัญหาที่เกี่ยวข้องกับปัญหาการแต่งงานที่มีเสถียรภาพ