%0 Journal Article
%T 低约束密度分布式约束优化问题的求解算法
%A 丁博？
%A 王怀民？
%A 史殿习？
%A 唐扬斌？
%J 软件学报
%P 625-639
%D 2011
%R 10.3724/SP.J.1001.2011.03765
%X 多agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.
%K 分布式约束优化问题
%K 多agent
%K 算法
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3765&flag=1