creatio ex nihilo

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

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
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 น. 0 comments
Counter : 1094 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.