ผู้ใช้:DearcIV/Sandbox/ปัญหาการแต่งงานที่มีเสถียรภาพ

ปัญหาการแต่งงานที่มีเสถียรภาพ (อังกฤษ: Stable Marriage Problem) คือ ปัญหาของการหาคู่สมรสที่มีเสถียรภาพระหว่างฝ่ายชายและฝ่ายหญิง โดยการจับคู่ สมรสระหว่างฝ่ายชายและฝ่ายหญิงที่ถือว่ามีสเถียรภาพจะต้องไม่เกิดกรณีทั้ง 2 กรณีดังต่อไปนี้

1. มีฝ่ายชายบางคนที่พึงพอใจฝ่ายหญิงบางคน ในขณะที่ฝ่ายชายคนนั้นได้ทำการเลือกคู่สมรสของตนไปแล้ว
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

ด้วยขั้นตอนวิธีนี้ จะสามารถรับประกันได้ว่า

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

ตัวอย่างการประยุกต์ใช้งาน

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

วิเคราะห์ประสิทธิภาพการทำงาน

ใช้พื้นที่ในการเก็บรายชื่อที่หมายปองของทั้งฝ่ายชายและฝ่ายหญิงเป็น $2n^{2}$

สมมติฐาน

สมมติฐานที่ 1: ฝ่ายชายขอแต่งงานกับฝ่ายหญิงด้วยลำดับความพึงพอใจที่ลดลงจากมากไปน้อย
สมมติฐานที่ 2: ฝ่ายหญิงที่ทำการหมั้นไปแล้วครั้งหนึ่ง จะไม่มีทางที่จะไร้คู่สมรสเพราะเธอจะไม่ถอนหมั้นก็ต่อเมื่อไม่เจอฝ่ายชายที่เลือกตนและตนพึงพอใจฝ่ายชายคนนั้นมากกว่าคู่หมั้นชั่วคราว

การแก้ปัญหาแบบถึก (Brute-force)

• เวลาที่ใช้ในการทำงานในกรณีแย่สุดที่ใช้การตรวจสอบรายชื่อทั้งหมด เป็น $n!x$ (เวลาที่ใช้ในการตรวจสอบเสถียรภาพของการจับคู่) เท่ากับ Θ$(n!n^{2})$

การพิสูจน์ความถูกต้อง

1. ขั้นตอนวิธีนี้จะหยุดการทำงานสำหรับกรณีช้าที่สุดเป็น $n^{2}$ จากการทำงานของวงวน

• พิสูจน์: จากรายชื่อที่หมายปองทั้งหมดของฝ่ายชายมีจำนวนรูปแบบที่เป็นไปได้ $n^{2}$ รูปแบบ ดังนั้น วงวนจะทำงานเป็นจำนวนครั้งมากที่สุดเท่ากับ $n^{2}$ ครั้ง

2. ฝ่ายชายและฝ่ายหญิงทุกคนได้แต่งงานกันทุกคน

• พิสูจน์โดยหาข้อขัดแย้ง

• • สมมติให้นายหนึ่ง ไม่มีคู่เลยแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
  • จะพบ มีนางสาวเอ ไม่มีคู่เช่นกันแม้ว่าการทำงานของขั้นตอนวิธีจะจบลงแล้ว
  • จากสมมติฐานที่ 2 แสดงว่านางสาวเอ ไม่มีฝ่ายชายคนไหนเลยที่ปรารถนาจะแต่งงานด้วยเลย
  • แต่จากปัญหานี้ ฝ่ายชายทุกคนจะทำการเลือกฝ่ายหญิงทุกคน ตามลำดับความพึงพอใจ ดังนั้น นายหนึ่ง ทำการเลือกนางสาวเอ แล้ว
  • ดังนั้นจึงเป็นไปไม่ได้ที่จะมีฝ่ายชายหรือฝ่ายหญิงคนใด ไม่มีคู่

3. ไม่มีคู่สมรสใด ที่ขาดเสถียรภาพ

• พิสูจน์โดยหาข้อขัดแย้ง

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

สรุป

• ขั้นตอนวิธีของเกล-แชปลีย์ รับประกันว่าจะสามารถหาคู่สมรสที่มีเสถียรภาพได้เสมอ ๆ สำหรับฝ่ายชาย และฝ่ายหญิงที่มีจำนวนเท่ากัน
• เวลาและเนื้อที่ที่ใช้สำหรับขั้นตอนวิธีของเกล-แชปลีย์ เป็น Ο$(n^{2})$

ลิงค์ภายนอก

• SMP Lecture Notes