检测和删除最少数量不一致事实的算法(可能在PROLOG中)？

Question

你如何编程以下算法？

想象一下像这样的"事实"列表,其中字母表示绑定到数值的变量:

x = 1
y = 2
z = 3
a = 1
b = 2
c = 3
a = x
b = z
c = z

这些"事实"显然不一定都是"真实的":当b = 2且z = 3时,b = z是不可能的.如果删除b = z或b = 2,则所有事实都是一致的.如果z = 3且b = z或c = z被移除,那么所有事实都是一致的,但事实上会比上面少一个.该集包含许多这样的一致子集.例如,a = 1,b = 2,c = 3是一致的子集,许多其他子集也是如此.

在此示例中,两个一致的子集大于任何其他一致的子集:

x = 1
y = 2
z = 3
a = 1
b = 2
c = 3
a = x
c = z

和

x = 1
y = 2
z = 3
a = 1
c = 3
a = x
b = z
c = z

使用适当的编程语言(我正在考虑PROLOG,但也许我错了)你将如何处理包含一致和不一致事实的大集合,然后输出最大可能的一致事实子集(或多个子集,如上面的例子)？

Answer 1

这与NP难多道切割问题密切相关.在(未加权)多道切割问题中,我们有一个无向图和一组终端顶点.目标是尽可能少地去除边缘,以便每个终端顶点位于其自己的连接组件中.

对于这个问题,我们可以将每个变量和每个常量解释为一个顶点,并将每个相等解释为从左侧到右侧的边.终端顶点是与常量相关的顶点.

对于仅两个端子,多路切割问题是多项式时间可解决的最小切割问题.我们可以使用最小切割来获得多向切割问题的多项式时间2近似,通过找到分离两个端子的最便宜切割,删除所涉及的边缘,然后对剩余的连接组件进行递归.在多道切割的理论文献中已经提出了几种具有更好比率的近似算法.

实际上,在计算机视觉的应用中出现了多向切割,因此我希望在获得精确解决方案方面已经有了一些工作.不过,我不知道那里有什么.