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