您好，我是answer-set-programming的新手。我过去已经做了prolog了！
我正在尝试解决此问题，我相信可以通过hamiltonian-cycle解决，请告诉我您的意见。如果您不熟悉ASP，则可以访问此站点[clingo和gringo] [1]。您可以使用此命令clingo name_of_the_file.lp或我在Ubuntu中测试过的clingo name_of_the_file.lp4在终端中运行文件。
（这些是.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并不是“街道”的标识符（更像是一个交叉点：节点是交叉点，边缘是街道，因为从概念上讲，很难以单向方式以固定的方式从一条街道到达另一条街道，不是吗？），而是一个值：这是基数约束。正确的表达式是：
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = 1 :- node(Y).
表示：
对于答案集中的任何事实
cycle(X,Y)：必须有一个对应的
edge(X,Y)任何
cycle(X,Y)的X必须完全为1任何
cycle(X,Y)的Y必须完全为1我不知道为什么clingo不抗议？我没有尝试运行此。
“哈密尔顿”周期或“中国邮递员问题”周期？
请注意，您写的是：
上述问题可以通过表示城市地图来建模
有向图，挑战在于访问所有边缘（即
道路）至少一次
这是完全正确的：边缘是道路/街道，因此在概念上将标签1..6的节点重新标记为
street1 .. street6是错误的（尽管在语法上是等效的）。然后，给出的程序将继续解决Hamiltonian Path问题（每个节点访问正好一次），而它应解决（复杂度上更简单）的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。问题是我们通过以下方式生成可能的路径，即“每次T都有一个文字”1 { path(e(X,Y),t(T)) : edge(X,Y) } 1 :- time(T).
然后根据约束检查这些
path/2文字集。因此，与Prolog不同，我们不能“在到达节点1且已访问所有边缘时终止”。如何正确完成？我虽然将“停放路径”放在最终成本为0的edge(1,1)上，但这会使程序混乱，并且我没有成功指定关于路径结构的全局约束，该约束由一个“好部分”组成”，“最后一次命中节点1”和“要忽略的尾部”。% ===
% 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
如下所示：
真好