1

实例.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）并且我的问题类只有在我给它起始节点 4 时才能解决它，并返回 2 个这样的模型：

类.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.

当我用 cligo 像这样运行它时：

clingo class.lp instance.lp 0

我得到了 2 个模型（汉密尔顿循环）。

我想在不给它起点的情况下运行它，但是当我用node(X)替换begin(X ) 时：

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

我有 120 个模型。

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

我将如何从这个答案集中过滤两个正确的模型？

4

1 回答 1

1

您的代码不会生成汉密尔顿循环，而是生成具有 n-1 个边的 n 节点的汉密尔顿路径。我只是假设你想生成路径。所以你的发电机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
于 2021-11-28T21:38:45.883 回答