如何计算 Dijkstra 守卫在 Prolog 中对执行进行排序

Question

我没有在 Dijsktras“if fi”中找到 Prolog cut，因为他 says“否则将选择一个具有真正守卫的任意守卫列表来执行。”。所以他的构造不会选择第一个匹配项，就像 Prolog cut 会做的那样：

if Cond1 -> Action11, .., Action1n1
[] Cond2 -> Action21, .., Action2n2
...
[] Condm -> Actionm1, .., Actionmn2
if

“do od”构造中是否可能有 Prolog 削减，只要受保护列表的至少一个条件为真，它就会循环？或者在 Prolog 中实现它的其他一些方法，我假设循环可以转换为递归调用。那么我们如何在 Prolog 中对 q1、q2、q3、q4 进行排序：

do q1 > q2 -> q1,q2 := q2,q1
[] q2 > q3 -> q2,q3 := q3,q2
[] q3 > q4 -> q3,q4 := q4,q3
od

Prolog 程序将有多少个非确定性执行路径（即 Prolog 解决方案）用于输入 7,11,5,3 并且都提供相同的答案？

Answer 1

如果我们假设没有保护计算可以发散，我认为以下表达了与问题中的排序示例相同的计算：

dgsort([A,B,C,D],R):-
  ( A > B -> X1 = [1]    ; X1 = [] ),
  ( B > C -> X2 = [2|X1] ; X2 = X1 ),
  ( C > D -> X3 = [3|X2] ; X3 = X2 ),
  (   X3 = [] -> R = [A,B,C,D]
  ;   random_member( X, X3),
      (  X =:= 1 -> dgsort([B,A,C,D],R)
      ;  X =:= 2 -> dgsort([A,C,B,D],R)
      ;  X =:= 3 -> dgsort([A,B,D,C],R) )).

评论：“任意受保护列表与true守卫将被选择执行”和所有其他掉了，也就是选择的是承诺，我一直认为。因此，如果我必须实施它，我会产生所有分支的守卫，在一些超时间隔检查它们，一旦一个或多个成功，我会随机选择其中一个，杀死所有其余的，然后继续获胜者，冠军。即致力于它。无论如何，这是我的理解。（或者超时也应该是随机的？）

我还认为 do-od 结构通过相同的机制选择了真正的守卫。即“至少一个”，我们不在乎是哪个。如果我们假设所有守卫计算都终止了，我们可以执行所有这些计算，随机选择获胜者，然后继续其操作。这就是上面的代码在做什么。

要找出执行路径的数量，我们需要将 random_member 更改为 member，运行谓词通过 findall 并测量结果的长度名单：

dgsortn([A,B,C,D],R):-
  ( A > B -> X1 = [1]    ; X1 = [] ),
  ( B > C -> X2 = [2|X1] ; X2 = X1 ),
  ( C > D -> X3 = [3|X2] ; X3 = X2 ),
  (   X3 = [] -> R = [A,B,C,D]
  ;   member( X, X3),
      (  X =:= 1 -> dgsortn([B,A,C,D],R)
      ;  X =:= 2 -> dgsortn([A,C,B,D],R)
      ;  X =:= 3 -> dgsortn([A,B,D,C],R) )).

运行成功5次：

9 ?- dgsortn( [7,11,5,3], R).
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11].

我们还可以添加一个计数器来查看生成每个解决方案所采取的步骤数。

Answer 2

我直接解决了计数问题并提出了这个解决方案。它的缺点是否定为失败会重新评估条件。

sortloop([Q1,Q2,Q3,Q4], R) :- Q1 > Q2, sortloop([Q2,Q1,Q3,Q4], R).
sortloop([Q1,Q2,Q3,Q4], R) :- Q2 > Q3, sortloop([Q1,Q3,Q2,Q4], R).
sortloop([Q1,Q2,Q3,Q4], R) :- Q3 > Q4, sortloop([Q1,Q2,Q4,Q3], R).
sortloop([Q1,Q2,Q3,Q4], [Q1,Q2,Q3,Q4]) :- \+ Q1 > Q2, \+ Q2 > Q3, \+ Q3 > Q4.

但是显示有5条执行路径：

?- sortloop([7,11,5,3], R).
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
false.

但是我们可以改进条件只评估一次吗？我想到的是软剪辑 (*->)/2 因为动作列表不会中止：

sortloop2([Q1,Q2,Q3,Q4], R) :-
  ((Q1 > Q2, sortloop2([Q2,Q1,Q3,Q4], R);
    Q2 > Q3, sortloop2([Q1,Q3,Q2,Q4], R);
    Q3 > Q4, sortloop2([Q1,Q2,Q4,Q3], R)) *-> true; R=[Q1,Q2,Q3,Q4]).

软切割解决方案给出相同的结果：

?- sortloop2([7,11,5,3], R).
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
R = [3, 5, 7, 11] ;
false.

但是 none 的解决方案使用 Prolog cut 来替换 Dijkstra 守卫中条件和动作列表之间的箭头。情况有点复杂。

编辑 2021 年 2 月 12 日：
如果有人好奇这 5 条路径在 DAG 中的样子：

Answer 3

我想你可以这样做：

do([Q1,Q2,Q3,Q4], [swap(Q1,Q2)|P], S) :-
    Q1 > Q2,
    do([Q2,Q1,Q3,Q4], P, S).

do([Q1,Q2,Q3,Q4], [swap(Q2,Q3)|P], S) :-
    Q2 > Q3,
    do([Q1,Q3,Q2,Q4], P, S).

do([Q1,Q2,Q3,Q4], [swap(Q3,Q4)|P], S) :-
    Q3 > Q4,
    do([Q1,Q2,Q4,Q3], P, S).

do([Q1,Q2,Q3,Q4], [], [Q1,Q2,Q3,Q4]) :- % termination state
    Q1 =< Q2,
    Q2 =< Q3,
    Q3 =< Q4.

执行：

?- do([7,11,5,3],P,S).
P = [swap(11, 5), swap(7, 5), swap(11, 3), swap(7, 3), swap(5, 3)],
S = [3, 5, 7, 11] ;
P = [swap(11, 5), swap(11, 3), swap(7, 5), swap(7, 3), swap(5, 3)],
S = [3, 5, 7, 11] ;
P = [swap(11, 5), swap(11, 3), swap(5, 3), swap(7, 3), swap(7, 5)],
S = [3, 5, 7, 11] ;
P = [swap(5, 3), swap(11, 3), swap(7, 3), swap(11, 5), swap(7, 5)],
S = [3, 5, 7, 11] ;
P = [swap(5, 3), swap(11, 3), swap(11, 5), swap(7, 3), swap(7, 5)],
S = [3, 5, 7, 11] ;
false.

如何计算 Dijkstra 守卫在 Prolog 中对执行进行排序

How count Dijkstra guards sort executions in Prolog

sorting

prolog

counting

non-deterministic