国科大学习资料--人工智能原理与算法-第六次作业解析（学长整理）

国科大学习资料–人工智能原理与算法-第六次作业解析（张文生老师主讲）（6.6、6.7、6.11）

6.6 说明如何通过使用辅助变量把诸如A+B=C这样的三元约束转变成三个二元约束。假设值域是有限的。（提示：考虑引进新变量表示变量对的值，引进约束如“X是Y变量对中的第一个元素”。）然后说明如何把多于三个变量的约束类似地转换为二元约束。说明如何通过改变变量的值域来消除一元约束。这就完整演示了任何CSP都可以转变为只含二元约束的CSP。

答：首先，我们引入一个新变量AB,假设A和B的范围均为N,AB的范围为N×N。存在3个二元约束条件，一个在A和AB之间，则表明A的值必须与AB成对值中的第一个元素相等；一个在B和AB之间，则表明B的值必须与AB成对值中的第二个元素相等；一个是C和AB之间，则表明C的值必须与AB成对值得和相等，从而实现了将三元约束转变成了二元约束。
其次，针对把多于三个变量的约束类似地转换为二元约束问题，由于前面已经实现了将三元约束转变成二元约束，对于新增加的多元约束，例如四元约束，可以首先通过将其中3元约束转化成二元约束，此时四元约束就转换成了3元约束，然后再利用3元约束变换成二元约束操作即可实现。所以即可实现将多于三个变量的约束类似的转换成二元约束。
最后，通过前面的证明，我们可以将任意的n元约束转化为n-1元约束，又因为任何的一元约束可以通过将约束的效果移动到变量即可删掉，所以我们可以将任何CSP都可以转变为只含二元约束的CSP。

6.7考虑下述的逻辑问题：有5所不同颜色的房子，住着5个来自不同国家

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！