Penyelesaian Farmer Problem Menggunakan BFS (Breadth First Search)

Artikel kali ini akan membahas tentang farmer problem, dimana terdapat seorang petani yang membawa serigala, kambing, dan sayur di sebuah sisi sungai kemudian petani ini akan memindahkan ketiga bawaanya ke seberang sungai, termasuk petani itu sendiri, menggunakan perahu yang hanya muat untuk petani itu sendiri dan satu barang bawaannya. Syaratnya, kambing dan sayur tidak boleh bersama-sama, begitu juga dengan serigala dan kambing. Penyelesaian masalah ini menggunakan metode BFS (Breadth First Search) dengan bahasa prolog (.pl)

Pembahasan:

member(X,[X|_]).

member(X,[_|T]):-member(X,T).

printLst([]).

printLst([H|T]) :- printLst(T),write(H),nl.

go(Start,Goal) :- path(Start,Goal,Start).

path(Goal,Goal,L) :- write('Solution Path is: ' ), nl,

flatten(L,X),printLst(X).

path(State,Goal,L) :- move(State,Next), not(member(Next,L)),

path(Next,Goal,[Next|L]),nl,!.

opp(e,w).

opp(w,e).

move(state(X,X,G,C), state(Y,Y,G,C))

:- opp(X,Y), not(unsafe(state(Y,Y,G,C))),

write('try farmer takes wolf'),nl.

move(state(X,W,X,C), state(Y,W,Y,C))

:- opp(X,Y), not(unsafe(state(Y,W,Y,C))),

write('try farmer takes goat'),nl.

move(state(X,W,G,X), state(Y,W,G,Y))

:- opp(X,Y), not(unsafe(state(Y,W,G,Y))),

write('try farmer takes cabbage'),nl.

move(state(X,W,G,C), state(Y,W,G,C))

:- opp(X,Y), not(unsafe(state(Y,W,G,C))),

write('try farmer takes self'),nl.

move(state(F,W,G,C), state(F,W,G,C))

:- write('BACKTRACK'),nl, fail.

unsafe(state(X,Y,Y,_)) :- opp(X,Y).

unsafe(state(X,_,Y,Y)) :- opp(X,Y).

input output

4 ?- go(state(w,w,w,w),state(e,e,e,e)).

try farmer takes goat

try farmer takes goat

try farmer takes goat

BACKTRACK

try farmer takes self

try farmer takes wolf

try farmer takes wolf

try farmer takes goat

try farmer takes goat

try farmer takes cabbage

try farmer takes wolf

try farmer takes wolf

try farmer takes goat

try farmer takes goat

try farmer takes cabbage

BACKTRACK

BACKTRACK

try farmer takes cabbage

try farmer takes self

try farmer takes goat

Solution Path is:

state(w,w,w,w)

state(e,w,e,w)

state(w,w,e,w)

state(e,e,e,w)

state(w,e,w,w)

state(e,e,w,e)

state(w,e,w,e)

state(e,e,e,e)

true.

Penjelasan program

member(X,[X|_]).

member(X,[_|T]):-member(X,T).

printLst([]).

            Kode di atas merupakan perintah List.

printLst([H|T]) :- printLst(T),write(H),nl.

go(Start,Goal) :- path(Start,Goal,Start).

path(Goal,Goal,L) :- write('Solution Path is: ' ), nl,

flatten(L,X),printLst(X).

path(State,Goal,L) :- move(State,Next), not(member(Next,L)),

path(Next,Goal,[Next|L]),nl,!.

opp(e,w).

opp(w,e).

      Kode di atas merupakan kode untuk sisi yang berlawanan, yakni sisi barat menjadi sisi timur, sisi timur menjadi sisi barat.

move(state(X,X,G,C), state(Y,Y,G,C))

:- opp(X,Y), not(unsafe(state(Y,Y,G,C))),

write('try farmer takes wolf'),nl.

      Kode di atas memindahkan farmer dan wolf ke sisi sungai yang berlawanan tetapi dengan posisi baru yang aman.

move(state(X,W,X,C), state(Y,W,Y,C))

:- opp(X,Y), not(unsafe(state(Y,W,Y,C))),

write('try farmer takes goat'),nl.

Kode di atas memindahkan farmer dan goat ke sisi sungai yang berlawanan tetapi dengan posisi baru yang aman.

move(state(X,W,G,X), state(Y,W,G,Y))

:- opp(X,Y), not(unsafe(state(Y,W,G,Y))),

write('try farmer takes cabbage'),nl.

Kode di atas memindahkan farmer dan cabbage ke sisi sungai yang berlawanan tetapi dengan posisi baru yang aman.

move(state(X,W,G,C), state(Y,W,G,C))

:- opp(X,Y), not(unsafe(state(Y,W,G,C))),

write('try farmer takes self'),nl.

Kode di atas memindahkan farmer ke sisi sungai yang berlawanan tetapi dengan posisi baru yang aman.

move(state(F,W,G,C), state(F,W,G,C))

:- write('BACKTRACK'),nl, fail.

      Perintah backtracking, yakni proses mengulangi kembali pada posisi awal dan mencoba kembali.

unsafe(state(X,Y,Y,_)) :- opp(X,Y).

Kode di atas menunjukkan sisi yang tidak aman, yakni ketika goat dan cabbage dalam sisi yang sama.

unsafe(state(X,_,Y,Y)) :- opp(X,Y).

Kode di atas menunjukkan sisi yang tidak aman, yakni ketika wolf dan goat dalam sisi yang sama.