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.

Program Silsilah Keluarga Menggunakan Prolog

Programming in Logic atau yang sering disingkat prolog merupakan bahasa pemrograman untuk komputasi simbolik, bukan numerik. Prolog cocok untuk mengatasi problem yang melibatkan objek dan hubungan antara objek-objek tersebut (Bratko, 1991). Bagi yang sudah atau sedang mengambil mata kuliah kecerdasan buatan (Artificial Intelegence) pasti tahu dengan bahasa yang satu ini.
Perbedaan operator logika dengan Prolog:

Operator Logika	Prolog
^	,
?	;
?	:-
¬	not

Di sini saya menggunakan prolog interpreter, SWI prolog (free), untuk mendapatkannya dapat didownload di http://www.swi-prolog.org/
Contoh aplikasi prolog yang umum adalah pada kasus silsilah keluarga. Nah, misalnya sebuah keluarga memiliki silsilah sebagai berikut.

Pada bahasa prolog kita dapat menuliskan fakta sebagai berikut:
married(yuda,nina).
Artinya Yuda menikah dengan Nina.
child(rico,yuda).
Artinya Rico adalah anak dari Yuda.
male(yuda).
Artinya Yuda adalah laki-laki.
Demikian juga dengan aturan, kita bisa menuliskannya sebagai berikut:
parent(A,B,C) :-child(A,B),married(B,C).
artinya jika A adalah anak B dan B menikah dengan C maka orang tua dari A adalah B dan C.
download silsilah-keluarga-dalam-prolog.pdf
download kode prolog silsilah.txt
Copy silsilah.txt dalam notepad++ kemudian simpan dengan nama silsilah.pl lalu simpan dalam direktori prolog (biasanya di My Document\Prolog)
Semoga bermanfaat.