任一时间面向任务联盟结构生成算法.pdfVIP

CN43-1258／TP 计算机工程与科学 2008年第 3O卷第 12期 ISSN 1007—130X COMPUTERENGINEERING ＆ SCIENCE Vo1．3O，No．12，2008 文章编号：1007-130X(2008)12—0085—05 任一时间面向任务联盟结构生成算法 AnAnytimeCoalitionStructureGeneration inTask—BasedSettings 骆剑彬 ，胡山立 ，苏射雄 。林耀海l- LUOJiambinj。HUShan-li，SUShe-xion~，LINYao-haiI· (1．福州大学计算机科学与技术系，福建 福州 350002；2．福建农林大学计算机与信息学院，福建 福州35ooo2) (1．DepartmentofComputerScienceandTechnology，FuzhouUniversity。FUyJlou350002； 2．DepartmentofComputerScienceandTechnology，FujianAgricultureandForestryUniversity。Fuzhou350002，China) 摘 要：联盟形成是多Agent系统中的一个关键问题。目前，大多数学者都在CFG下研究联盟结构生成问题。然而， 在很多实际应用中，联盟的形成往往是为了完成任务集中某些任务。但是，在 CFG中并没有把联盟和任务一起考虑。显 然，加入任务后，问题将变得更复杂。Dang等人 已经证明，这是个NP难问题 ，并且要建立最坏情况下的限界K(n， )，搜 索面向任务联盟结构集合L、Lz(除{(A， )，(， ))是必要且充分的，接着提 出一个限界具有保证的任一时间算法。本 文深刻分析 了面向任务联盟结构间的关系，引入更小的有哪些信誉好的足球投注网站粒度 (面向任务势结构)，提 出一种新的任一时间有哪些信誉好的足球投注网站算法；在 有哪些信誉好的足球投注网站完最小有哪些信誉好的足球投注网站之后，进一步有哪些信誉好的足球投注网站C了’S集合C了、5(，m，6)对应的部分面向任务联盟结构，渐进给出越来越低的限界，大 大改进 了Dang等人的工作。 Abstract：Coalitionformationisakeytopicinmulti-agentsystems．Atpresent，mostworkoncoalitionstructuregener- ationhasconcentratedonsimplecharacteristicfunctiongames(CFGs)．However，inmanypracticalapplications，itisoften thecasethatacoalitionisformedinordertOperform sometasks．ButinCFGsthisconnectionbetweencoalitionsisabsent Thenotionoftasksgenerallyincreasesthecomplexityoftheproblem．Dangeta1．hasshownthattheproblem isNP-hrad anditSHfficestosearchthesetoftask-basedcoalitionstructure(except{(A， )，( ，T)))inordertoestablishaworst- caseboundK(n，m)，andhaspresentde annaytimealgorithm withboundguarantee．Thispaperanalyzestherelationsa— mongtask-basedcoalitionstructuresindepthandpresentsthesma llergrnaularityofseraching(task-basedcardinalitysturc— ture)．Thenwepresentsanew anytimealgoritmh basedonthecardinalitysturcturethatonlyhastOtakeastepfurthernad searchthosetask-has