Search Algorithms

25 views
Skip to first unread message

Kelly

unread,
Jul 20, 2017, 1:40:27 AM7/20/17
to SWI-Prolog
Hello all,

I have some search algorithms implemented in a program, which I can not modify. I also have a labyrinth represented in the picture:



I can implement the labyrinth in any way I want. But I'm not getting the correct result with my implementation. My question is: how can I represent the labyrinth in a way that produces the correct result?

I appreciate any help.

Here follows the code:

start(r1:_).
goal(_:r8).

action(go(P,Q),P,Q,D) :- link(P,Q,D).

link(r1,r2,1).
link(r1,r3,1).
link(r1,r4,1).
link(r1,r5,1).
link(r2,r6,1).
link(r2,r7,1).
link(r3,r6,1).
link(r3,r7,1).
link(r4,r7,1).
link(r4,r8,1).
link(r6,r9,1).

h(_,0).

%------------------------------
%I Can`t modify code from here
%------------------------------

search(T) :-
   start(E),
   search(T,[_:_:0:E:[]],[],P:G),
   type(T,N),
   format('~nTipo.: ~w',[N]),
   format('~nPlano: ~w',[P]),
   format('~nCusto: ~w~n~n',[G]).
search(_,[_:_:G:E:C|_],_,P:G) :-
   goal(E), !,
   reverse(C,P).
search(T,[_:_:G:E:C|F],V,P) :-
   suc(T,G:E:C,V,S),
   insert(T,S,F,NF),
   union([E],V,NV),
   search(T,NF,NV,P).
suc(T,G1:E:C,V,R) :-
   findall(F:H:G:S:[A|C],
  (action(A,E,S,G),
   not(member(S,V)),
   h(S,H), G is G1+G2,
   (T=4 -> F is G
   ;T=5 -> F is H
   ;T=6 -> F is G+H
   ;       F is 0)),R).
insert(1,S,F,NF) :- append(S,F,R),
                    length(R,L), shuffle(L,R,NF), !.
insert(2,S,F,NF) :- append(F,S,NF), !.
insert(3,S,F,NF) :- append(S,F,NF), !.
insert(_,S,F,NF) :- append(S,F,R), sort(R,NF), !.

shuffle(0,F,F) :- !.
shuffle(L,F,[X|NF]) :-
   N is random(L),
   nth0(N,F,X), delete(F,X,R),
   M is L-1,
   shuffle(M,R,NF), !.

type(1,aleatória).
type(2,breadth_first_search).
type(3,depth_first_search).
type(4,menor_custo).
type(5,melhor_estimativa).
type(6,a_search).



Reply all
Reply to author
Forward
0 new messages