3

您好，我是新手。我过去做了一点！我正在尝试解决这个问题，我相信它可以用解决，让我知道你的意见。如果您不熟悉 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）

4

2 回答 2

1

问题出在这段代码中：

{ cycle(X,Y) : edge(X,Y) } = street1 :- node(X).
{ cycle(X,Y) : edge(X,Y) } = street1 :- node(Y).

您已将 1 替换为 atom 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)任何一个都必须正好有 1 个X
  • cycle(X,Y)任何一个都必须正好有 1 个Y

我不知道为什么clgo不抗议？我没有尝试运行它。

“汉密尔顿”循环还是“中国邮递员问题”循环？

注意你写；

上述问题可以通过用有向图表示城市地图来建模，挑战是至少访问所有边缘（即道路）一次

这是完全正确的：边缘是道路/街道，因此将称为 1..6 的节点重新标记为street1..在概念上是错误的（尽管在语法上等效） street6。

给定的程序然后继续解决哈密顿路径问题（每个节点都访问一次），而它应该解决（复杂性更简单的）路线检查/中国邮递员问题（每个边至少访问一次，最好恰好访问一次）。

原程序的约束

{ 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 并且所有边都已访问时终止”。这是如何正确完成的？我虽然关于“将路径停在edge(1,1)最后成本为 0”的问题，但这会使程序变得混乱，并且我没有成功指定关于路径结构的全局约束，然后它由一个“好的部分”组成，一个“最后一次命中节点 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

这看起来如下：

中国邮递员+优化

好的。

于 2020-02-08T10:41:15.657 回答
0

受到@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

上面第二个答案的图表未连接：

示例解决方案

于 2020-02-10T09:25:54.900 回答