最大サブアレイ（Kadaneのアルゴリズム） - テイル再帰

Question

私はKadane's AlgorithmをPrologに実装しようとしています。 要件の1つは、テールコール（再帰）です。

私は多くの可能性を試しましたが、成功しませんでした。

max_sum(L, S) :- 
    S is 0, 
    H is 0, 
    max_sum(L, H, S). 

max_sum([], S, S). 
max_sum([X | L], H, S) :- 
    ( H + X < 0 -> NewH is 0; NewH is H + X), 
    ( S < H + X -> NewS is NewH; NewS is S), 
    length(L, N), 
    ( N < 1 -> max_sum(L, NewS, NewS); max_sum(L, NewH, NewS)). 

NewH、ニュースが（？我々は正しいPrologで値の2倍を割り当てるカント）の一時値です： はここに私のコードです。 私はヒントを求めることができますか？

編集：コール（11）で

[trace] ?- max_sum([1, 2, 3], S). 
    Call: (7) max_sum([1, 2, 3], _G8907) ? creep 
    Call: (8) _G8907 is 0 ? creep 
    Exit: (8) 0 is 0 ? creep 
    Call: (8) _G8991 is 0 ? creep 
    Exit: (8) 0 is 0 ? creep 
    Call: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) 0+1<0 ? creep 
    Fail: (9) 0+1<0 ? creep 
    Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) _G8994 is 0+1 ? creep 
    Exit: (9) 1 is 0+1 ? creep 
    Call: (9) 0<0+1 ? creep 
    Exit: (9) 0<0+1 ? creep 
    Call: (9) _G8997 is 1 ? creep 
    Exit: (9) 1 is 1 ? creep 
    Call: (9) length([2, 3], _G8998) ? creep 
    Exit: (9) length([2, 3], 2) ? creep 
    Call: (9) 2<1 ? creep 
    Fail: (9) 2<1 ? creep 
    Redo: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Call: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) 1+2<0 ? creep 
    Fail: (10) 1+2<0 ? creep 
    Redo: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) _G9000 is 1+2 ? creep 
    Exit: (10) 3 is 1+2 ? creep 
    Call: (10) 1<1+2 ? creep 
    Exit: (10) 1<1+2 ? creep 
    Call: (10) _G9003 is 3 ? creep 
    Exit: (10) 3 is 3 ? creep 
    Call: (10) length([3], _G9004) ? creep 
    Exit: (10) length([3], 1) ? creep 
    Call: (10) 1<1 ? creep 
    Fail: (10) 1<1 ? creep 
    Redo: (9) max_sum([2, 3], 1, 1) ? creep 
    Call: (10) max_sum([3], 3, 3) ? creep 
    Call: (11) 3+3<0 ? creep 
    Fail: (11) 3+3<0 ? creep 
    Redo: (10) max_sum([3], 3, 3) ? creep 
    Call: (11) _G9006 is 3+3 ? creep 
    Exit: (11) 6 is 3+3 ? creep 
    Call: (11) 3<3+3 ? creep 
    Exit: (11) 3<3+3 ? creep 
    Call: (11) _G9009 is 6 ? creep 
    Exit: (11) 6 is 6 ? creep 
    Call: (11) length([], _G9010) ? creep 
    Exit: (11) length([], 0) ? creep 
    Call: (11) 0<1 ? creep 
    Exit: (11) 0<1 ? creep 
    Call: (11) max_sum([], 6, 6) ? creep 
    Exit: (11) max_sum([], 6, 6) ? creep 
    Exit: (10) max_sum([3], 3, 3) ? creep 
    Exit: (9) max_sum([2, 3], 1, 1) ? creep 
    Exit: (8) max_sum([1, 2, 3], 0, 0) ? creep 
    Exit: (7) max_sum([1, 2, 3], 0) ? creep 

私はこの簡単な例から（6）良い結果を持っています。この時点で関数を終了せずに終了するにはどうすればよいですか？それは私の問題です。このコードから

結果は、S = 6

最終編集（作業コード）、S = 0ではない：

max_sum(L, S) :- 
    max_sum(L, 0, 0, S). 

max_sum([], _, S, S). 
max_sum([X | L], H, F, S) :- 
    NewH is max(0, H + X), 
    (F < H + X -> NewF is NewH; NewF is F), 
    max_sum(L, NewH, NewF, S). 

：

• S - 最終結果、
• F - maximum_so_far、
• H - maximum_ending_here、
• リストのXヘッド、
• リスト、
• NewH、NewF - temp値。

助けてくれてありがとう:)

Answer 1

Iは@repeatによって提案solutionのわずかに変更されたバージョンを提案する：

:- use_module(library(clpfd)). 

zs_max([Z|Zs], MSF) :- 
    zs_max_(Zs, Z, Z, MSF). 

zs_max_([], _, MSF, MSF). 
zs_max_([Z|Zs], MEH0, MSF0, MSF) :- 
    max(Z, MEH0+Z) #= MEH1, 
    max(MSF0, MEH1) #= MSF1, 
    zs_max_(Zs, MEH1, MSF1, MSF). 

まず、同じ結果をもたらす原solutionからのサンプルクエリ：

?- zs_max([-2,1,-3,4,-1,2,1,-5,4], Max). 
Max = 6 
    ?- zs_max([-2,3,4,-5,8,-12,100,-101,7], Max). 
Max = 100 

をしかし、このバージョンはより一般的です。つまり、任意の値で動作します（solutionへのコメントの@falseで示唆されているように）。これは、従って、次のクエリは異なる結果をもたらす代わりに0のリストの最初の要素の値で開始することによって達成される：

?- zs_max([-2,-3,-4], X). 
X = -2 
    ?- zs_maxmum([-2,-3,-4], X). 
X = 0 

もう一つの違いは、空のリストが解を持たないことである。

?- zs_max([], X). 
no 
    ?- zs_maxmum([], X). 
X = 0 

空リストにはサブリストがないため、最大値を選択するサブリストの合計がないので、この動作はより合理的だと思います。ただし、必要に応じて、空のリストの特殊なケースを簡単に追加することができます。

zs_max([], replaceThisWithAReasonableValue). 

Answer 2

は、標準的な方法は、再帰が停止したときに統一されます出力パラメータを、追加することです。ウィキペディアに記載されている両方のバージョンは、すべてのテストを必要としない、または長さ/ 2の計算：

max_sum(L, S) :- 
    max_sum(L, 0, 0, S). 

max_sum([], _, S, S). 
... 

のようなものは次に、あなたのコードは、必要以上の方法より複雑です。 インスタンスMax_ending_here is max(0, H + X),と末尾再帰呼び出しのために使用することができます（単に計算を残し、それを簡素化するようにしてください。

Answer 3

1. この質問は、実際には、 「Finding the maximum sublist in Prolog」の複製である。そこ

2. それは重複としてフラグを設定することはできませんので、恵みが、それのために提供されている。

3. 私はそれがclpfdに基づいており、SWI-Prologので実行され、私のprevious solution —を使用して提案します。