ASP 哈密顿循环的故事
ASP Hamiltonian Cycle Story
你好我是answer-set-programming. I have done a little prolog新来的！
我正在尝试解决这个问题，我相信它可以用 hamiltonian-cycle 解决，让我知道你的意见。如果您不熟悉 ASP，您可以访问此站点 [clingo 和 gringo][1]。您可以使用此命令 运行 终端中的文件 clingo name_of_the_file.lp 或 clingo name_of_the_file.lp4 我在 Ubuntu.
中对其进行了测试
（这些是 .lp 或 .lp4 文件）
我阅读和理解的第一个代码是有 3 个结果的代码
% Generating part
% ---------------
% Cardinality constraint:
% For any ground fact cycle(X,Y) in the answer set:
% - there must be a corresponding edge(X,Y)
% - there must be exactly 1 of cycle(X,Y) for any X
% - there must be exactly 1 of cycle(X,Y) for any Y
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Testing part
% ------------
% It is a contradiction to that have a "node" that is not "reached"
:- node(Y), not reached(Y).
% Defining part
% -------------
% Nodes
node(1..6).
% (Directed) Edges
edge(1,(2;3;4)). edge(2,(4;5;6)). edge(3,(1;4;5)).
edge(4,(1;2)). edge(5,(3;4;6)). edge(6,(2;3;5)).
% Edge Costs cost(X,Y,Cost)
cost(1,2,2). cost(1,3,3). cost(1,4,1).
cost(2,4,2). cost(2,5,2). cost(2,6,4).
cost(3,1,3). cost(3,4,2). cost(3,5,2).
cost(4,1,1). cost(4,2,2).
cost(5,3,2). cost(5,4,2). cost(5,6,1).
cost(6,2,4). cost(6,3,3). cost(6,5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Displaying part
% ---------------
#show cycle/2.
我得到这个结果：
clingo version 5.4.0
Reading from cycle_hamilt.lp4
Solving...
Answer: 1
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,6) cycle(6,5) cycle(5,3)
Optimization: 13
Answer: 2
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 12
Answer: 3
cycle(1,2) cycle(4,1) cycle(3,4) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 11
OPTIMUM FOUND
Models : 3
Optimum : yes
Optimization : 11
Calls : 1
Time : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.003s
我试着把这段代码转换成这样：
% Generate
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).
% Define
reached(Y) :- cycle(street1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).
% Nodes
%node(1..6).
node(street1..street6).
%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
这个看起来有点尴尬我得到这个结果：
clingo version 5.4.0
Reading from cleaning_street_names.lp4
Solving...
UNSATISFIABLE
Models : 0
Calls : 1
Time : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.003s
我试着按照你在评论中告诉我的那样更正它：
% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).
% Nodes
%node(1..6).
node(street1..street6).
%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
我得到了这个结果：
clingo version 5.4.0
Reading from cleaning_street_names.lp4
cleaning_street_names.lp4:30:6-22: info: interval undefined:
street1..street6
Solving...
Answer: 1
SATISFIABLE
Models : 1
Calls : 1
Time : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.002s
（如果我输入 node(1..6)。结果是 UNSATISFIABLE）
问题出在这段代码中:
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).
您已将 1 替换为原子 street1。
但原始程序中的 1 不是 "street" 的 标识符（更像是 交叉点 ：节点是交叉路口，边是街道，因为从概念上讲，很难以单向方式从另一条街道到达一条街道，而且成本是固定的，是吗？ t it?)，而是一个 value：它是 cardinality constraint。正确的表达方式是：
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
表示：
对于答案集中的任何基本事实 cycle(X,Y)：
- 必须有对应的
edge(X,Y)
- 对于任何
X ，必须恰好有 cycle(X,Y) 中的 1 个
- 对于任何
Y ，必须恰好有 cycle(X,Y) 中的 1 个
不知道clingo为什么不抗议？我还没试过 运行 这个。
"Hamiltonian"循环还是"Chinese Postman Problem"循环？
注意你写的；
The above problem can be modeled by representing the map of the city
with a directed graph and the challenge is to visit all the edges (ie
roads) at least once
这是完全正确的：边是 roads/streets，因此将名为 1..6 的节点重新标记为 street1..[=24= 在概念上是错误的（尽管在语法上是等效的） ].
给出的程序然后继续解决 Hamiltonian Path problem (every node visted exactly once) whereas it should solve the (comnplexity-wise simpler) Route Inspection/Chinese Postman 问题（每条边至少访问一次，最好只访问一次）。
原程序的约束
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
表示对哈密顿路径的约束（还不是哈密顿循环在同一节点开始和结束，只是一条路径）。对于任何一个节点，只有一条入边属于环，也只有一条出边属于环。因此，每个节点只被访问一次 => 哈密顿路径。
(不知道reached是不是多余的？如果不是，为什么不呢？)
原始问题的图表
- 节点是蓝色圆圈。
- 成本是白色椭圆。
- 循环的起始节点是 1。
- 箭头指示如何遍历边（按照惯例）
- 指出了一个解决方案。
更新：我在 ASP
的尝试
这个 ASP 东西很棘手。我不确定如何正确表达问题。一个大问题是我们不知道要搜索多深，我发现攻击的唯一方法是 运行 具有连续更大 max_time 值的程序，直到 SATISFIABLE 是输出。问题是我们生成了 "exactly one literal at every time T" 到
的可能路径
1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).
然后根据约束检查这些 path/2 组文字。与 Prolog 不同，我们因此不能 "terminate when we reach node 1 and all edges have been visited"。这是如何正确完成的？我虽然关于 edge(1,1) 上的 "parking the path" 最后成本为 0，但这使程序变得混乱，我没有成功指定关于路径结构的全局约束，然后由 "good part"、一个 "hit node 1 one last time" 和一个 "tail part to be disregarded"。
% ===
% Attempt at the "Chinese Postman Problem" / "Route Inspection Problem"
% ===
% https://en.wikipedia.org/wiki/Route_inspection_problem
% Original statement:
%
% "Find a shortest closed path or circuit that visits every edge of an
% (connected) undirected graph."
%
% Here:
%
% "Find a closed path (cycle) starting from node 1 that visits every pair
% (X,Y) of nodes of a directed graph where that pair is connected by an edge
% (X->Y) or (Y->X) or both. Every edge has an associated
% cost. Find the cycle with the minimum cost."
%
% "max_time" is the length of the resulting path. Sadly, one has to manually
% reduce "max_time" in a stepwise fashion until the shortest path is found.
% How can that be done programmatically?
#const max_time=13.
time(1..max_time).
% ---
% Generating part
% ---
% For every time "T", there is exactly one path/2 literal indicating that
% the path element for time T goes via edge(X,Y).
1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).
% ---
% Defining part
% ---
% "Start at node 1", alias:
% "The path/2 literal for time=1 cannot be based on an edge/2 literal that
% does not start at node 1"
:- path(e(X,Y),t(1)), edge(X,Y), X!=1.
% "Path literals must be connected", alias
% "The path/2 literals for time=T and time=T+1 cannot have edges ending and
% starting at different nodes"
:- path(e(X,N1),t(T)), path(e(N2,Y),t(TT)), TT=T+1, N1!=N2.
% "Every street must have been visited at least once before time T", alias:
% "It is not possible for edge/2 to exist between node pair (X,Y) and
% visited(X,Y) not to be true"
% and
% "visited(X,Y) is true if edge(X,Y) or the edge(Y,X) (or both) are the path"
visited(X,Y,T) :- time(T),path(e(X,Y),t(Tx)), Tx <= T.
visited(X,Y,T) :- time(T),path(e(Y,X),t(Tx)), Tx <= T.
:- edge(X,Y), not visited(X,Y,max_time).
% "The path must be a cycle, returning to node 1 at exactly max_time"
:- path(e(X,Y),t(max_time)), Y!=1.
% Compute cumulative cost of path
acc_cost(C,1) :- path(e(X,Y),t(1)),cost(edge(X,Y),C).
acc_cost(C,T) :- time(T),T>1,path(e(X,Y),t(T)),cost(edge(X,Y),Cx),Tp=T-1,acc_cost(Cp,Tp),C=Cp+Cx.
% ---
% Define the graph itself
% ---
% Nodes are street intersections, just labeled node(1) .. node(6).
% Note that this is different from using atoms as names as in
% node_1, node_2, ....
% What we are saying here is that "certain integers 1 ... 6 can appear
% as labels of nodes" or "integer 1 ... 6 have the attribute 'node'"
node(1..6).
% Directed edges are streets, linking the nodes, i.e. the intersections.
% If there is an edge A->B and an edge B->A then it's a two-way-street.
% If there is an edge A->B but no edge B->A then it's a one-way street.
% What we are saying here is that "certain tuples of integers (X,Y) can
% appear as labels of edges".
edge(1,(2;3;4)). edge(2,(4;5;6)). edge(3,(1;4;5)).
edge(4,(1;2)). edge(5,(3;4;6)). edge(6,(2;3;5)).
% Not made explicit is the fact that X and Y in edge(X,Y) must be labels
% of nodes. For good measure, we add an integrity constraint. Also,
% disallow reflexivity.
:- edge(X,Y), not node(X).
:- edge(X,Y), not node(Y).
:- edge(X,X).
% Driving down a street has a cost, so associate a cost with each edge.
% Let's be explicit in naming and use the "edge/2" predicate inside of the
% cost/2 predicate.
cost(edge(1,2),2). cost(edge(1,3),3). cost(edge(1,4),1).
cost(edge(2,4),2). cost(edge(2,5),2). cost(edge(2,6),4).
cost(edge(3,1),3). cost(edge(3,4),2). cost(edge(3,5),2).
cost(edge(4,1),1). cost(edge(4,2),2).
cost(edge(5,3),2). cost(edge(5,4),2). cost(edge(5,6),1).
cost(edge(6,2),4). cost(edge(6,3),3). cost(edge(6,5),1).
:- cost(edge(X,Y),C), not edge(X,Y).
:- edge(X,Y), not cost(edge(X,Y),_).
:- cost(edge(X,Y),C1), cost(edge(Y,X),C2), C1 != C2.
% ---
% Optimization
% ---
#minimize { C: acc_cost(C,max_time) }.
% ---
% Displaying part
% ---
#show path/2.
% #show acc_cost/2.
所以通过将 max_time 设置为 13，我们发现：
Solving...
Answer: 1
path(e(1,3),t(1)) path(e(3,1),t(2)) path(e(1,2),t(3))
path(e(2,5),t(4)) path(e(5,4),t(5)) path(e(4,2),t(6))
path(e(2,6),t(7)) path(e(6,3),t(8)) path(e(3,5),t(9))
path(e(5,6),t(10)) path(e(6,3),t(11)) path(e(3,4),t(12))
path(e(4,1),t(13))
Optimization: 30
OPTIMUM FOUND
这看起来如下：
不错。
灵感来自@David 的改变，我做到了，我们有 2 个答案！
%hamilltonian cycles
% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
cleaned(Y) :- cycle(X,Y).
cleaned(Y) :- cycle(X,Y), cleaned(X).
% Test
:- node(Y), not cleaned(Y).
% Nodes
%node(1..6).
%node(street1..street6).
node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
运行 以上
Solving...
Answer: 1
cycle(street1,street4) cycle(street2,street5) cycle(street3,street1) cycle(street4,street2) cycle(street5,street6) cycle(street6,street3)
Optimization: 12
Answer: 2
cycle(street1,street2) cycle(street2,street4) cycle(street3,street5) cycle(street4,street1) cycle(street5,street6) cycle(street6,street3)
Optimization: 11
OPTIMUM FOUND
上面第二个答案的图没有连接：
你好我是answer-set-programming. I have done a little prolog新来的！
我正在尝试解决这个问题，我相信它可以用 hamiltonian-cycle 解决，让我知道你的意见。如果您不熟悉 ASP，您可以访问此站点 [clingo 和 gringo][1]。您可以使用此命令 运行 终端中的文件 clingo name_of_the_file.lp 或 clingo name_of_the_file.lp4 我在 Ubuntu.
（这些是 .lp 或 .lp4 文件） 我阅读和理解的第一个代码是有 3 个结果的代码
% Generating part
% ---------------
% Cardinality constraint:
% For any ground fact cycle(X,Y) in the answer set:
% - there must be a corresponding edge(X,Y)
% - there must be exactly 1 of cycle(X,Y) for any X
% - there must be exactly 1 of cycle(X,Y) for any Y
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Testing part
% ------------
% It is a contradiction to that have a "node" that is not "reached"
:- node(Y), not reached(Y).
% Defining part
% -------------
% Nodes
node(1..6).
% (Directed) Edges
edge(1,(2;3;4)). edge(2,(4;5;6)). edge(3,(1;4;5)).
edge(4,(1;2)). edge(5,(3;4;6)). edge(6,(2;3;5)).
% Edge Costs cost(X,Y,Cost)
cost(1,2,2). cost(1,3,3). cost(1,4,1).
cost(2,4,2). cost(2,5,2). cost(2,6,4).
cost(3,1,3). cost(3,4,2). cost(3,5,2).
cost(4,1,1). cost(4,2,2).
cost(5,3,2). cost(5,4,2). cost(5,6,1).
cost(6,2,4). cost(6,3,3). cost(6,5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Displaying part
% ---------------
#show cycle/2.
我得到这个结果：
clingo version 5.4.0
Reading from cycle_hamilt.lp4
Solving...
Answer: 1
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,6) cycle(6,5) cycle(5,3)
Optimization: 13
Answer: 2
cycle(1,4) cycle(4,2) cycle(3,1) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 12
Answer: 3
cycle(1,2) cycle(4,1) cycle(3,4) cycle(2,5) cycle(6,3) cycle(5,6)
Optimization: 11
OPTIMUM FOUND
Models : 3
Optimum : yes
Optimization : 11
Calls : 1
Time : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.003s
我试着把这段代码转换成这样：
% Generate
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).
% Define
reached(Y) :- cycle(street1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).
% Nodes
%node(1..6).
node(street1..street6).
%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
这个看起来有点尴尬我得到这个结果：
clingo version 5.4.0
Reading from cleaning_street_names.lp4
Solving...
UNSATISFIABLE
Models : 0
Calls : 1
Time : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.003s
我试着按照你在评论中告诉我的那样更正它：
% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
reached(Y) :- cycle(1,Y).
reached(Y) :- cycle(X,Y), reached(X).
% Test
:- node(Y), not reached(Y).
% Nodes
%node(1..6).
node(street1..street6).
%node(street1).
%node(street2).
%node(street3).
%node(street4).
%node(street5).
%node(street6).
%node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
我得到了这个结果：
clingo version 5.4.0
Reading from cleaning_street_names.lp4
cleaning_street_names.lp4:30:6-22: info: interval undefined:
street1..street6
Solving...
Answer: 1
SATISFIABLE
Models : 1
Calls : 1
Time : 0.002s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.002s
（如果我输入 node(1..6)。结果是 UNSATISFIABLE）
问题出在这段代码中:
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).
您已将 1 替换为原子 street1。
但原始程序中的 1 不是 "street" 的 标识符（更像是 交叉点 ：节点是交叉路口，边是街道，因为从概念上讲，很难以单向方式从另一条街道到达一条街道，而且成本是固定的，是吗？ t it?)，而是一个 value：它是 cardinality constraint。正确的表达方式是：
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
表示：
对于答案集中的任何基本事实 cycle(X,Y)：
- 必须有对应的
edge(X,Y) - 对于任何
X，必须恰好有 - 对于任何
Y，必须恰好有
cycle(X,Y) 中的 1 个
cycle(X,Y) 中的 1 个
不知道clingo为什么不抗议？我还没试过 运行 这个。
"Hamiltonian"循环还是"Chinese Postman Problem"循环？
注意你写的；
The above problem can be modeled by representing the map of the city with a directed graph and the challenge is to visit all the edges (ie roads) at least once
这是完全正确的：边是 roads/streets，因此将名为 1..6 的节点重新标记为 street1..[=24= 在概念上是错误的（尽管在语法上是等效的） ].
给出的程序然后继续解决 Hamiltonian Path problem (every node visted exactly once) whereas it should solve the (comnplexity-wise simpler) Route Inspection/Chinese Postman 问题（每条边至少访问一次，最好只访问一次）。
原程序的约束
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
表示对哈密顿路径的约束（还不是哈密顿循环在同一节点开始和结束，只是一条路径）。对于任何一个节点，只有一条入边属于环，也只有一条出边属于环。因此，每个节点只被访问一次 => 哈密顿路径。
(不知道reached是不是多余的？如果不是，为什么不呢？)
原始问题的图表
- 节点是蓝色圆圈。
- 成本是白色椭圆。
- 循环的起始节点是 1。
- 箭头指示如何遍历边（按照惯例）
- 指出了一个解决方案。
更新：我在 ASP
的尝试这个 ASP 东西很棘手。我不确定如何正确表达问题。一个大问题是我们不知道要搜索多深，我发现攻击的唯一方法是 运行 具有连续更大 max_time 值的程序，直到 SATISFIABLE 是输出。问题是我们生成了 "exactly one literal at every time T" 到
1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).
然后根据约束检查这些 path/2 组文字。与 Prolog 不同，我们因此不能 "terminate when we reach node 1 and all edges have been visited"。这是如何正确完成的？我虽然关于 edge(1,1) 上的 "parking the path" 最后成本为 0，但这使程序变得混乱，我没有成功指定关于路径结构的全局约束，然后由 "good part"、一个 "hit node 1 one last time" 和一个 "tail part to be disregarded"。
% ===
% Attempt at the "Chinese Postman Problem" / "Route Inspection Problem"
% ===
% https://en.wikipedia.org/wiki/Route_inspection_problem
% Original statement:
%
% "Find a shortest closed path or circuit that visits every edge of an
% (connected) undirected graph."
%
% Here:
%
% "Find a closed path (cycle) starting from node 1 that visits every pair
% (X,Y) of nodes of a directed graph where that pair is connected by an edge
% (X->Y) or (Y->X) or both. Every edge has an associated
% cost. Find the cycle with the minimum cost."
%
% "max_time" is the length of the resulting path. Sadly, one has to manually
% reduce "max_time" in a stepwise fashion until the shortest path is found.
% How can that be done programmatically?
#const max_time=13.
time(1..max_time).
% ---
% Generating part
% ---
% For every time "T", there is exactly one path/2 literal indicating that
% the path element for time T goes via edge(X,Y).
1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).
% ---
% Defining part
% ---
% "Start at node 1", alias:
% "The path/2 literal for time=1 cannot be based on an edge/2 literal that
% does not start at node 1"
:- path(e(X,Y),t(1)), edge(X,Y), X!=1.
% "Path literals must be connected", alias
% "The path/2 literals for time=T and time=T+1 cannot have edges ending and
% starting at different nodes"
:- path(e(X,N1),t(T)), path(e(N2,Y),t(TT)), TT=T+1, N1!=N2.
% "Every street must have been visited at least once before time T", alias:
% "It is not possible for edge/2 to exist between node pair (X,Y) and
% visited(X,Y) not to be true"
% and
% "visited(X,Y) is true if edge(X,Y) or the edge(Y,X) (or both) are the path"
visited(X,Y,T) :- time(T),path(e(X,Y),t(Tx)), Tx <= T.
visited(X,Y,T) :- time(T),path(e(Y,X),t(Tx)), Tx <= T.
:- edge(X,Y), not visited(X,Y,max_time).
% "The path must be a cycle, returning to node 1 at exactly max_time"
:- path(e(X,Y),t(max_time)), Y!=1.
% Compute cumulative cost of path
acc_cost(C,1) :- path(e(X,Y),t(1)),cost(edge(X,Y),C).
acc_cost(C,T) :- time(T),T>1,path(e(X,Y),t(T)),cost(edge(X,Y),Cx),Tp=T-1,acc_cost(Cp,Tp),C=Cp+Cx.
% ---
% Define the graph itself
% ---
% Nodes are street intersections, just labeled node(1) .. node(6).
% Note that this is different from using atoms as names as in
% node_1, node_2, ....
% What we are saying here is that "certain integers 1 ... 6 can appear
% as labels of nodes" or "integer 1 ... 6 have the attribute 'node'"
node(1..6).
% Directed edges are streets, linking the nodes, i.e. the intersections.
% If there is an edge A->B and an edge B->A then it's a two-way-street.
% If there is an edge A->B but no edge B->A then it's a one-way street.
% What we are saying here is that "certain tuples of integers (X,Y) can
% appear as labels of edges".
edge(1,(2;3;4)). edge(2,(4;5;6)). edge(3,(1;4;5)).
edge(4,(1;2)). edge(5,(3;4;6)). edge(6,(2;3;5)).
% Not made explicit is the fact that X and Y in edge(X,Y) must be labels
% of nodes. For good measure, we add an integrity constraint. Also,
% disallow reflexivity.
:- edge(X,Y), not node(X).
:- edge(X,Y), not node(Y).
:- edge(X,X).
% Driving down a street has a cost, so associate a cost with each edge.
% Let's be explicit in naming and use the "edge/2" predicate inside of the
% cost/2 predicate.
cost(edge(1,2),2). cost(edge(1,3),3). cost(edge(1,4),1).
cost(edge(2,4),2). cost(edge(2,5),2). cost(edge(2,6),4).
cost(edge(3,1),3). cost(edge(3,4),2). cost(edge(3,5),2).
cost(edge(4,1),1). cost(edge(4,2),2).
cost(edge(5,3),2). cost(edge(5,4),2). cost(edge(5,6),1).
cost(edge(6,2),4). cost(edge(6,3),3). cost(edge(6,5),1).
:- cost(edge(X,Y),C), not edge(X,Y).
:- edge(X,Y), not cost(edge(X,Y),_).
:- cost(edge(X,Y),C1), cost(edge(Y,X),C2), C1 != C2.
% ---
% Optimization
% ---
#minimize { C: acc_cost(C,max_time) }.
% ---
% Displaying part
% ---
#show path/2.
% #show acc_cost/2.
所以通过将 max_time 设置为 13，我们发现：
Solving...
Answer: 1
path(e(1,3),t(1)) path(e(3,1),t(2)) path(e(1,2),t(3))
path(e(2,5),t(4)) path(e(5,4),t(5)) path(e(4,2),t(6))
path(e(2,6),t(7)) path(e(6,3),t(8)) path(e(3,5),t(9))
path(e(5,6),t(10)) path(e(6,3),t(11)) path(e(3,4),t(12))
path(e(4,1),t(13))
Optimization: 30
OPTIMUM FOUND
这看起来如下：
不错。
灵感来自@David 的改变，我做到了，我们有 2 个答案！
%hamilltonian cycles
% Generate
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
% Define
cleaned(Y) :- cycle(X,Y).
cleaned(Y) :- cycle(X,Y), cleaned(X).
% Test
:- node(Y), not cleaned(Y).
% Nodes
%node(1..6).
%node(street1..street6).
node(street1;street2;street3;street4;street5;street6).
% (Directed) Edges
edge(street1,(street2;street3;street4)).
edge(street2,(street4;street5;street6)).
edge(street3,(street1;street4;street5)).
edge(street4,(street1;street2)).
edge(street5,(street3;street4;street6)).
edge(street6,(street2;street3;street5)).
% Edge Costs
cost(street1,street2,2). cost(street1,street3,3). cost(street1,street4,1).
cost(street2,street4,2). cost(street2,street5,2). cost(street2,street6,4).
cost(street3,street1,3). cost(street3,street4,2). cost(street3,street5,2).
cost(street4,street1,1). cost(street4,street2,2).
cost(street5,street3,2). cost(street5,street4,2). cost(street5,street6,1).
cost(street6,street2,4). cost(street6,street3,3). cost(street6,street5,1).
% Optimize minimum cost and cycle
#minimize { C,X,Y : cycle(X,Y), cost(X,Y,C) }.
% Display
#show cycle/2.
运行 以上
Solving...
Answer: 1
cycle(street1,street4) cycle(street2,street5) cycle(street3,street1) cycle(street4,street2) cycle(street5,street6) cycle(street6,street3)
Optimization: 12
Answer: 2
cycle(street1,street2) cycle(street2,street4) cycle(street3,street5) cycle(street4,street1) cycle(street5,street6) cycle(street6,street3)
Optimization: 11
OPTIMUM FOUND
上面第二个答案的图没有连接：