stable marriage Theorem
สาว ๆ n คนลิสต์อันดับหนุ่ม ๆ ในดวงใจ n คน หนุ่ม ๆ ทั้ง n คน ก็ลิสต์อันดับสาว ๆ เช่นเดียวกัน David Gale กับ Lloyd Shapley นักคณิตศาสตร์เศรษฐศาสตร์ชาวอเมริกัน บอกเราว่าสามารถสร้างคู่ที่สมดุล (stable) สำหรับทุกคนได้เสมอ คู่ที่สมดุลหมายถึงคู่ที่ไม่มีคู่ใดแตกจากคู่ปัจจุบันเพื่อไปสร้างคู่ใหม่



แนวคิดเรียบง่ายครับ สาว W หมายปองหนุ่ม M ถ้าหนุ่ม M ยังไม่มีคู่ ก็จับคู่ (M,W) เข้าด้วยกัน แต่ถ้าหนุ่ม M มีคู่อยู่แล้วคือ (M,W') ก็ให้ดูว่า M ปรารถนาสาวใดมากกว่ากัน W หรือ W' ถ้าเขาอยากเป็นคู่กับ W มากกว่า ก็จับคู่ (M,W) สำหรับ W' ต้องขีดฆ่าชื่อ M ออกจากลิสต์ แต่ถ้าเขาอยากจับคู่กับ W' มากกว่า ก็คงคู่ (M,W') ไว้ดังเดิม ส่วน W ก็ต้องขีดฆ่าชื่อ M ออกจากลิสต์



ตัวอย่าง ชาย 4 หญิง 4


จากตารางนี้เห็นชัดว่า (M1,W1), (M2,W2), (M3,W3), (M4,W4) เป็นคู่ที่ไม่เสถียร คู่ที่สมดุล หรือเสถียรจากตัวอย่างนี้คือ (M1,W2), (M2,W1), (M3,W4), (M4,W3) คงเป็นโชคร้ายของคู่ (M3,W4) ทั้ง 2 คนไม่ค่อยชอบกัน แต่ก็หมดตัวเลือกอื่น ๆ แล้ว










Create Date : 23 ธันวาคม 2550
Last Update : 23 ธันวาคม 2550 23:06:38 น.
Counter : 1125 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

ศล
Location :
กรุงเทพ  Thailand

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด