資源描述：
《一種有效的決定優(yōu)勝者問題的近似算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、Vol125No.7July2004第25卷第7期2004年7月小型微型計(jì)算機(jī)系統(tǒng)MINI-MICROSYSTEMS一種有效的決定優(yōu)勝者問題的近似算法李崢,李師賢(中山大學(xué)計(jì)算機(jī)科學(xué)系,廣東廣州510275)摘要:組合拍賣是多Agent系統(tǒng)常用的一種協(xié)商機(jī)制,而決定優(yōu)勝者問題是該機(jī)制不可避免的一個(gè)NP問題.這個(gè)問題的近似算法CASUS,相對(duì)于前人的工作,它主要在以下方面作了改進(jìn):提出更精確的估算收益上界的啟發(fā)規(guī)則;提出對(duì)叫價(jià)進(jìn)行兩級(jí)處理,并在分析算法復(fù)雜度的基礎(chǔ)上,限定搜索空間的大小,保證多項(xiàng)式時(shí)間內(nèi)有解;大大降低了算法的空間復(fù)雜度.關(guān)鍵詞:決定優(yōu)勝者問題;組合拍賣;啟發(fā)規(guī)則;深度優(yōu)先搜索中圖
2、分類號(hào):TP311.132.3文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):100021220(2004)0721393204EfficientApproximateAlgorithmforWinnerDeterminationLIZheng,LIShi2xian(DepartmentofComputerScience,ZhongshanUniversity,Guangzhou510275,China)Abstract:CombinatorialAuctionisapopularnegotiationmechanisminMulti2agentsystem,andWinnerDeterminationisthees
3、sentialNPprobleminthismechanism.Inthisarticle,anapproximatealgorithmforWinnerDeterminationisputforward.Comparewithothers’work,thisalgorithmhasbeenimprovedintheseaspects:inheuristicsearchingprovideamoreaccurateheuristicruleforestimatingtheupperlimitofrevenue;basedonthealgorithmanalysis,re2strictthese
4、archingspaceefficientlybytwo2layerdisposalsonbids,thisensurethealgorithmtoobtaintheresultinpolynomialtimeandmakeitmuchbetterthanthemainstreamalgorithmsinspacecomplexity.Keywords:winnerdetermination;combinatorialauction;heuristicrule;depth-firstsearch1引言明確地表達(dá)這種關(guān)聯(lián),它同時(shí)對(duì)多種資源進(jìn)行分配,允許A2gent同時(shí)拋出任意多個(gè)叫價(jià),每個(gè)叫價(jià)都
5、是針對(duì)一個(gè)資源集的,而不是單個(gè)資源.組合拍賣的重要性在于允許Agent根據(jù)它對(duì)資源的使用將相關(guān)聯(lián)的資源作為一個(gè)整體進(jìn)行叫價(jià),這樣做更為合理,Rothkopf在1998年的一篇論文中重點(diǎn)闡述了使用組合拍賣的合理性4.因此,在實(shí)際應(yīng)用中組合拍賣有很大的適用空間,在這方面比較著名的例子是美國(guó)聯(lián)邦通信協(xié)會(huì)FCC售賣通信波段的交易,在引入合理的拍賣機(jī)制后,給它帶來了數(shù)十億美元的收入3.1.1問題的提出拍賣機(jī)制越來越引起分布式人工智能領(lǐng)域的研究者的重視,因?yàn)榕馁u是一種有效的多Agent系統(tǒng)中的協(xié)商機(jī)制,廣泛地被應(yīng)用于資源分配、時(shí)間調(diào)度、路由選擇、商品交易等領(lǐng)域的協(xié)商系統(tǒng)中.在這些領(lǐng)域的應(yīng)用中,以資源分配為
6、例,代表競(jìng)價(jià)者的競(jìng)價(jià)Agent往往希望對(duì)一個(gè)資源的集合進(jìn)行叫價(jià),而不是對(duì)資源集合中的每項(xiàng)資源單獨(dú)叫價(jià).因?yàn)楦?jìng)價(jià)Agent通常需要多項(xiàng)資源來完成一個(gè)任務(wù),比如,某個(gè)Agent需要一臺(tái)打印機(jī)和一臺(tái)掃描儀來完成一項(xiàng)工作,在這項(xiàng)工作中它可以獲得x元的收入,于是它就知道如果它以低于x元的價(jià)格一并獲得打印機(jī)和掃描儀,它就能賺錢,因此在它的眼中,打印機(jī)和掃描儀就具有某種關(guān)聯(lián),它希望以它們作為一個(gè)資源集進(jìn)行出價(jià).在實(shí)際應(yīng)用中,從用戶角度出發(fā)的這種“關(guān)聯(lián)”是普遍存在的,比如鐵路的使用權(quán)的拍賣中,競(jìng)價(jià)者也許希望獲得一組首尾相接的鐵路的使用權(quán);又比如在工廠的時(shí)間調(diào)度中,競(jìng)價(jià)者也許希望同時(shí)獲得包含多個(gè)時(shí)間片的一整段時(shí)
7、間的占用權(quán).組合拍賣(CombinatorialAuction)就是允許競(jìng)價(jià)Agent1.2問題的描述組合拍賣中有一個(gè)不可避免的NP完全的計(jì)算問題——決定優(yōu)勝者問題(WinnerDetermination).決定優(yōu)勝者問題是指作為供給方的Agent在收到競(jìng)價(jià)Agent的叫價(jià)后,決定將資源分配給誰(shuí)的問題.它必須在所有叫價(jià)中選出一個(gè)叫價(jià)子集,這個(gè)叫價(jià)子集中的叫價(jià)都是不相沖突的,即它們都針對(duì)不同的資源,
