我是否以正确的方式使用序言?

发布于 01-19 21:31 字数 3637 浏览 3 评论 0原文

我们的教授给了我们以下练习:使用遗传算法来解决N-Queen问题(但n = 4)。

我的程序有效并解决了这个问题,但是我觉得自己在作弊,就像我以命令性的方式使用序言而不是声明性。 以下是我的代码:

use_module(library(lists)).
/*
 * You can query with: genetic_four_queens(R).
 * Or alternatively if you want to set the initial population manually you can do:
 * genetic_four_queens([[1,2,3,4],[2,3,4,1]],R)
 * 
 * Note that each possible solution is represented by a list of size 4: [A,B,C,D]
 * where A =\= B =\= C =\= D
 * */
genetic_four_queens(Result):-
    genetic_four_queens([[1,2,3,4],[4,3,2,1]],Result).

genetic_four_queens(Population, Result):-
    write('Population: '),
    writeln(Population),
    evaluate(Population,Scores),
    min_list(Scores,Min),
    Min =\= 0,
    sum_list(Scores,Tot),
  selection(Population,Tot,S),
    proper_length(S,Len),
    (   Len =\= 0 ->  
        Survivors = S
      ;   
        Survivors = Population
    ),
    write('Survivors: '),writeln(Survivors),
    crossover(Survivors, Cross),
    write('Reproduction:'),writeln(Cross),
    mutation(Cross, Mutants),
    list_to_set(Mutants, NewPopulation),
    genetic_four_queens(NewPopulation,Result).

genetic_four_queens(Population, Result):-
    evaluate(Population,Scores),
    min_list(Scores,Min),
    Min = 0,
    nth1(I,Scores,0),
    nth1(I,Population,Result),
  write('Solution: '),writeln(Result).

evaluate([],[]).
evaluate([QList|List], [R|Res]):-
    fitness(QList, F), % List is an array of arrays
  evaluate(List, Res),
    R is F.

selection([],_,[]).
selection([Q|List],Tot, Res):-
    fitness(Q,F),
    P is 1 - F/Tot,
    (maybe(P) ->
      Res = [R|Tail],
      R = Q,
      selection(List, Tot, Tail)
      ;   
      selection(List, Tot, Res)
    ).
crossover([],[]).
crossover([Q|List], Res) :-
    try_crossing(Q,List,Crossings),
    crossover(List, R2),
    union([Q|R2],Crossings,Res).
    
try_crossing(_,[],[]).
try_crossing(Q,[C|List],Res):-
    cross(Q,C,C1,C2),
%    Res = [C,C1,C2 | Tail],
    try_crossing(Q,List, Tail),
    union([C1,C2],Tail,Res).
try_crossing(Q,[C|List],Res):-
    \+ cross(Q,C,_,_),
%    Res = [C,C1,C2 | Tail],
    try_crossing(Q,List, Tail),
    Res=Tail.    

cross(Q,C, R1,R2) :-
    [Q1,Q2|Q_tail] = Q,
    [C1,C2,C3,C4] = C,
    Q1 =\= C3,
    Q1 =\= C4,
    Q2 =\= C3,
    Q2 =\= C4,
    R1 = [Q1,Q2,C3,C4],
    R2 = [C1,C2|Q_tail].

mutation([],[]).
mutation([Q|QList], [Q,M|RList]):-
    proper_length(Q,L),
    random_between(1,L,Rand1),
    random_between(1,L,Rand2),
    permute(Q,Rand1,Rand2,M),
    mutation(QList,RList).

permute(Q,X,Y,M):-
    nth1(X,Q, Ex),
    nth1(Y,Q, Ey),
    replace(Q,Y,Ex,M1),
    replace(M1,X,Ey,M).

replace([],_,_,[]).
replace([_|List],Index,Element,[N|NewList]):-
    Index = 1,
    N = Element,
    I is Index-1,
    replace(List,I,Element,NewList).

replace([L|List],Index,Element,[N|NewList]):-
    Index =\= 1,
    N = L,
    I is Index-1,
    replace(List,I,Element,NewList).

fitness([], 0).
fitness([Q|Qlist], Res) :-
    collisions(Q, Qlist, 1, Collisions),
    fitness(Qlist, R2),
    Res is R2 + Collisions.

collisions(_,[], _, 0).
collisions(Q,[Q1|Qlist],Xdist,Result) :-
  Q =\= Q1, %not on the same row  
  Test is abs(Q1-Q),
  Test =\= Xdist, %it means non diagonal conflict
  Xdist1 is Xdist + 1,
  collisions(Q,Qlist,Xdist1, R2),
    Result is R2.

collisions(Q,[Q1|Qlist],Xdist,Result) :-
  Q =\= Q1, %not on the same row  
  Test is abs(Q1-Q),
  Test = Xdist, %it means diagonal conflict
  Xdist1 is Xdist + 1,
  collisions(Q,Qlist,Xdist1, R2),
    Result is R2 + 1.

特别是我想指出的是主要功能genetic_four_queens(人口,结果),在构建单个功能评估,选择,繁殖和突变之后,我只是使用它们,例如它们以某种方式是函数感到势在必行。

这是对的吗?

Our professor gave us the following excercise: create a prolog program using a genetic algorithm to solve the N-Queen problem (but N=4).

My program works and solves the issue, but I feel like I'm cheating, like if I'm using a prolog in an imperative manner and not declarative.
Following is my code:

use_module(library(lists)).
/*
 * You can query with: genetic_four_queens(R).
 * Or alternatively if you want to set the initial population manually you can do:
 * genetic_four_queens([[1,2,3,4],[2,3,4,1]],R)
 * 
 * Note that each possible solution is represented by a list of size 4: [A,B,C,D]
 * where A =\= B =\= C =\= D
 * */
genetic_four_queens(Result):-
    genetic_four_queens([[1,2,3,4],[4,3,2,1]],Result).

genetic_four_queens(Population, Result):-
    write('Population: '),
    writeln(Population),
    evaluate(Population,Scores),
    min_list(Scores,Min),
    Min =\= 0,
    sum_list(Scores,Tot),
  selection(Population,Tot,S),
    proper_length(S,Len),
    (   Len =\= 0 ->  
        Survivors = S
      ;   
        Survivors = Population
    ),
    write('Survivors: '),writeln(Survivors),
    crossover(Survivors, Cross),
    write('Reproduction:'),writeln(Cross),
    mutation(Cross, Mutants),
    list_to_set(Mutants, NewPopulation),
    genetic_four_queens(NewPopulation,Result).

genetic_four_queens(Population, Result):-
    evaluate(Population,Scores),
    min_list(Scores,Min),
    Min = 0,
    nth1(I,Scores,0),
    nth1(I,Population,Result),
  write('Solution: '),writeln(Result).

evaluate([],[]).
evaluate([QList|List], [R|Res]):-
    fitness(QList, F), % List is an array of arrays
  evaluate(List, Res),
    R is F.

selection([],_,[]).
selection([Q|List],Tot, Res):-
    fitness(Q,F),
    P is 1 - F/Tot,
    (maybe(P) ->
      Res = [R|Tail],
      R = Q,
      selection(List, Tot, Tail)
      ;   
      selection(List, Tot, Res)
    ).
crossover([],[]).
crossover([Q|List], Res) :-
    try_crossing(Q,List,Crossings),
    crossover(List, R2),
    union([Q|R2],Crossings,Res).
    
try_crossing(_,[],[]).
try_crossing(Q,[C|List],Res):-
    cross(Q,C,C1,C2),
%    Res = [C,C1,C2 | Tail],
    try_crossing(Q,List, Tail),
    union([C1,C2],Tail,Res).
try_crossing(Q,[C|List],Res):-
    \+ cross(Q,C,_,_),
%    Res = [C,C1,C2 | Tail],
    try_crossing(Q,List, Tail),
    Res=Tail.    

cross(Q,C, R1,R2) :-
    [Q1,Q2|Q_tail] = Q,
    [C1,C2,C3,C4] = C,
    Q1 =\= C3,
    Q1 =\= C4,
    Q2 =\= C3,
    Q2 =\= C4,
    R1 = [Q1,Q2,C3,C4],
    R2 = [C1,C2|Q_tail].

mutation([],[]).
mutation([Q|QList], [Q,M|RList]):-
    proper_length(Q,L),
    random_between(1,L,Rand1),
    random_between(1,L,Rand2),
    permute(Q,Rand1,Rand2,M),
    mutation(QList,RList).

permute(Q,X,Y,M):-
    nth1(X,Q, Ex),
    nth1(Y,Q, Ey),
    replace(Q,Y,Ex,M1),
    replace(M1,X,Ey,M).

replace([],_,_,[]).
replace([_|List],Index,Element,[N|NewList]):-
    Index = 1,
    N = Element,
    I is Index-1,
    replace(List,I,Element,NewList).

replace([L|List],Index,Element,[N|NewList]):-
    Index =\= 1,
    N = L,
    I is Index-1,
    replace(List,I,Element,NewList).

fitness([], 0).
fitness([Q|Qlist], Res) :-
    collisions(Q, Qlist, 1, Collisions),
    fitness(Qlist, R2),
    Res is R2 + Collisions.

collisions(_,[], _, 0).
collisions(Q,[Q1|Qlist],Xdist,Result) :-
  Q =\= Q1, %not on the same row  
  Test is abs(Q1-Q),
  Test =\= Xdist, %it means non diagonal conflict
  Xdist1 is Xdist + 1,
  collisions(Q,Qlist,Xdist1, R2),
    Result is R2.

collisions(Q,[Q1|Qlist],Xdist,Result) :-
  Q =\= Q1, %not on the same row  
  Test is abs(Q1-Q),
  Test = Xdist, %it means diagonal conflict
  Xdist1 is Xdist + 1,
  collisions(Q,Qlist,Xdist1, R2),
    Result is R2 + 1.

In particular I would like to point out at the main function genetic_four_queens(Population, Result), where after building the single functions evaluation,selection,reproduction and mutation I just use them like if they were functions in a way that feels imperative.

Is any of this right?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文