ปัญหาการแต่งงานที่มีเสถียรภาพ (อังกฤษ : Stable Marriage Problem) คือ ปัญหาของการหาคู่สมรส ที่มีเสถียรภาพระหว่างฝ่ายชายและฝ่ายหญิง โดยการจับคู่
สมรสระหว่างฝ่ายชายและฝ่ายหญิงที่ถือว่ามีสเถียรภาพจะต้องไม่เกิดกรณีทั้ง 2 กรณีดังต่อไปนี้
มีฝ่ายชายบางคนที่พึงพอใจฝ่ายหญิงบางคน ในขณะที่ฝ่ายชายคนนั้นได้ทำการเลือกคู่สมรสของตนไปแล้ว
มีฝ่ายหญิงบางคนที่พึงพอใจฝ่ายชายบางคนมากกว่าคนที่เธอได้ทำหารเลือกเป็นคู่สมรสของตนไปแล้ว
ซึ่งหมายความว่า การจับคู่สมรสที่มีสเถียรภาพนั้นจะเกิดขึ้นเมื่อไม่มีฝ่ายชายและฝ่ายหญิงคนใดที่มีคู่สมรสอยู่แล้วไปจับคู่สมรสกับฝ่ายหญิงและฝ่ายชายอื่นตามลำดับ
ในค.ศ. 1962 เดวิด เกล และ ลอยด์ แชปลีย์ นักคณิตศาสตร์ และนักเศรษฐศาสตร์ ชาวอเมริกัน ได้ทำการพิสูจน์ว่า ทุกๆ ครั้งที่มีจำนวนของฝ่ายชาย และฝ่ายหญิงเท่ากัน จะสามารถแก้ปัญหาการแต่งงานที่มีเสถียรภาพได้เสมอ โดยพวกเขาได้ทำการเสนอขั้นตอนวิธี ที่ชื่อว่า ขั้นตอนวิธีของเกล-แชปลีย์เพื่อแก้ปัญหาดังกล่าว [1]
ผลเฉลยของปัญหาที่คิดค้นโดย เดวิด เกล และ ลอยด์ แชปลีย์
แก้
ขั้นตอนวิธีของเกล-แชพลีย์ จะใช้วงวนสำหรับการดำเนินการตามขั้นตอนวิธี โดยที่ฝ่ายชายที่ยังไม่ได้ทำ"การหมั้น"กับฝ่ายหญิง ทำการเลือกฝ่ายหญิงที่ตนหมายปองมากที่สุด และเป็นคนที่เขายังไม่ได้เลือกมาก่อน โดยที่ฝ่ายหญิงแต่ละคนนั้นทำการพิจารณาเลือกฝ่ายชายที่ทำการเลือกเธอแต่ละคน และบอกว่าผู้ใดที่เธอพึงพอใจมากที่สุด โดยการ ตอบตกลง สำหรับคนที่เธอเลือก และ ปฏิเสธ กับทุกคนที่เธอไม่ได้เลือก จากนั้นฝ่ายหญิงจะตอบรับ"การหมั้น"จากฝ่ายชายที่ตนเลือกไว้ชั่วคราว ซึ่งจะสามารถคิดเป็นขั้นตอนวิธี ได้ดังนี้
ในการวนซ้ำครั้งแรกนั้น จะประกอบไปด้วยขั้นตอนดังนี้
1. ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด
2. ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่เธอหมายปองมากที่สุดด้วยการหมั้นชั่วคราว และ ปฏิเสธ กับฝ่ายชายคนอื่น ๆ ที่เธอไม่ได้หมายปอง
ในการวนซ้ำรอบถัด ๆ มา จะประกอบไปด้วยขั้นตอนดังนี้
1. ฝ่ายชายที่ยังไม่ได้ทำการหมั้นแต่ละคนเลือกผู้หญิงที่ตนหมายปองมากที่สุด ที่ยังไม่ได้เลือกมาก่อนในรอบก่อนหน้านี้ โดยไม่ต้องคำนึงถึงว่าฝ่ายหญิงจะมีคู่หมั้นอยู่แล้ว
2. ฝ่ายหญิงแต่ะละคน ตอบตกลง กับฝ่ายชายที่เลือกเธอ และเป็นคนที่ที่เธอหมายปองมากที่สุด และปฏิเสธคนที่เหลือ (รวมทั้งฝ่ายชายที่ตนทำการหมั้นไว้ชั่วคราวด้วย ถ้าเธอพึงพอใจฝ่ายชายที่เลือกเธอรอบนี้มากกว่าคู่หมั้นชั่วคราวของเธอ)
ข้อมูลนำเข้า และผลลัพธ์
แก้
ข้อมูลนำเข้า : เซตของผู้ชาย n คน และผู้หญิง n คน โดยที่แต่ละคนมิรายชื่อของบุคคลที่ตนหมายปอง
ผลลัพธ์ : เซตของคู่สมรสที่มีเสถียรภาพ ระหว่างฝ่ายชายและฝ่ายหญิง
การทำงาน การจับคู่ที่มีเสถียรภาพ
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
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ
ดี
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ
บี
ดี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง
สี่
สอง
สาม
บี
สาม
หนี่ง
สอง
สี่
ซี
สอง
สี่
หนี่ง
สาม
ดี
หนึ่ง
สี่
สาม
สอง
รอบที่ 1 (รอบแรก)
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ (เลือก)
ซี
ดี
บี
สอง
บี (เลือก)
เอ
ดี
ซี
สาม
บี (เลือก)
ดี
ซี
เอ
สี่
ซี (เลือก)
เอ
บี
ดี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่
สอง
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง
สี่ (หมั้น)
หนี่ง
สาม
ดี
หนึ่ง
สี่
สาม
สอง
ตารางแสดงความหมายปองรอบปัจจุบัน
คำอธิบาย
เอ
หนึ่ง
---
---
---
บี
สอง
สาม
---
---
ซี
สี่
---
---
---
ดี
---
---
---
---
"หนึ่ง" ขอ "เอ" แต่งงาน และ"เอ"ก็ตอบรับ"หนึ่ง"ด้วยการหมั้นชั่วคราว
"สอง" ขอ "บี" แต่งงาน แต่ "บี"ปฏิเสธ"สอง"เนื่องจาก"สาม"ก็ขอ"บี"แต่งงานด้วยเช่นกัน และ"บี"หมายปอง"สาม" มากกว่า
"สี่"ขอ"ซี"แต่งงาน และ"ซี"ก็ตอบรับ"สี่"ด้วยการหมั้นชั่วคราว
"ดี"ยังไม่มีใครหมายปองในรอบที่ 1
รอบที่ 2
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ (เลือก)
ดี
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ
บี
ดี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่
สอง (ปฏิเสธ)
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง
สี่ (หมั้น)
หนี่ง
สาม
ดี
หนึ่ง
สี่
สาม
สอง
ตารางแสดงความหมายปองรอบปัจจุบัน
คำอธิบาย
เอ
สอง
---
---
---
บี
---
---
---
---
ซี
---
---
---
---
ดี
---
---
---
---
"สอง" เป็นบุคคลเดียวที่ยังไม่มีคู่หมั้นชั่วคราว
"สอง" ทำการเลือกคู่ในรอบที่ 2 โดยเลือก "เอ"
"เอ" ปฏิเสธการขอของ "สอง" เนื่องจากมีคู่หมั้นชั่วคราวอยู่แล้วคือ "หนึ่ง" และ"เอ"ไม่ได้หมายปอง"สอง" ไปมากกว่า "หนึ่ง"
รอบที่ 3
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ
ดี (เลือก)
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ
บี
ดี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่
สอง
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง (หมั้น)
สี่ (ถอนหมั้น)
หนี่ง
สาม
ดี
หนึ่ง
สี่
สาม
สอง
ตารางแสดงความหมายปองรอบปัจจุบัน
คำอธิบาย
เอ
---
---
---
---
บี
---
---
---
---
ซี
สอง
---
---
---
ดี
---
---
---
---
"สอง" เป็นบุคคลเดียวที่ยังไม่มีคู่หมั้นชั่วคราว
"สอง" ทำการเลือกคู่ในรอบที่ 3 โดยเลือก "ซี"
"ซี"ถอนหมั้นกับสี่ และตอบรับ"สอง"ด้วยการหมั้นชั่วคราว
"สี่" ต้องทำการเลือกคู่ใหม่
รอบที่ 4
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ
ดี
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ (เลือก)
บี
ดี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่ (ปฏิเสธ)
สอง
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง (หมั้น)
สี่
หนี่ง
สาม
ดี
หนึ่ง
สี่
สาม
สอง
ตารางแสดงความหมายปองรอบปัจจุบัน
คำอธิบาย
เอ
สี่
---
---
---
บี
---
---
---
---
ซี
---
---
---
---
ดี
---
---
---
---
"สี่" เป็นบุคคลเดียวที่ยังไม่มีคู่หมั้นชั่วคราว
"สี่" ทำการเลือกคู่ในรอบที่ 4 โดยเลือก "เอ"
"เอ" ปฏิเสธการขอของ"สี่"เนื่องจากมีคู่หมั้นชั่วคราวอยู่แล้วคือ"หนึ่ง" และเอไม่ได้หมายปอง"สี่" ไปมากกว่า "หนึ่ง"
รอบที่ 5
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ
ดี
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ
ดี
บี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่
สอง
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง (หมั้น)
สี่
หนี่ง
สาม
ดี
หนึ่ง
สี่ (หมั้น)
สาม
สอง
ตารางแสดงความหมายปองรอบปัจจุบัน
คำอธิบาย
เอ
---
---
---
---
บี
---
---
---
---
ซี
---
---
---
---
ดี
สี่
---
---
---
"สี่" เป็นบุคคลเดียวที่ยังไม่มีคู่หมั้นชั่วคราว
"สี่" ทำการเลือกคู่ในรอบที่ 5 โดยเลือก "ดี"
"ดี" ตอบรับการขอของ "สี่" ด้วยการหมั้นชั่วคราว
เสร็จสิ้นการเลือกคู่สมรส
รายชื่อที่หมายปองของฝ่ายชาย
รายชื่อที่หมายปองของฝ่ายหญิง
ชาย
หญิงอันดับ1
หญิงอันดับ2
หญิงอันดับ3
หญิงอันดับ4
หนึ่ง
เอ
ซี
ดี
บี
สอง
บี
เอ
ดี
ซี
สาม
บี
ดี
ซี
เอ
สี่
ซี
เอ
ดี
บี
หญิง
ชายอันดับ1
ชายอันดับ2
ชายอันดับ3
ชายอันดับ4
เอ
หนึ่ง (หมั้น)
สี่
สอง
สาม
บี
สาม (หมั้น)
หนี่ง
สอง
สี่
ซี
สอง (หมั้น)
สี่
หนี่ง
สาม
ดี
หนึ่ง
สี่ (หมั้น)
สาม
สอง
จากตารางจะพบว่าไม่มีสมาชิกของฝ่ายชายและฝ่ายหญิงใด ที่ยังไม่มีคู่หมั้น จึงได้คำตอบของปัญหาการแต่งงานที่มีเสถียรภาพ ดังนี้
ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า
ทุกคนจะได้ทำการสมรส เนื่องจาก ฝ่ายชายแต่ละคนจะมีรายชื่อของฝ่ายหญิงที่ตนหมายปองครบทุกคน ดังนั้นจะไม่มีฝ่ายหญิงคนใดเลยที่ไม่ถูกเลือก โดยฝ่ายชาย จึงเป็นไปไม่ได้ที่จะทั้งฝ่ายหญิงและฝ่ายชายเป็นโสดพร้อมกันในที่สุด
การสมรสมีเสถียรภาพ เนื่องจากการที่ฝ่ายหญิงมีสิทธิ์ที่จะเลือกฝ่ายชายที่ตนเองหมายปองด้วยเช่นกัน สมมติเช่น ถ้าหากเกิดสถานการณ์ที่ฝ่ายหญิงมีคู่หมั้นชั่วคราวอยู่แล้ว แต่ว่ามีฝ่ายชายที่หมายปองตนและตนนั้นก็พึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราวของตน ฝ่ายหญิงมีสิทธิ์ที่จะถอนหมั้น และทำการหมั้นกับฝ่ายชายคนใหม่ที่ตนพึงพอใจมากกว่าได้ ดังนั้นจึงรับประกันได้ว่าฝ่ายหญิงจะได้แต่งงานกับฝ่ายชายที่ตนพึงพอใจมากที่สุด จึงทำให้การสมรสมีเสภียรภาพ
วิเคราะห์ประสิทธิภาพการทำงาน
แก้
ตัวอย่างการประยุกต์ใช้งาน
แก้
มีการนำขั้นตอนวิธีของ เกล-แชปลีย์ ไปประยุกต์ใช้อย่างกว้างขวาง ยกตัวอย่างเช่น การคัดเลือกนักเรียนชั้นประถมศึกษาเพื่อเข้าศึกษาต่อในโรงเรียนระดับมัธยมศึกษาของประเทศสิงคโปร์ [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] ).