一种求解合取范式可满足性问题的数学物理方法 |
| |
引用本文: | 李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法[J].中国科学A辑,1994,37(11):1208-1217. |
| |
作者姓名: | 李未 黄文奇 |
| |
作者单位: | 北京航空航天大学计算机系 北京 100083
华中理工大学计算机系 武汉 430074 |
| |
摘 要: | 给出合取范式与带电质点在某类静电场中势函数的一一对应关系,证明判断一个合取范式是否可满足等价于判断一个带电质点在相应的静电场中是否有使其势函数为零的位置,由于带电质点在静电场中总是沿使其势能下降最快的方向,也就是沿其势函数梯度指引的方向运动,并最终达到势能最低的位置。因此,对一个客观上可满足的合取范式所对应的势函数,使用梯度算法是求使该合取范式成真的赋值的高效算法。
|
关 键 词: | 合取范式 势函数 梯度算法 |
|
| 点击此处可从《中国科学A辑》浏览原始摘要信息 |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 |
|