如何在Prolog中解決這個難題？

Question

我想解決一個Prolog中的一個難題，它涉及到一個數字的平方（數字列表），並返回從上到下依次排列的數字的最大組合列表。每次移動必須向下，向右或向左移動。

我一直在試圖做一段時間，現在有沒有人有我可以開始的地方？

例如，在板

[[0, 2, 1, 0], 
    [0, 1, 1, 0], 
    [0,10,20,30]] 

最好行動將是[1, 2, 3]爲33分。

Answer 1

因此，這裏是你如何能做到這一點。我知道這有點羅嗦，這可能是因爲我在Prolog中不是很流利......

% Lookup a value in a list by it's index. 
% this should be built into prolog? 
at(0, [H|_], H). 
at(N, [_|T], X) :- 
    N > 0, 
    N1 is N - 1, 
    at(N1, T, X). 

% like Haskell's maximumBy; takes a predicate, a 
% list and an initial maximum value, finds the 
% maximum value in a list 
maxby(_, [], M, M). 
maxby(P, [H|T], M0, M) :- 
    call(P, H, M0, M1), 
    maxby(P, T, M1, M). 

% which of two paths has the bigger score? 
maxval(path(C, I), path(C1, _), path(C, I)) :- C >= C1. 
maxval(path(C0, _), path(C, I), path(C, I)) :- C0 < C. 

% generate N empty paths as a starting value for 
% our search 
initpaths(N, Ps) :- 
    findall(path(0, []), 
      between(0, N, _), 
     Ps). 

% given the known best paths to all indexes in the previous 
% line and and index I in the current line, select the best 
% path leading to I. 
select(Ps, I, N, P) :- 
    I0 is I-1, 
    I1 is I+1, 
    select(Ps, I0, N, path(-1, []), P0), 
    select(Ps, I, N, P0, P1), 
    select(Ps, I1, N, P1, P). 

% given the known best paths to the previous line (Ps), 
% an index I and a preliminary choice P0, select the path 
% leading to the index I (in the previous line) if I is within 
% the range 0..N and its score is greater than the preliminary 
% choice. Stay with the latter otherwise. 
select(_, I, _, P0, P0) :- I < 0. 
select(_, I, N, P0, P0) :- I > N. 
select(Ps, I, _, P0, P) :- 
    at(I, Ps, P1), 
    maxby(maxval, [P0], P1, P). 

% given the known best paths to the previous line (P1), 
% and a Row, which is the current line, extend P1 to a 
% new list of paths P indicating the best paths to the 
% current line. 
update(P1, P, Row, N) :- 
    findall(path(C, [X|Is]), 
      (between(0, N, X) 
      , select(P1, X, N, path(C0, Is)) 
      , at(X, Row, C1) 
      , C is C0 + C1), 
     P). 

% solve the puzzle by starting with a list of empty paths 
% and updating it as long as there are still more rows in 
% the square. 
solve(Rows, Score, Path) :- 
    Rows = [R|_], 
    length(R, N0), 
    N is N0 - 1, 
    initpaths(N, IP), 
    solve(N, Rows, IP, Score, Path). 
solve(_, [], P, Score, Path) :- 
    maxby(maxval, P, path(-1, []), path(Score, Is0)), 
    reverse(Is0, Path). 
solve(N, [R|Rows], P0, Score, Path) :- 
    update(P0, P1, R, N), 
    solve(N, Rows, P1, Score, Path). 

我們試試嗎？這裏是你的例子：

?- solve([[0,2,1,0], [0,1,1,0], [0,10,20,30]], Score, Path). 
Score = 33, 
Path = [1, 2, 3] ; 
false. 

?- solve([[0,1,1], [0,2,1], [10,0,0]], Score, Path). 
Score = 13, 
Path = [1, 1, 0] ; 
false. 

Answer 2

我的序言有點不穩定。實際上我所記得的關於序言的一點是它是聲明性的。

這裏有一些haskell代碼來查找最大路徑的值。尋找蹤跡應該是一個簡單的下一步，但是我想象的代碼更復雜一點。我想一個非常優雅的跟蹤解決方案將使用單子。

maxValue :: [ [ Int ] ] -> Int 
maxValue p = maximum $ maxValueHelper p 
maxValueHelper :: [ [ Int ] ] -> [ Int ] 
maxValueHelper [ row ] = row 
maxValueHelper (row : restOfRows) = combine row (maxValueHelper restOfRows) 
combine :: [ Int ] -> [ Int ]-> [ Int ] 
combine [ x ] [ y ] = [ x + y ] 
combine (x1 : x2 : lx) (y1 : y2 : ly) = 
    let (z2 : lz) = combine (x2 : lx) (y2 : ly) 
    in 
    (max (x1 + y1) (x1 + y2) : max (x2 + y1) z2 : lz) 

main :: IO() 
main = print $ maxValue [[0,2,1,0], [0,1,1,0], [0,10,20,30]] 

Answer 3

?- best_path_score([[0, 2, 1, 0],[0, 1, 1, 0],[0,10,20,30]], P, S). 
P = [1, 2, 3], 
S = 33. 

這一定義

best_path_score(Rs, BestPath, BestScore) :- 
    aggregate_all(max(Score, Path), a_path(Rs, Path, Score), max(BestScore, BestPath)). 

a_path([R|Rs], [P|Ps], Score) :- 
    nth0(P, R, S0), 
    a_path(Rs, P, Ps, S), 
    Score is S0 + S. 

a_path([], _, [], 0). 
a_path([R|Rs], P, [Q|Qs], T) :- 
    (Q is P - 1 ; Q is P ; Q is P + 1), 
    nth0(Q, R, S0), 
    a_path(Rs, Q, Qs, S), 
    T is S0 + S.