(34.239.158.107) 您好!臺灣時間:2019/08/21 11:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:顏志瑜
研究生(外文):Chih-yu Yen
論文名稱:穩定婚姻及穩定配偶的模擬
論文名稱(外文):The Simulation of Stable Marriage and Stable Pairs
指導教授:于振華
指導教授(外文):Jenn-hwa Yu
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文出版年:2010
畢業學年度:98
語文別:中文
論文頁數:60
中文關鍵詞:穩定婚姻穩定配偶
外文關鍵詞:stable marriagestable pairs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:215
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:55
  • 收藏至我的研究室書目清單書目收藏:0
本文主要在於探討穩定配對中的穩定婚姻問題,提及穩定男伴、拆散配對以及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.
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔