CAJ | 학술논문

联盟形成是多Agent系统中的一个关键问题. 寻求能极大化联盟值总和的最优联盟结构是NP-完全的. Sandholm等人已经证明要建立最坏情况下的限界k,搜索联盟结构图的最底两层是必要且是充分的,在搜索联盟结构图的最底两层之后如何进一步搜索,是个长期以来未能解决的问题. Dang等人给出的算法,对于奇数限界k≥3,在搜索最底两层及顶层后,进一步搜索最大联盟的势不小于- n(k-1)/(k+1) - 的所有联盟结构,是迄今所知的第1个不以层为搜索单位的算法,对于较小的限界明显地优于Sandholm等人给出的算法. 文中深刻分析了联盟结构间的关系,提出的算法在搜索最底两层后,只需进一步搜索最大联盟的势等于- n(k-1)/(k+1) - 的所有联盟结构,从而使需要搜索的联盟结构数大大减少,并进一步将搜索某些层最大联盟的势等于- n(k-1)/(k+1) - 的联盟结构巧妙地改为搜索联盟结构数更少的相应层,使需要搜索的联盟结构数进一步减少,较大地改进了Sandholm等人和Dang等人的工作.
련맹형성시다Agent계통중적일개관건문제. 심구능겁대화련맹치총화적최우련맹결구시NP-완전적. Sandholm등인이경증명요건립최배정황하적한계k,수색련맹결구도적최저량층시필요차시충분적,재수색련맹결구도적최저량층지후여하진일보수색,시개장기이래미능해결적문제. Dang등인급출적산법,대우기수한계k≥3,재수색최저량층급정층후,진일보수색최대련맹적세불소우- n(k-1)/(k+1) - 적소유련맹결구,시흘금소지적제1개불이층위수색단위적산법,대우교소적한계명현지우우Sandholm등인급출적산법. 문중심각분석료련맹결구간적관계,제출적산법재수색최저량층후,지수진일보수색최대련맹적세등우- n(k-1)/(k+1) - 적소유련맹결구,종이사수요수색적련맹결구수대대감소,병진일보장수색모사층최대련맹적세등우- n(k-1)/(k+1) - 적련맹결구교묘지개위수색련맹결구수경소적상응층,사수요수색적련맹결구수진일보감소,교대지개진료Sandholm등인화Dang등인적공작.