如何在Answer Set Programming(ASP)中用递归实现全路径遍历？

原代码核心问题 #

• ASP不支持N + 1这类变量运算，必须通过整数域枚举定义合法步数范围
• 缺少点不重复访问的约束：仅判断当前步与上一步点不同，未保证所有已访问点唯一
• 无递归终止/完成条件：无法确保遍历完所有5个点

修正后的完整代码 #

% 定义所有节点
point(1..5).

% 定义步数范围：起点为第0步，需跳4次覆盖5个点，步数取值0-4
step(0..4).

% 固定起点：第0步位于点1
jump(0, 1).

% 递归跳转规则：第N+1步跳至从未访问过的点Y
possible_jump(N1, Y) :-
    step(N), N1 = N + 1, step(N1),  % 限定合法的步数递增逻辑
    jump(N, X),                     % 上一步所在节点为X
    point(Y), Y != X,               % Y是不同于X的有效节点
    not jump(_, Y).                 % Y未被任何之前的步数访问过

% 约束：第1-4步必须且只能选择一个合法跳转
1 { jump(N, X) : possible_jump(N, X) } 1 :- step(N), N > 0.

% 强制约束：所有节点必须被访问到，过滤未完成遍历的结果
:- point(X), not jump(_, X).

#show jump/2.

关键逻辑说明 #

• 用step(0..4)明确步数范围，规避ASP不支持变量运算的限制
• 通过not jump(_, Y)确保每个节点仅被访问一次，实现无重复遍历
• 新增全局约束:- point(X), not jump(_, X).，保证最终结果是覆盖所有5个点的完整路径
• 跳转选择规则仅对第1-4步生效，第0步固定为起点无需选择

运行后会输出所有以1为起点的全排列路径，例如：

jump(0,1) jump(1,2) jump(2,3) jump(3,4) jump(4,5)
jump(0,1) jump(1,3) jump(2,2) jump(3,5) jump(4,4)
...（共4!种合法路径）

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