基于偏序任务的社会网络合作算法研究

来源：计算机研究与发展杂志2016年第11期北京时间：

作者：刘勇,韩雪,李金宝,任倩倩,王楠,

摘要：针对不同任务之间通常存在偏序关系这种实际情况，提出了基于偏序任务的社会网络合作问题(collaborationprobleminsocialnetworksbasedontaskswithpartialorderingrelations,CSN-TPR).该问题研究如何从社会网络中选择合适的团队来合作完成具有偏序关系的任务集，使得由通信代价、时间代价和预算代价构成的总体代价性能最优.首先证明了CSN-TPR是NP-hard问题，然后利用爬山法、分支限界策略和动态规划方法提出了近似算法HillClimbingTF_BBS.HillClimbingTF_BBS算法不仅输出有效的团队，而且能给出团队成员的具体任务分配以及每项任务的开始时间.真实数据上的实验结果表明：HillClimbingTF_BBS算法能有效并高效求解CSN-TPR.

关键词：社会网络, 合作, 偏序关系, 爬山法, 分支限界,