Prolog

Question

我正在尝试根据所有地点的出发和到达时间来计算我在旅行中花费的总时间。

我正在尝试使用此功能来计算我将等待下一次运输的时间：

time_out([(_,Hf1),(Hi2,Hf2)|R],To):-
   diff_t(Hi2,Hf1,To_I),
   time_out([(Hi2,Hf2)|R],To_R),
   To is To_R + To_I.

diff_t(Hi,Hf,D):-Hf>Hi, D is Hf - Hi.
diff_t(Hi,Hf,D):-Hf=<Hi,HCA is Hf + 2400, D is HCA - Hi.

我测试的时候:

?- time_out([(_,1300),(1400,1600)],T).
false.

为什么它不给我我想要的总时间？

Answer 1

time_out/2 谓词只有一个递归子句。基础条款在哪里？这个递归子句正在遍历列表。假设使用封闭列表调用谓词，您最终将使用空列表作为第一个参数调用谓词。由于没有与该目标统一的 head 子句，调用失败。

另请注意，您的子句不是尾递归的。 IE。在这种情况下，在 recursive 调用之后有一个目标。这意味着这个目标必须保存在堆栈中（对于每个递归调用），直到找到基本情况。这浪费了space（递归调用次数的线性un）。在这种情况下（通常情况下），将谓词转换为尾递归谓词的解决方案是对要计算的距离使用 accumulator。当您到达（缺少基本情况）时，累加器的值将是您正在计算的距离：

time_out(Stops, Distance) :-
    % the initial value of the accumulator is zero
    % as we're computing the sum of distances
    time_out(Stops, 0, Distance).

time_out([], Distance, Distance).
time_out([(_, End1), (Start2, End2)| Stops], Distance0, Distance) :- 
    diff_t(Start2, End1, Leg),
    Distance1 is Leg + Distance0,
    time_out([(Start2, End2)| Stops], Distance1, Distance).

但是这个定义是不正确的。你能发现问题吗？当列表包含单个开始-结束对时会发生什么？你能纠正这个定义吗？也许我们有 错误的 基本情况？

大多数 Prolog 系统提供 trace 功能，这通常有助于理解 Prolog 计算：

?- trace.
true.

[trace]  ?- time_out([(_,1300),(1400,1600)],T).
   Call: (7) time_out([ (_G2156, 1300), (1400, 1600)], _G2169) ? creep
   Call: (8) time_out([ (_G2156, 1300), (1400, 1600)], 0, _G2169) ? creep
   Call: (9) diff_t(1400, 1300, _G2261) ? creep
   Call: (10) 1300>1400 ? creep
   Fail: (10) 1300>1400 ? creep
   Redo: (9) diff_t(1400, 1300, _G2261) ? creep
   Call: (10) 1300=<1400 ? creep
   Exit: (10) 1300=<1400 ? creep
   Call: (10) _G2262 is 1300+2400 ? creep
   Exit: (10) 3700 is 1300+2400 ? creep
   Call: (10) _G2265 is 3700-1400 ? creep
   Exit: (10) 2300 is 3700-1400 ? creep
   Exit: (9) diff_t(1400, 1300, 2300) ? creep
   Call: (9) _G2268 is 2300+0 ? creep
   Exit: (9) 2300 is 2300+0 ? creep
   Call: (9) time_out([ (1400, 1600)], 2300, _G2169) ? creep
   Fail: (9) time_out([ (1400, 1600)], 2300, _G2169) ? creep
   Fail: (8) time_out([ (_G2156, 1300), (1400, 1600)], 0, _G2169) ? creep
   Fail: (7) time_out([ (_G2156, 1300), (1400, 1600)], _G2169) ? creep
false.

仔细观察通话 (9)。我会在明天之前为您找到解决此错误的方法。快乐黑客！

更新

既然 OP 找到了可行的解决方案，是时候解决这个问题了。例如，写成：

time_out([(_, End1)| Stops], Distance) :-
    % the initial value of the accumulator is zero
    % as we're computing the sum of distances
    time_out(Stops, End1, 0, Distance).

time_out([], _, Distance, Distance).
time_out([(Start2, End2)| Stops], End1, Distance0, Distance) :- 
    diff_t(Start2, End1, Leg),
    Distance1 is Leg + Distance0,
    time_out(Stops, End2, Distance1, Distance).

请注意，大多数 Prolog 系统都实现了一种称为 第一参数索引 的优化，它允许尝试可能能够解决当前目标的子句。这种优化通常通过考虑类型来实现，对于原子术语，在某些情况下，还考虑第一个参数（如果绑定）的值。 time_out/4 谓词的两个子句中的第一个参数是，对于第一个，atom []（空列表是 not 一个列表），第二个 list 包含一个或多个元素。因此，假设这个优化，每次调用这个谓词时都会选择正确的子句（当然，它的第一个参数被实例化），从而避免虚假的选择点。然而，相同的优化不能应用于您的解决方案，因为在您的 time_out/2 谓词的两个子句中，第一个参数是一个列表。

Answer 2

正如 Paulo 所说，递归需要一个基本子句：

time_out([_], 0).
time_out([(_, Hf1), (Hi2, Hf2)|R], To) :- 
              diff_t(Hi2, Hf1, To_I),
              time_out([(Hi2, Hf2)|R], To_R),
              To is To_R + To_I.

Prolog - 计算一次旅行的总时间

Prolog - Calculate the total time of a trip