基于序列的分配方式是一個簡單且應(yīng)用廣泛的資源分配方式。分配機構(gòu)需要把一系列不可分割的物品分配給多個代理人,代理人對物品有偏好,分配過程是代理人根據(jù)給出的序列依次選擇物品且只能選擇剩余的物品。該分配方式不具備防策略性,即代理人可以通過謊報自己對物品的偏好來獲得更好的效用。因此研究者提出了基于序列的物品分配的操縱問題,研究代理人如何采取策略,給出一個使自己效益達到最大的物品偏好。該問題在只有兩個代理人（一個是操控者,一個是非操控者）時是多項式可解的,也被證明了當(dāng)代理人個數(shù)為輸入的時候是NP難的。那么對于常數(shù)個代理人,哪怕只有三個代理人的時候,該問題的計算復(fù)雜性并不清楚,成為了一個重要的公開難題。本文最重要的一項貢獻就是解決了這個公開難題,給出了一個算法,該算法在任何常數(shù)個代理人時都是多項式運行時間。在算法設(shè)計中,我們提出了兩個重要的概念:關(guān)鍵問題和不變性。關(guān)鍵問題與原問題有相同的最優(yōu)解,但是關(guān)鍵問題可以利用貪心算法快速解決。解決原始問題則可以轉(zhuǎn)換成尋找與原始問題具有相同最優(yōu)解的關(guān)鍵問題。我們定義了問題的支配關(guān)系,提供了搜索關(guān)鍵問題的空間,與原始問題有相同最優(yōu)解的關(guān)鍵問題一定在原始問題支配的... 

【文章來源】：電子科技大學(xué)四川省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：65 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
abstract
第一章 緒論
    1.1 研究工作的背景與意義
    1.2 基于序列的物品分配問題的國內(nèi)外研究歷史與現(xiàn)狀
    1.3 本文的主要貢獻與創(chuàng)新
    1.4 本論文的結(jié)構(gòu)安排
第二章 基于序列的物品分配模型
    2.1 代理人的偏好
    2.2 代理人的序列
    2.3 基于序列的物品分配模型的操縱問題
    2.4 本章小結(jié)
第三章 基于序列的物品分配問題模型的精確算法
    3.1 最優(yōu)解問題介紹
    3.2 關(guān)鍵問題
    3.3 暴力搜索
    3.4 不變性
    3.5 動態(tài)規(guī)劃算法
        3.5.1 動態(tài)規(guī)劃介紹
        3.5.2 最優(yōu)解問題的動態(tài)規(guī)劃算法
    3.6 記憶化搜索
    3.7 本章小結(jié)
第四章 基于序列的物品分配問題模型的近似算法
    4.1 近似算法介紹
    4.2 基于貪心策略的近似算法
    4.3 近似率
    4.4 近似率的緊致性
    4.5 本章小結(jié)
第五章 實驗測試
    5.1 實驗準(zhǔn)備
        5.1.1 對比算法介紹
        5.1.2 實驗數(shù)據(jù)
        5.1.3 參數(shù)、環(huán)境和指標(biāo)
    5.2 暴力搜索和記憶化搜索的對比
        5.2.1 平衡序列的實驗結(jié)果
        5.2.2 極端序列的實驗結(jié)果
    5.3 近似算法實驗
    5.4 本章小結(jié)
第六章 全文總結(jié)與展望
    6.1 全文總結(jié)
    6.2 后續(xù)工作展望
致謝
參考文獻
攻讀碩士學(xué)位期間取得的成果



本文編號：2961837