博文
多解的子句块关联段求解
|||
多解的子句块关联段求解
姜咏江
都是多解的子句块形成的关联段，求解时要先解决有可能形成无解的情况。表1中可能形成无解的情况只有底纹暗色的部分，那么选取x1和x4及x5的值，就要注意不能够产生无解的剩余子句块。
图1中用子句消去法若选择x1＝1，x4＝1就会出现无解的情况。因而求解中要避开无解。
表1 多解的子句块关联
|
|
|
|
|
|
|
|
|
|
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 |
0 | 0 | 0 |
|
|
|
|
|
|
|
0 | 0 | 1 |
|
|
|
|
|
|
|
1 | 1 | 0 |
|
|
|
|
|
|
|
1 | 1 | 1 |
|
|
|
|
|
|
|
| 1 | 0 | 1 |
|
|
|
|
|
|
| 1 | 0 | 0 |
|
|
|
|
|
|
| 1 | 1 | 0 |
|
|
|
|
|
|
| 1 | 1 | 1 |
|
|
|
|
|
|
| 0 | 0 |
| 0 |
|
|
|
|
|
| 1 | 0 |
| 0 |
|
|
|
|
|
|
|
| 0 | 0 |
| 1 |
|
|
|
|
|
| 0 | 1 |
| 1 |
|
|
|
|
|
| 0 | 0 | 0 |
|
|
|
|
|
|
|
| 1 | 1 | 0 |
|
|
|
|
|
|
| 0 | 1 | 1 |
|
|
|
|
|
|
|
|
| 1 | 1 | 1 |
|
|
|
|
|
|
|
| 0 | 0 | 1 |
|
|
|
|
|
|
| 1 | 0 | 0 |
这个问题中，只要选择x1＝0，就进入了可解状态。
显然，多解子句块间有两个变量相互关联段才有可能出现无解的情况，而只有一个变量关联的多解子句块间不会形成无解。
2015-12-15
https://blog.sciencenet.cn/blog-340399-943506.html
上一篇：3SAT剩余子句块多解表示方法
下一篇：详解3SAT归约到子集和问题的方法
扫一扫，分享此博文
全部作者的精选博文
全部作者的其他最新博文
全部精选博文导读
相关博文
- • Minerals线下恳谈会：履践致远、与时偕行——对话中国科学院广州地球化学研究所期刊合作学者
- • 聚英才 建高地 | 北京理工大学“特立青年学者”全球招聘开启
- • 700年后日本或濒临灭绝？日本学者推算预测：届时或仅剩1名15岁以下孩子
- • [转载]【同位素视角】非英语母语学者如何区分’e.g.’, ‘i.e.’, ‘namely’与‘such as’等混淆难题
- • 美国佐治亚大学等机构学者：刈割策略对Bulldog 805紫花苜蓿+Tifton 85狗牙根混播草地产量及品质的影响
- • 美国堪萨斯州立大学、密苏里大学等机构学者研究成果：土壤水分管理策略和品种多样性对紫花苜蓿产量、营养品质和农场盈利能力的影