Answer Set Programming 无给定起点的哈密顿环正确模型过滤问题

你之前的修改存在核心逻辑错误：把reached(X) :- begin(X)改成reached(X) :- node(X)相当于直接废掉了连通性校验规则，所有节点默认被标记为已到达，原来「路径必须连通且覆盖所有节点」的约束完全失效，自然会生成大量无效的路径组合。

按以下方案修改即可回到你要的2个正确结果，同时可以灵活配置是否固定起点：

修正后的class.lp代码 #

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

% 起点配置
start(4). % 固定4为起点，和原有需求对齐
% {start(S)} :- node(S). % 若不需要固定起点，注释上一行、启用这行即可自动选起点
:- #count{S: start(S)} != 1. % 保证全局只有一个起点

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

% test
% 所有节点必须在路径上可达
:- node(X), not reached(X).
% 每个节点最多1条出边
:- path(X,Y), path(X,Y1), Y!=Y1.
% 每个节点最多1条入边
:- path(X,Y), path(X1,Y), X!=X1.
% 固定路径边数：n个节点的哈密顿路径有且仅有n-1条边
:- node(N), #count{X,Y: path(X,Y)} != N-1.

如果你实际需要求解的是哈密顿环（路径终点可回到起点形成闭环），额外添加以下约束即可：

% 哈密顿环专属约束：终点必须有边连回起点
:- start(S), path(_,S), not path(Y,S), path(Y,_).

修改完成后运行clingo class.lp instance.lp 0，就会输出你需要的2个正确模型。

内容的提问来源于stack exchange，提问作者cheshire