2

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

在此处输入图像描述

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

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

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.
4

1 回答 1

2

您的代码存在问题

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
于 2022-01-08T21:01:40.013 回答