约束规划是人工智能领域的重要分支,在产品配置、任务调度、组合优化等问题上有广泛的应用。约束规划为实际问题提供了一种简单有效的解决方案,首先通过约束建模将实际问题抽象成统一的约束模型,然后利用约束求解技术对模型进行求解。结合相容性技术的回溯搜索算法是约束求解的主流方法之一,通过相容性技术对回溯搜索过程进行剪枝可以提高问题求解的效率。表约束是一种重要的约束的表示形式,通过枚举支持或者禁止元组将约束以表格的形式呈现。表约束处理的目的是维持约束网络的相容性,表约束处理对整个问题求解过程影响巨大。广义弧相容(GAC)是目前应用最为广泛的相容性,其简单高效性在大多数问题实例上有良好的效果。简单表缩减算法(STR算法)及其优化(STR2算法和STR3算法)是在表约束上维持广义弧相容的高效算法,STR算法通过动态维持有效支持元组来保证约束网络的相容性。STR2算法对STR算法做出两点改进,一方面如果两次相容性检查过程中变量论域未发生改变,则跳过该变量上值的有效性检查。另一方面如果某变量论域中的值均存在有效支持,则停止为该值继续寻找支持。STR3算法将表约束的表示形式变为对偶表,在对偶表上维持约束网络的相容性。然而随着问题中变量个数的增加,表约束规模可能呈指数阶上升,表约束处理的效率将会下降。有学者使用笛卡尔积压缩方法对正表约束进行压缩,并提出压缩正表上维持广义弧相容的方法STR2-C算法和STR3-C算法,在压缩率较高的问题实例上,其空间规模和时间效率均优于STR2算法和STR3算法。负表是正表的互补表示形式,负表是约束上所有禁止元组的集合。当负表规模较小时,直接处理负表效率更高。STR-N算法是针对负表约束提出的简单表缩减算法,可以直接在负表上维持约束网络的相容性。STR-N算法计算有效元组与有效禁止元组的差值,根据差值是否为零判断论域中的值是否满足广义弧相容,从而进一步检查整个约束网络的相容性。但STR-N算法维持约束网络相容性时需要遍历负表中的所有元组,当负表规模较大时算法效率较低。因此,受STR2-C算法和STR3-C算法的启发,本文对STR-N算法进行了优化,首先使用笛卡尔积压缩方法将负表进行压缩得到压缩负表,并提出在压缩负表上维持广义弧相容的方法STRC-N算法。STRC-N算法同样是通过计算有效元组与有效禁止元组的差值来检查约束网络的相容性,但是STRC-N算法统计有效禁止元组数的方法却有所不同。STRC-N算法直接处理有效压缩禁止元组,有效压缩禁止元组上一次遍历可以统计多个有效标准禁止元组。经过笛卡尔积压缩后,压缩负表的空间规模更小,STRC-N算法更加节省空间。得益于压缩负表规模的减小,STRC-N算法相对于STR-N算法速度更快,效率更高。