计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2012年
4期
227-231
,共5页
调查传播算法%难解区域%蚁群算法%局部搜索
調查傳播算法%難解區域%蟻群算法%跼部搜索
조사전파산법%난해구역%의군산법%국부수색
布尔可满足性问题(Boolean Satisfiability Problem,SAT)是逻辑学的一个基本问题,也是NP-hard问题.调查传播算法(Survey Propagation,SP)是求解SAT的一种非常高效的算法,但SP在难解区域极易不收敛,或者出现错误赋值.将SP算法与蚁群算法结合,把SP算法得到的消息值应用到蚁群算法中来求解3-SAT问题,使用这些消息值引导蚁群算法求解,并在算法中加入高效的局部搜索.新算法对于SP算法不收敛的一些实例也能很快找到解.
佈爾可滿足性問題(Boolean Satisfiability Problem,SAT)是邏輯學的一箇基本問題,也是NP-hard問題.調查傳播算法(Survey Propagation,SP)是求解SAT的一種非常高效的算法,但SP在難解區域極易不收斂,或者齣現錯誤賦值.將SP算法與蟻群算法結閤,把SP算法得到的消息值應用到蟻群算法中來求解3-SAT問題,使用這些消息值引導蟻群算法求解,併在算法中加入高效的跼部搜索.新算法對于SP算法不收斂的一些實例也能很快找到解.
포이가만족성문제(Boolean Satisfiability Problem,SAT)시라집학적일개기본문제,야시NP-hard문제.조사전파산법(Survey Propagation,SP)시구해SAT적일충비상고효적산법,단SP재난해구역겁역불수렴,혹자출현착오부치.장SP산법여의군산법결합,파SP산법득도적소식치응용도의군산법중래구해3-SAT문제,사용저사소식치인도의군산법구해,병재산법중가입고효적국부수색.신산법대우SP산법불수렴적일사실례야능흔쾌조도해.
