ASP 中有向图的路由检查

Question

对于下面的多向图，我正在尝试编写一个至少访问所有边一次的程序。例如，在下图中，我正在寻找类似于“edge(1,2), edge(2,3), edge(3,1), edge(1,2), edge(2,4)”的结果, 边(4,5), 边(5,4), 边(4,3), 边(3,1)"

到目前为止，这是我的代码。它运行不正确，但我不知道如何修复 it.Could 请协助如何继续？欢迎任何建议或代码。

基本上，我相信我正在寻找欧拉循环的变体，其中边可以被访问不止一次。

edge(1,2). edge(2,3). edge(3,1).
edge(2,4). edge(4,3).
edge(4,5). edge(5,4).
    
#const s=1.
start(s).

time(1..20). % allow at most 20 time-steps

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

:- move(edge(X,Y),step(1)), edge(X,Y), X!=s. % start from s

:- move(edge(X,Y_1),step(T)), move(edge(Y_2,Y),step(TT)), TT=T+1, Y_1!=Y_2.

visited(X,Y,T) :- time(T),move(edge(X,Y),step(S)), S<T, T<=20.
visited(X,Y,T) :- time(T),move(edge(Y,X),step(S)), S<T, T<=20.

:- edge(X,Y), not visited(X,Y,20).

:- move(edge(X,Y),step(S)), S<=20, Y!=s. %ensures path is cycle (back to s)

#minimize { T : time(T) }. % here i try to get as many steps as possible out of the upper bound of 20 

#show move/2.

Answer 1

您的代码行有问题

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

这里的问题是你在每个时间步都强制移动，这意味着你的路径必须有 20 步，这对于没有正好 20 步的解决方案的问题实例来说可能会有问题。

还有你的线路

:- move(edge(X,Y),step(S)), S<=20, Y!=s.

是一个问题，因为它强制每一步都以 s 结束 - 因此代码无法满足。

您也是在搜索最小值还是最大值？您的代码说明最小值，您的评论说明最大值。

我稍微修改了你的代码，现在它似乎可以工作了。主要变化是引入了步数并从谓词 visited.

中删除了计时器

#const s=1.
start(s).
1 {endt(1..20)} 1. % guess end time
time(1..T) :- endt(T). 

1 { move(edge(X,Y),step(T)) : edge(X,Y) } 1 :- time(T).

:- move(edge(X,Y),step(1)), edge(X,Y), X!=S, start(S). % start from s
:- move(edge(X,Y_1),step(T)), move(edge(Y_2,Y),step(T+1)), Y_1!=Y_2.
:- move(edge(X,Y),step(S)), edge(X,Y), Y!=s, endt(S). % end from s

visited(X,Y) :- move(edge(X,Y),step(_)).
visited(X,Y) :- move(edge(Y,X),step(_)).

:- edge(X,Y), not visited(X,Y). % visit all edges

#minimize { T : endt(T) }. 
#show move/2.

输出：

Answer: 1
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,3),step(8)) move(edge(3,1),step(9))
Optimization: 9
OPTIMUM FOUND

对于 #maximize { T : endt(T) }.:

Answer: 1
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,3),step(8)) move(edge(3,1),step(9))
Optimization: -9
Answer: 2
move(edge(1,2),step(1)) move(edge(2,3),step(2)) move(edge(3,1),step(3)) move(edge(1,2),step(4)) move(edge(2,4),step(5)) move(edge(4,5),step(6)) move(edge(5,4),step(7)) move(edge(4,5),step(8)) move(edge(5,4),step(9)) move(edge(4,5),step(10)) move(edge(5,4),step(11)) move(edge(4,5),step(12)) move(edge(5,4),step(13)) move(edge(4,5),step(14)) move(edge(5,4),step(15)) move(edge(4,3),step(16)) move(edge(3,1),step(17)) move(edge(1,2),step(18)) move(edge(2,3),step(19)) move(edge(3,1),step(20))
Optimization: -20

ASP 中有向图的路由检查

Route Inspection of Directed Graph in ASP

graph-theory

logic-programming

answer-set-programming

euler-path