3

Prolog でKadane のアルゴリズムを実装しようとしています。要件の 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、NewS は一時的な値です (Prolog で値を 2 回割り当てることはできませんよね?)。ヒントをお願いできますか？

編集：

[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

Call(11) では、この単純な例から良い結果 (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 - リストの先頭、
  • L - リスト、
  • NewH、NewF - 一時値。

助けてくれてありがとう ：）

4

3 に答える 3

3

  1. 実際、この質問は「Prolog で最大のサブリストを見つける」の複製です。

  2. 報奨金が提供されているため、重複としてフラグを立てることはできません。

  3. 以前のソリューションを使用することを提案します— これはに基づいており、SWI-Prolog で実行されます。

于 2016-04-01T15:06:59.710 に答える
1

標準的な方法は、再帰が停止したときに統合される出力パラメーターを追加することです。何かのようなもの

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

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

次に、コードは必要以上に複雑になります。ウィキペディアにリストされている両方のバージョンは、テストや長さ/2の計算を必要としません。計算だけを残して単純化してみてください（たとえばMax_ending_here is max(0, H + X),、末尾の再帰呼び出しを使用できます。

于 2016-03-30T15:55:57.003 に答える