4

I have written the following program, which calculates the longest non-decreasing sub-sequence of input array.

The sub-program to find the longest list from the list of lists is taken from stackoverflow (How do I find the longest list in a list of lists) itself. 

:- dynamic lns/2.
:- retractall(lns(_, _)).

lns([], []).
lns([X|_], [X]).
lns([X|Xs], [X, Y|Ls]) :-
    lns(Xs, [Y|Ls]),
    X < Y,
    asserta(lns([X|Xs], [X, Y|Ls])).
lns([_|Xs], [Y|Ls]) :-
    lns(Xs, [Y|Ls]).

% Find the longest list from the list of lists.
lengths([], []).
lengths([H|T], [LH|LengthsT]) :-
    length(H, LH),
    lengths(T, LengthsT).

lengthLongest(ListOfLists, Max) :-
    lengths(ListOfLists, Lengths),
    max_list(Lengths, Max).

longestList(ListOfLists, Longest) :-
    lengthLongest(ListOfLists, Len),
    member(Longest, ListOfLists),
    length(Longest, Len).

optimum_solution(List, Ans) :-
    setof(A, lns(List, A), P),
    longestList(P, Ans), 
    !.

I have used the Prolog dynamic database for memoization purpose. Though the program with database runs slower than the program without database. Below are the comparative times between two runs.

?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 53,397 inferences, 0.088 CPU in 0.088 seconds (100% CPU, 609577 Lips)
Ans = [0, 2, 6, 9]. %% With database

?- time(optimum_solution([0, 8, 4, 12, 2, 10, 6, 14, 1, 9], Ans)).
% 4,097 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 2322004 Lips)
Ans = [0, 2, 6, 9]. %% Without database. commented out the database usage.

I would like to know if I am using the dynamic database correctly. Thanks!

4

4 に答える 4

2

問題は、リスト構築サブシーケンスをトラバースしているとき、最後の値が手元にある値よりも小さい前のサブシーケンスのみを考慮する必要があることです。問題は、Prolog の最初の引数のインデックス作成が、より小さいチェックではなく、等しいチェックを行っていることです。そのため、Prolog は のストア全体をトラバースlns/2し、最初のパラメーターを値で統一して、それが小さいかどうかを確認してからバックトラックして次のパラメーターを取得する必要があります。

于 2016-02-05T17:32:01.207 に答える
1

TL;DR:この回答では、 に基づく非常に一般的なアプローチを実装しています。

:- use_module(ライブラリ(clpfd) )。

list_nondecreising_subseq(Zs, Xs) :-
   append (_, Suffix, Zs),
    same_length (Suffix, Xs),
    chain (Xs, #=<),
   list_subseq(Zs, Xs)。%別名subset/2 by @gusbro

SWI-Prolog 7.3.16 を使用したサンプル クエリ:

?- list_nondecreaging_subseq([0,8,4,12,2,10,6,14,1,9], Zs)。
   Zs = [0,8,12,14]
; Zs = [0,8,10,14]
; Zs = [0,4,12,14]
; Zs = [0,4,10,14]
; Zs = [0,4,6,14]
; Zs = [0,4,6,9]
; Zs = [0,2,10,14]
; Zs = [0,2,6,14]
; Zs = [0,2,6,9]
; Zs = [0,8,12]
...
; Zs = [9]
; Zs = []
; 間違い。

回答シーケンスの特定の順序に注意してください! 最も長いリストが最初に来て、少し小さいリストが続きます...シングルトンリストと空のリストに至るまで。

于 2016-02-05T20:21:47.233 に答える
0

どんどん良くなる！この回答では、この以前の回答で提示された — のドロップlist_long_nondecreasing_subseq__NEW/2イン置換を提示します。list_long_nondecreasing_subseq/2

本題に切り込んで を定義しましょうlist_long_nondecreasing_subseq__NEW/2!

:- use_module([ライブラリ(clpfd)、ライブラリ(リスト)、ライブラリ(ランダム)、ライブラリ(間)])。

list_long_nondecreaging_subseq __NEW (Zs, Xs) :-
   最小(最小、Zs)、
   append(プレフィックス、サフィックス、Zs)、
   same_length(サフィックス、X)、
   zs_skiped_subseq_taken0 ( Zs、Prefix、 Xs、Min)。

zs_ skipped_ subseq_taken0([], _, [], _)。
zs_ skipped_ subseq_taken0([E|Es], Ps, [E|Xs], E0) :-
   E0 #=< E,
   zs_skiped_subseq_taken0 ( Es、Ps、Xs、E)。
zs_ skipped_ subseq_taken0([E|Es], [_|Ps] , Xs, E0) :-
   zs_ skipped_ subseq_taken0_min0_max0(Es、Ps、Xs、E0、E、E)。

zs_ skipped_ subseq_taken0_min0_max0([], _, [], E0, _, Max) :-
   最大 #< E0。
zs_ skipped_ subseq_taken0_min0_max0([E|Es], Ps , [E|Xs], E0, Min, Max) :-
   E0 #=< E,
   E0 #> 最小 #\/ 最小 #> E,
   E0 #> 最大 #\/ 最大 #> E,
   zs_skiped_subseq_taken0 ( Es、Ps、 Xs、E)。
zs_ skipped_ subseq_taken0_min0_max0([E|Es], [_|Ps], Xs, E0, Min0, Max0) :-
   最小 #= 分(Min0,E),
   最大 #= max(Max0,E),
   zs_skiped_subseq_taken0_min0_max0 ( Es、Ps、 Xs、E0、最小、最大)。

それで...以前と同じように機能しますか？いくつかのテストを実行して、回答シーケンスを比較してみましょう。

| | ?- setrand(random(29251,13760,3736,425005073)),
     間(7, 23, N),
     nl、
     書き込み(n=N)、
     書きます（' '）、
     長さ(Zs, N),
     間(1, 10, _),
     maplist(ランダム(1,N), Zs),
     findall(Xs1, list_long_nondecreising_subseq( Zs,Xs1), Xss1),
     findall(Xs2, list_long_nondecreising_subseq__NEW(Zs,Xs2), Xss2),
     ( Xss1 == Xss2 -> true ; throw(up) ),
     長さ(Xss2、L)、
     書き込み({L})、
     間違い。

n=7 {3}{8}{3}{7}{2}{5}{4}{4}{8}{4}
n=8 {9}{9}{9}{8}{4}{4}{7}{5}{6}{9}
n=9 {9}{8}{5}{7}{10}{7}{9}{4}{5}{4}
n=10 {7}{12}{7}{14}{13}{19}{13}{17}{10}{7}
n=11 {14}{17}{7}{9}{17}{21}{14}{10}{10}{21}
n=12 {25}{18}{20}{10}{32}{35}{7}{30}{15}{11}
n=13 {37}{19}{18}{22}{20}{14}{10}{11}{8}{14}
n=14 {27}{9}{18}{10}{20}{29}{69}{28}{10}{33}
n=15 {17}{24}{13}{26}{32}{14}{22}{28}{32}{41}
n=16 {41}{55}{35}{73}{44}{22}{46}{47}{26}{23}
n=17 {54}{43}{38}{110}{50}{33}{48}{64}{33}{56}
n=18 {172}{29}{79}{36}{32}{99}{55}{48}{83}{37}
n=19 {225}{8​​3}{119}{61}{27}{67}{48}{65}{90}{96}
n=20 {58}{121}{206}{169}{111}{66}{233}{57}{110}{146}
n=21 {44}{108}{89}{99}{149}{148}{92}{76}{53}{47}
n=22 {107}{137}{221}{79}{172}{156}{184}{78}{162}{112}
n=23 {163}{62}{76}{192}{133}{372}{101}{290}{84}{378}
番号

すべての回答シーケンスはまったく同じでした。…では、ランタイムはどうですか？

SICStus Prolog 4.3.2 を使用してさらにクエリを実行し、回答を整形してみましょう!

?- メンバー(N, [15,20,25,30,35,40,45,50]),
   長さ(Zs, N),
   _NN #= N*N,
   maplist(ランダム(1,_NN), Zs),
   call_time(once(list_long_nondecreising_subseq( Zs, Xs )), T1),
   call_time(once(list_long_nondecreising_subseq__NEW(Zs,_Xs2)), T2),
   Xs == _Xs2、
   長さ(Xs,L)。
N = 15、L = 4、T1 = 20、T2 = 0、Zs = [224,150,161,104,134,43,9,111,76,125,50,68,202,178,148]、Xs = [104,111,125,202];
N = 20、L = 6、T1 = 60、T2 = 10、Zs = [71,203,332,366,350,19,241,88,370,100,288,199,235,343,181,90,63,149,215,285]、Xs = [71,88,100,193,23]5、
n = 25、l = 7、t1 = 210、t2 = 20、zs = [62,411,250,222,141,292,276,94,548,322,13,317,68,488,137,33,80,167,41,475,475,429,27777777777,41,48,137,33,80,167
N = 30, L = 10, T1 = 870, T2 = 30, Zs = [67,175,818,741,669,312,99,23,478,696,63,793,280,364,677,254,530,216,291,660,218,664,476,556,678,626,75,834,578,850], Xs = [67,175,312,478,530,660,664,678,834,850] ;
n = 35、l = 7、t1 = 960、t2 = 120、zs = [675,763,1141,1070,299,650,1061,1184,512,905,139,719,84444,8,1186,1006,400,690,29,791,180880880808080808080808080808808808808808808808808808808808808808808808808808880880880880880880880880880880880880880880888088808808808808808808808808808808808808808808880 ,431,416,357,1139,636,591]、Xs = [299,650,719,844,1006,1180,1220];
N = 40、L = 9、T1 = 5400、T2 = 470、Z = [958,1047,132,1381,22,991,701,1548,470,1281,358,32,605,1270,692,1020,350,794,1451,11,985 ,1196,504,1367,618,1064,961,463,736,907,1103,719,1385,1026,935,489,1053,380,637,51]、X = [132,470,605,692,794,985,1196,1367,1385];
N = 45、L = 10、T1 = 16570、T2 = 1580、Zs = [1452,171,442,1751,160,1046,470,450,1245,971,1574,901,1613,1214,1849,1805,341,34 ,1923,698,156,1696,717,1708,1814,1548,463,421,1584,190,1195,1563,1772,1639,712,693,1848,1531,250,783,1654,1732,1333,717,13]、Xs =22]、 [171,442,1046,1245,1574,1613,1696,1708,1814,1848];
N = 50、L = 11、T1 = 17800、T2 = 1360、Z = [2478,2011,2411,1127,1719,1286,1081,2042,1166,86,355,894,190,7,1973,1912,753,1411,1082 ,70,2142,417,1609,1649,2329,2477,1324,37,1781,1897,2415,1018,183,2422,1619,1446,1461,271,56,2399,1681,267,977,826,2145,2318 ,2391,137,55,1995]、Xs = [86,355,894,1411,1609,1649,1781,1897,2145,2318,2391];
間違い。

もちろん、この回答で示されているバロック様式のアプローチは、 を決定するための「本格的な」適切なアルゴリズムと競合することはできません— それでも、10 倍のスピードアップを得ることは常に気分が良いです :)

于 2016-02-08T06:21:27.850 に答える