本文關(guān)鍵詞：基于抽象論辯理論的穩(wěn)定匹配問題研究

  更多相關(guān)文章： 穩(wěn)定匹配問題 穩(wěn)定婚姻問題 穩(wěn)定室友問題 抽象論辯理論 論辯框架

【摘要】：穩(wěn)定匹配問題(簡(jiǎn)稱為SM)一直是數(shù)學(xué)、運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)和社會(huì)學(xué)等領(lǐng)域研究的熱點(diǎn)問題。穩(wěn)定匹配問題通常以矩陣形式出現(xiàn),因此多以組合數(shù)學(xué)的方法進(jìn)行計(jì)算,比較依賴數(shù)組的順序特性,適合求解性別優(yōu)先的單個(gè)穩(wěn)定匹配結(jié)果。圖論也是求解穩(wěn)定匹配較常用的理論之一,主要從穩(wěn)定匹配問題的結(jié)構(gòu)著手,通過求解符合某些特點(diǎn)的二分圖來(lái)計(jì)算穩(wěn)定匹配結(jié)果。無(wú)論是從組合數(shù)學(xué)的角度還是從圖論的角度,對(duì)穩(wěn)定匹配問題的研究都缺少系統(tǒng)的形式化刻畫,并且求解過程高度抽象。傳統(tǒng)的研究無(wú)法高效地判斷單個(gè)配對(duì)的狀態(tài),因?yàn)橐粋�(gè)配對(duì)必須在某個(gè)穩(wěn)定匹配中才是穩(wěn)定配對(duì),因此我們必須計(jì)算出完整的穩(wěn)定匹配才能判斷單個(gè)配對(duì)的狀態(tài)。此外,穩(wěn)定匹配問題具有非單調(diào)性,而已有的研究著重分析新加入的對(duì)象以及原有對(duì)象所獲得的匹配更好或者更差,不能很好地處理穩(wěn)定匹配問題的動(dòng)態(tài)計(jì)算問題。論辯理論可以很好地解決上述問題。穩(wěn)定匹配問題是一個(gè)在沖突的信息中進(jìn)行選擇——評(píng)估——再選擇——再評(píng)估的過程,可以用抽象論辯框架對(duì)其進(jìn)行刻畫。與組合數(shù)學(xué)和圖論的方法相比,基于論辯的分析更貼合我們的日常推理過程。我們將每一個(gè)配對(duì)抽象為論證,將對(duì)象間互相的偏好度抽象為論證間的二元攻擊關(guān)系,因此計(jì)算穩(wěn)定匹配時(shí)可以從任何一個(gè)論證入手,而不必依賴原有的順序特征。抽象論辯框架有各種語(yǔ)義,而我們可以選擇穩(wěn)定語(yǔ)義和優(yōu)先語(yǔ)義現(xiàn)有的算法對(duì)不同的穩(wěn)定匹配問題進(jìn)行求解,如基于回答集編程的方法(ASP),基于加標(biāo)的方法(MC),基于強(qiáng)連通分量的方法(SCC)和基于絕對(duì)被駁斥論證的方法(MSR)。論辯語(yǔ)義可以計(jì)算出所有穩(wěn)定匹配結(jié)果,并且所求得的結(jié)果是無(wú)性別差異的(當(dāng)然,對(duì)于穩(wěn)定婚姻問題,男士最優(yōu)和女士最優(yōu)的結(jié)果也在所有的穩(wěn)定匹配中)。我們可以通過提高論辯語(yǔ)義計(jì)算效率來(lái)提高穩(wěn)定匹配的計(jì)算效率,例如,將整個(gè)論辯框架劃分為多個(gè)更小的SCC,分別計(jì)算每個(gè)SCC,然后合并各個(gè)部分的語(yǔ)義；或者將絕對(duì)被駁斥論證——被基外延攻擊的論證從計(jì)算過程中刪除。我們可以用論辯爭(zhēng)議樹來(lái)判斷單個(gè)配對(duì)是否穩(wěn)定,是否屬于所有穩(wěn)定匹配。當(dāng)穩(wěn)定匹配問題發(fā)生變化時(shí),例如增加匹配對(duì)象、改變偏好列表、刪除配對(duì),通過論辯框架可以對(duì)匹配結(jié)果的數(shù)量改變和內(nèi)容變化進(jìn)行分析,并且用論辯語(yǔ)義的動(dòng)態(tài)計(jì)算對(duì)穩(wěn)定匹配問題進(jìn)行比較高效的重新求解。我們首先介紹抽象論辯理論,然后用抽象論辯框架對(duì)穩(wěn)定婚姻和穩(wěn)定室友問題進(jìn)行了刻畫：包括帶完整全序偏好列表的經(jīng)典穩(wěn)定婚姻問題sm和經(jīng)典穩(wěn)定室友問題sr,帶完整非全序偏好列表(又稱偏序列表或無(wú)差別列表)的穩(wěn)定婚姻問題smt和穩(wěn)定室友問題srt,帶全序不完整偏好列表的穩(wěn)定婚姻問題smi和穩(wěn)定室友問題sri,帶非全序不完整偏好列表的穩(wěn)定婚姻問題smti和穩(wěn)定室友問題srti。對(duì)穩(wěn)定匹配問題進(jìn)行論辯形式化后,我們用論辯語(yǔ)義證明的方法來(lái)判斷單個(gè)配對(duì)的狀態(tài)；然后用穩(wěn)定語(yǔ)義來(lái)求解sm、smt、smi、smti問題,用優(yōu)先語(yǔ)義求解sr、 srt、sri、srti問題。最后在靜態(tài)求解的基礎(chǔ)上根據(jù)論辯動(dòng)態(tài)性的研究對(duì)穩(wěn)定匹配問題的動(dòng)態(tài)性進(jìn)行分析,主要介紹基于劃分的動(dòng)態(tài)計(jì)算方法和基于論證狀態(tài)的計(jì)算方法。通過分析,我們證明穩(wěn)定語(yǔ)義和優(yōu)先語(yǔ)義的求解結(jié)果就是我們所要求取的相應(yīng)的穩(wěn)定匹配結(jié)果,并且如果穩(wěn)定匹配結(jié)果存在,我們總是能用相應(yīng)的論辯語(yǔ)義進(jìn)行求解。對(duì)于某個(gè)配對(duì),如果該配對(duì)相應(yīng)的論證沒有被輕信證成(在某個(gè)語(yǔ)義下),則該論證不屬于任何外延,該配對(duì)也不屬于任何穩(wěn)定匹配。穩(wěn)定匹配問題的論辯框架有其自身的特點(diǎn)——每個(gè)論證都與其他論證有直接或間接的關(guān)系,使得我們無(wú)法很好地劃分SCC,并且使用基于加標(biāo)的方法也會(huì)延長(zhǎng)判斷的過程,因此,我們用基于擴(kuò)展的MSR方法：從每一個(gè)論證出發(fā),嘗試將其擴(kuò)展為最大可相容集合。對(duì)于穩(wěn)定匹配問題的動(dòng)態(tài)性研究,我們首先以穩(wěn)定婚姻問題為例分析了配對(duì)增加或刪除以及偏好列表中滿意度改變對(duì)穩(wěn)定匹配結(jié)果造成的影響；然后介紹基于劃分的動(dòng)態(tài)計(jì)算方法,并在此基礎(chǔ)上提出基于論證狀態(tài)的方法,進(jìn)一步縮小需要重新計(jì)算的范圍。
【關(guān)鍵詞】：穩(wěn)定匹配問題 穩(wěn)定婚姻問題 穩(wěn)定室友問題 抽象論辯理論 論辯框架
【學(xué)位授予單位】：浙江大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2014
【分類號(hào)】：B81-0
【目錄】：

• 致謝5-6
• 摘要6-8
• Abstract8-16
• 第1章 引言16-28
• 1.1 匹配問題19-21
• 1.2 已有研究存在的問題21-26
• 1.3 主要內(nèi)容26-28
• 第2章 論辯理論28-43
• 2.1 基于擴(kuò)展的定義29-31
• 2.2 基于加標(biāo)的定義31-35
• 2.3 論辯語(yǔ)義的計(jì)算35-41
• 2.3.1 基于加標(biāo)的方法35-38
• 2.3.2 基于ASP的算法38-40
• 2.3.3 基于SCC的算法40
• 2.3.4 基于MSR的算法40-41
• 2.4 論辯框架的動(dòng)態(tài)性41-43
• 第3章 穩(wěn)定匹配問題的論辯框架43-67
• 3.1 穩(wěn)定婚姻問題的論辯框架43-57
• 3.1.1 sm的論辯框架44-50
• 3.1.2 smt的論辯框架50-52
• 3.1.3 smi的論辯框架52-55
• 3.1.4 smti的論辯框架55-57
• 3.2 穩(wěn)定室友問題的論辯框架57-67
• 3.2.1 sr的論辯框架57-62
• 3.2.2 srt的論辯框架62-63
• 3.2.3 sri的論辯框架63-64
• 3.2.4 srti的論辯框架64-67
• 第4章 穩(wěn)定匹配問題的論辯語(yǔ)義計(jì)算67-95
• 4.1 單個(gè)配對(duì)的穩(wěn)定性判斷67-77
• 4.1.1 穩(wěn)定配對(duì)69-73
• 4.1.2 固定配對(duì)73-77
• 4.2 穩(wěn)定匹配的求解77-95
• 4.2.1 基于矩陣旋轉(zhuǎn)的方法77-79
• 4.2.2 基于MSR的計(jì)算方法79-90
• 4.2.3 基于無(wú)沖突集合擴(kuò)展的方法90-95
• 第5章 穩(wěn)定婚姻問題的論辯動(dòng)態(tài)性95-106
• 5.1 sm問題：增加或刪除配對(duì)95-98
• 5.2 sm問題：改變偏好列表98-101
• 5.3 匹配問題的動(dòng)態(tài)計(jì)算101-106
• 5.3.1 基于劃分的方法101-102
• 5.3.2 基于論證狀態(tài)的方法102-106
• 第6章 結(jié)語(yǔ)106-108
• 6.1 內(nèi)容回顧106
• 6.2 創(chuàng)新點(diǎn)與不足106-108
• 參考文獻(xiàn)108-114
• 作者簡(jiǎn)歷114

【相似文獻(xiàn)】

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前1條

1 鐘仁明;何垠波;李曉玉;陳林;姜慶豐;柏森;許峰;;IGRT放療中匹配結(jié)果與放療精度[A];2007第六屆全國(guó)放射腫瘤學(xué)學(xué)術(shù)年會(huì)論文集[C];2007年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 馬素華;同構(gòu)對(duì)稱發(fā)布/訂閱系統(tǒng)中Top-k算法的研究與實(shí)現(xiàn)[D];東北大學(xué);2012年

，

本文編號(hào)：596207