| 层次图(混合Horn)公式的部分极大可满足性 |
| |
| 引用本文： | 埃瓦尔特·施佩肯梅尔,史蒂凡·珀尔舜.层次图(混合Horn)公式的部分极大可满足性[J].逻辑学研究,2010(3):24-43. |
| |
| 作者姓名： | 埃瓦尔特·施佩肯梅尔 史蒂凡·珀尔舜 |
| |
| 作者单位： | 科隆大学计算机科学研究所 |
| |
| 基金项目： | We would like to thank Mattias Gartner for executing the implementational part. |
| |
| 摘 要： | 本文为解决一类混合Horn公式(13,14]),又称为层次图公式(15])的MAXSAT问题进行了基于随机局部搜索过程的经验研究。具体地,我们首先在随机CNF公式的MAX2SAT及MAX3SAT问题上进行WalkSAT和Tabu-Sat(及其变种)的比较,其次,我们在层次图公式上比较了上述过程的改进版本,这些公式编码了随机生成层次图的最小化跨边问题。本文所引入的Tabu-Sat过程,当在搜索空间中检测到一个圈的时候,动态地改变Tabu长度参数。另一个被称为Vector-Tabu-Sat的过程,对所有的布尔变元进行独立的Tabu长度参数管理。一些数值实验的结果显示,我们改进的Tabu-Sat变种在子句个数增长的时候优于Walksat.
|
| 关 键 词： | 公式 混合 搜索空间 数值实验 随机 最小化 变种 长度 |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
