|
所有变量都被界定了，所有约束都满意了，一个方案就被找到。
CP就是一个搜索的方案，基于约束问题主要有以下组成:
－具有给定值的域的几种变量
－在这些变量的几种约束
基本上, 我们要找到方案, 就是要给一值，对所有变量来满足所有约束或找到最佳方案,给一值对所有变量来满足所有约束，及来优化一给定的准则。
约束传播的优点：
约束解决问题的理论复杂性，约束程序的理论复杂性是指数的。给定V 具有N大小的域的变量, 有 N^V 可能分配给变量的值
CP的优点:
1.搜寻树在传播的每一步是减少。
2.传播可以尽早触发一个失败
3.在减少变量域之前, 传播使得启发更好的运作
CP-总结
1.一个约束程序专注有限域约束变量和约束.
2.当已标出后，约束触发初始域减少.
3.当变量得到修正, 改变其它变量的影响是被约束传播的。
4.专注于复杂排程问题
5.CP应该用于非常复杂约束限制排程问题如很难找到任何可行的方案。
6.基于
约束传播
分枝和定界
注意: CP 是启发搜索方法，它不能保证是找到的是最优化的方案
(完)
本文由作者向AMT提供
蔡颖
专栏 |
