计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2012年
12期
2618-2624
,共7页
多Agent系统%联盟结构%势结构%给定限界%分组
多Agent繫統%聯盟結構%勢結構%給定限界%分組
다Agent계통%련맹결구%세결구%급정한계%분조
联盟形成是多Agent系统中的一个关键问题,寻求能极大化联盟值总和的最优联盟结构是NP-完全的.Sandholm等人已经证明,要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的.当实际应用提出最坏情况下的具体限界要求时,如何通过进一步的最小搜索找到一个能保证在最坏情况下其联盟结构值与最优的联盟结构值相距在一个给定的限界内的联盟结构,是个长期以来值得研究而又尚未解决的问题.文中深刻分析了不同的分组方法对需要搜索的势结构数的影响,针对给定限界,在最坏情况下提出一种新的分组方法和一个新的联盟结构生成算法,使需要搜索的势结构数和联盟结构数比已有的算法都大大减少.
聯盟形成是多Agent繫統中的一箇關鍵問題,尋求能極大化聯盟值總和的最優聯盟結構是NP-完全的.Sandholm等人已經證明,要建立最壞情況下的限界k,搜索聯盟結構圖的最底兩層是必要且是充分的.噹實際應用提齣最壞情況下的具體限界要求時,如何通過進一步的最小搜索找到一箇能保證在最壞情況下其聯盟結構值與最優的聯盟結構值相距在一箇給定的限界內的聯盟結構,是箇長期以來值得研究而又尚未解決的問題.文中深刻分析瞭不同的分組方法對需要搜索的勢結構數的影響,針對給定限界,在最壞情況下提齣一種新的分組方法和一箇新的聯盟結構生成算法,使需要搜索的勢結構數和聯盟結構數比已有的算法都大大減少.
련맹형성시다Agent계통중적일개관건문제,심구능겁대화련맹치총화적최우련맹결구시NP-완전적.Sandholm등인이경증명,요건립최배정황하적한계k,수색련맹결구도적최저량층시필요차시충분적.당실제응용제출최배정황하적구체한계요구시,여하통과진일보적최소수색조도일개능보증재최배정황하기련맹결구치여최우적련맹결구치상거재일개급정적한계내적련맹결구,시개장기이래치득연구이우상미해결적문제.문중심각분석료불동적분조방법대수요수색적세결구수적영향,침대급정한계,재최배정황하제출일충신적분조방법화일개신적련맹결구생성산법,사수요수색적세결구수화련맹결구수비이유적산법도대대감소.
