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