在 Prolog 中实现顶点覆盖

Question

我正在尝试在序言中实现 vertex covering。我正在考虑执行以下操作：

按以下格式使用图 [(VertexSouce/VertexDest), ...] 并传递图中的顶点总数。所以谓词看起来像这样 vertexCover(NodeCount, Graph, MaxNodesInResult, Result)。 Result 应小于 MaxNodesInResult`

我得到了以下示例输出：

?- vertexCover(6,[(1/2),(1/3),(2/3),(2/4),(3/5),(4/5),(4/6)],3,L).
L = [1,3,4] ;
L = [2,3,4] ;
false.
?- vertexCover(6,[(1/2),(1/3),(2/3),(2/4),(3/5),(4/5),(4/6)],2,L).
false.

感谢任何帮助！

Answer 1

这是一个可行的解决方案，感谢 Isabelle 的修复！正如她提到的，我发现的另一个解决方案是在 covers/2 的第二行添加一个剪切，但她的解决方案更加清晰。

vertexCover(N,L1,M,L2) :- numlist(1, N, L), comb(M,L,L2), covers(L2,L1).

covers(_,[]).
covers(L,[H|T]) :- isIn(L,H), covers(L,T).

isIn([A|T],(X/Y)) :-  (( A = X ; A = Y ) -> true
                       ;   isIn(T, (X/Y)) ).

comb(0,_,[]).
comb(N,[X|T],[X|Comb]):-    N>0,N1 is N-1,comb(N1,T,Comb).
comb(N,[_|T],Comb):-        N>0,comb(N,T,Comb).

Answer 2

这确实应该是 Dartuso 对正确解决方案的评论，但它不适合。所以这里是一个替代答案。使用 Dartuso 的代码，您会得到重复的答案：

?- vertexCover(6,[(1/2),(1/3),(2/3),(2/4),(3/5),(4/5),(4/6)],3,L).
L = [1, 3, 4] ;
L = [1, 3, 4] ;
L = [2, 3, 4] ;
L = [2, 3, 4] ;
L = [2, 3, 4] ;
L = [2, 3, 4] ;
false.

得到重复的答案并没有错。但有时出于性能原因或只是为了获得更好的输出，我们希望避免它们。

在这种情况下，重复来自这样一个事实，即单个边缘可以以多种方式出现在封面中：

?- isIn([1, 3], (1/3)).
true ;
true ;
false.

这是因为Dartuso给出的isIn/2的子句不是相互排斥的。第一个和第二个子句都匹配这个查询，这就是为什么你会获得两次成功的原因。

有几种方法可以"fix"。最干净的是添加条件以排除前面条款已经涵盖的情况：

isIn([A|_],(X/_)) :-
    A = X.
isIn([A|_],(X/Y)) :-
    dif(A, X),
    A = Y.
isIn([A|T],(X/Y)) :-
    dif(A, X),
    dif(A, Y),
    isIn(T,(X/Y)).

这里的dif/2谓词表示不平等。因此第二个子句在第一个子句中的等式已经涵盖的情况下不再成功，这消除了重复成功和重复答案：

?- isIn([1, 3], (1/3)).
true ;
false.

?- vertexCover(6,[(1/2),(1/3),(2/3),(2/4),(3/5),(4/5),(4/6)],3,L).
L = [1, 3, 4] ;
L = [2, 3, 4] ;
false.

一个不太好的解决方案使用 "if-then-else" 构造 Condition -> TrueBranch ; FalseBranch 这并非没有问题（但非常实用！）：

isIn([A|T],(X/Y)) :-
    (   A = X
    ->  true
    ;   A = Y
    ->  true
    ;   isIn(T, (X/Y)) ).

或者，正如我在实践中可能会写的那样：

isIn([A|T],(X/Y)) :-
    (   ( A = X ; A = Y )
    ->  true
    ;   isIn(T, (X/Y)) ).

使用后一种解决方案，上面的查询只成功一次，甚至没有留下选择点：

?- isIn([1, 3], (1/3)).
true.

有了这个，整个谓词也不再有重复的答案：

?- vertexCover(6,[(1/2),(1/3),(2/3),(2/4),(3/5),(4/5),(4/6)],3,L).
L = [1, 3, 4] ;
L = [2, 3, 4] ;
false.

在这种特殊情况下，if-then-else 只会删除不需要的重复解决方案，但通常它可以删除您确实想要的解决方案。小心使用。

（其他人可能会告诉您使用剪切运算符 !/0，因为它比其中一些解决方案更短。不要屈服。更短的代码不会自动成为更好的代码，并且剪切会使您的代码特别复杂并且难以理解和修改。）

在 Prolog 中实现顶点覆盖

Implementing vertex covering in Prolog

math

prolog

graph-theory

np