算法設(shè)計與分析課程設(shè)計報告——穩(wěn)定婚姻問題的gale-shapley算法-文庫吧
2025-01-04 00:53 本頁面
【正文】 擊追求自己最喜歡的女生策略，女生采用“守株待兔”和“喜新厭舊”策略。每一位男生主動去追求自己最喜歡的女生，而女生則在追求自己的男生中與現(xiàn)任男友中，選擇一位最喜歡的接受。如果追求成功，為被拋棄的男友追求他下一位喜歡的女生。如果追求不成功，則為這位男生追求他下一位喜歡的女生。這樣進行了N次循環(huán)后，每一位男生都是從自己最喜歡的女生開始追求，并且都有女友，那么男生喜歡的程度多于現(xiàn)任妻子的那位女生肯定是曾經(jīng)拒絕過自己的。同理，女生也是按照自己喜歡程度進行選擇的。那么也不會出現(xiàn)不穩(wěn)定問題。三、 程序模塊說明1. 總體設(shè)計說明：程序采用兩個二維數(shù)組man[max][max],woman[max][max]來記錄max位男生，女生對異性的喜歡程度順序。數(shù)組acman[]記錄男生下一位追求的女生順序（最開始從0位，也就是最喜歡的一位開始）；數(shù)組acwoman[]記錄每一位女生當(dāng)前男友（最開始設(shè)置一位虛擬男友，其喜歡程度最?。┎捎?個for循環(huán)，分別對4個數(shù)組初始化。采用一個for循環(huán)遍歷man數(shù)組（為每一位男生追求其最喜歡的女生）采用一個for循環(huán)輸出結(jié)果2. 模塊說明： 模塊一：bool changeBF(vectorvectorint woman,int i,int newBF,int oldBF,int max)函數(shù)(1) 概要說明：判斷某位女生的當(dāng)前男友與追求她的男友的排位順序（喜歡程度）(2) 關(guān)鍵數(shù)據(jù)結(jié)構(gòu)和算法及其分析（比較newBF和oldBF在數(shù)組woman[][max]的序號大小，從而判斷喜歡程度）(3) 輸入（數(shù)組woman[][]）(4) 輸出(bool類型1,0)四、 總結(jié)（含主函數(shù)設(shè)計說明）穩(wěn)定婚姻問題被應(yīng)用到許多實際問題的處理過程中，例如學(xué)生的入學(xué)，工作招聘，但是為找到所有的穩(wěn)定匹配結(jié)果，我們設(shè)計了基于先序遍歷森林的算法，利用此算法，對于眾多不同的婚姻匹配，不會重復(fù)判斷它們包含相同的配對子部分，這樣大大節(jié)省了時間。為了進一步提高速度，由GaleShapl
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1