答案集编程——从大量模型中筛选

Question

instance.lp

node(1). node(2). node(3). node(4). node(5). node(6).
edge(1,2). edge(2,1). edge(4,1). edge(2,3). edge(2,6).
edge(3,4). edge(3,5). edge(5,6). edge(6,3).
begin(4).

我有这个问题实例，有向图有一个起始节点 begin(4) 和相应的边。在此图中，只能从节点 4 (4->1->2->3->5->6 或 4->1->2->6->5->3) 开始得到哈密尔顿循环我的问题 class 只有在我给它起始节点 4 和 returns 2 个这样的模型时才能解决它：

class.lp

% generate
{path(X,Y)} :- edge(X,Y).

% define
reached(X) :- begin(X).
reached(Y) :- reached(X), path(X,Y).

% test
:- node(X), not reached(X).
:- path(X,Y), path(X,Y1), Y!=Y1.
:- path(X,Y), path(X1,Y), X!=X1.

当我运行喜欢 clingo 时:

clingo class.lp instance.lp 0

我得到了 2 个模型（汉密尔顿周期）。

我想运行它而不给它起点，但是当我用 node(X)[ 替换 begin(X) 时=36=]:

. . % define reached(X) :- node(X). reached(Y) :- reached(X), path(X,Y). . .

我得到 120 个模型。

我的猜测是现在它生成了所有可能的组合并且我添加了额外的约束来过滤出正确的解决方案。

我如何从这个答案集中筛选出两个正确的模型？

Answer 1

您的代码不会生成哈密顿循环，而是生成 n 个节点有 n-1 条边的哈密顿路径。我只是假设你想生成路径。所以你的 begin/1 生成器坏了：

reached(X) :- node(X).

你字面上的意思是：我的所有节点都到达了。
这是修复：

{ begin(X) : node(X) } == 1.

它有什么作用？它的内容如下：对于所有节点 X，只选择一个 begin(X) 有效。使用

的输出

#show begin/1.
#show path/2.

如下：

Answer: 1
path(1,2) path(4,1) path(3,4) path(5,6) path(6,3) begin(5)
Answer: 2
path(1,2) path(4,1) path(2,3) path(3,5) path(5,6) begin(4)
Answer: 3
path(1,2) path(4,1) path(2,6) path(3,5) path(6,3) begin(4)
SATISFIABLE

答案集编程——从大量模型中筛选

Answer Set Programming - filtering from a large number of models

logic-programming

answer-set-programming

clingo

gringo