| 姓名 |
顏志瑜(Chih-yu Yen)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
穩定婚姻及穩定配偶的模擬
(The Simulation of Stable Marriage and Stable Pairs)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
本文主要在於探討穩定配對中的穩定婚姻問題，提及穩定男伴、拆散配對以及P循環的概念，重新推導 Knuth, Motwani 與 Pittel 的結論:
對任何女生的穩定男伴為至少 max(0,(1/2-epsilon)lnn ，最多為 (1+epsilon)lnn 個的機率趨近 1，當n → ∞ 時，其中 0< varepsilon <1 。並介紹兩種方法找到所有的穩定配對，透過 C++ 模擬結果比較各方法的優缺點，並與理論值作比對。
|
| 摘要(英) |
In this paper we study the stable marriage and stable husbands problems of stable matching, using the concept of breakmarriage and p-cycle, and revisit the result of Knuth ,Motwani and, Pittel :
any particular girl has at least max(0, (1/2−epsilon) ln n) and at most (1+epsilon) ln n different husbands, with probability approaching 1 as n → ∞, if 0 < epsilin < 1. We introduce two methods to find all stable matchings and simulate in C++ programming language to compare these two methods and theoretical results.
|
| 關鍵字(中) |
★ 穩定婚姻
★ 穩定配偶 |
關鍵字(英) |
★ stable marriage
★ stable pairs |
| 論文目次 |
1. 簡介................................................1
2. 穩定配對 ...........................................2
2.1 穩定男伴........................................2
2.2 隨機模型........................................6
2.3 機率性定理......................................7
3. 拆散配對...........................................23
3.1 基本觀念.......................................23
3.2 所有穩定配對...................................25
4. P循環..............................................30
4.1 所有穩定配偶...................................30
4.2 演算法.........................................31
4.3 利用 P 循環架構 G..............................34
4.4 樹狀圖 T.......................................37
5. 結論...............................................39
參考文獻..............................................40
附錄一................................................41
附錄二................................................44
附錄三................................................46
附錄四................................................50
|
| 參考文獻 |
[1] D. Gale and L. S. Shapley (1962), College admissions and the stability of marriage, Am. Math. Monthly, 69, 9-15.
[2] R. L. Graham, D. E. Knuth, and O.Patashnik (1989), Concrete Mathematics, AddisonWesley, Reading, MA.
[3] D. Gusfield (1987), The fast algorithms for four problems in stable marriage, SIAM J. Comput. 16, 111-128.
[4] D.E.Knuth (1976), Marriages Stable et leurs relations avec d'autres problemes combinatoires, Les Presses de l'Universite de Montreal, Montreal.
[5] D.E. Knuth (1988), Personal Communication .
[6] D.E. Knuth and R. Motwani and B. Pittel (1990), Stable husbands, Random Structures and Algorithms, Vol.1, No.1.
[7] D. G. McVitie and L. B. Wilson(1971), The stable marriage problem, Commun. ACM, 14 , 486-492.
[8] B. Pittel (1989), The average number of stable matchings, SIAM J. Discr. Math., to appear.
|
| 指導教授 |
于振華(Jenn-hwa Yu)
|
審核日期 |
2010-7-21 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
