图 书 馆
统一调查信仰可满足性的传播方式Unified survey-belief propagation approach for satisfiability |
|
| 课程网址: | http://videolectures.net/oiml05_pretti_usbpa/ |
| 主讲教师: | Marco Pretti |
| 开课单位: | 都灵理工大学 |
| 开课时间: | 2007-02-25 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In this talk I shall discuss a modified message-passing BP (Belief Propagation) procedure, which can be generally used to minimize variational Bethe free energies in statistical physics. By a straightforward mapping, this algorithm can be easily applied to combinatorial optimization problems, such as 3-satisfiability, the prototype of NP-hard problems. I show that the method can be also extended to the framework of SP (Survey Propagation), a recently proposed algorithm which, still making use of techniques borrowed from statistical physics, overcomes problems encountered by local search algorithms on hard instances close to the ``SAT-UNSAT'' transition. This allows to obtain a unified and quite stable message passing scheme, which can be used both in the ``full replica-symmetry-breaking'' region, where ordinary Belief Propagation usually does not converge, and in the ``hard'' region near the sat-unsat transition, where it allows to solve subformulae generated by ``survey inspired decimation''. |
| 关 键 词: | 统计物理; 组合优化; 消息传递方案 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-06-02：张荧(课程编辑志愿者) |
| 阅读次数: | 53 |