Depth First Search
Depth-First Search (DFS) adalah salah satu algoritma pencarian yang menggunakan struktur data Stack saat mencapai suatu simpul atau vertex yang terhubung dalam suatu graph. Kemampuannya dalam menemukan simpul-simpul yang belum dikunjungi memudahkan pencarian solusi optimum dalam suatu persoalan termasuk persoalan lintasan terpanjang (longest path problem).
LISTING PROGRAM
?-
G_X=20, G_Y=20,
X1 is 20*G_X, Y1 is 20*G_Y,
retractall(ico(_,_,_)),
set(click(1|_)),
add_icon2(default),
add_icon2("c1.ico"),
add_icon2("c2.ico"),
add_icon2("c3.ico"),
add_icon2("c4.ico"),
add_icon2("c5.ico"),
add_icon2("c6.ico"),
add_icon2("c7.ico"),
add_icon2("c8.ico"),
add_icon2("c9.ico"),
add_icon2("c10.ico"),
add_icon2("c11.ico"),
add_icon2("c12.ico"),
add_icon2("c13.ico"),
add_icon2("c14.ico"),
add_icon2("c15.ico"),
add_icon2("c16.ico"),
add_icon2("c17.ico"),
window( _, _, win_func(_), "Memory Blocks", 200, 100, 373, 412).
write_mark(x, X1, Y1, X2, Y2) :-
line(X1, Y1, X2, Y2),
line(X2, Y1, X1, Y2).
write_mark(o, X1, Y1, X2, Y2) :-
ellipse(X1, Y1, X2, Y2).
win_func(init) :-
menu( pop_up, _, _, menu_file(_), "&File"),
put_buttons,
fail.
put_buttons :-
for( X, 0, 300, 60),
for( Y,0, 300, 60),
button( _, 1, but_func(_), "", X, Y, 60, 60),
fail.
put_buttons.
menu_file(init) :-
menu( normal, _, 1, menu_exit(_), "&Exit").
menu_exit(press) :-
close_window(_).
but_func(press) :-
position(_,X, Y),
click(N| _),
m_click(X, Y, N).
m_click(X, Y, 1):-
close_window(_),
X1 is X//60,
Y1 is Y//60,
ico(X1,Y1,Ico),
X2 is X1*62 +10,
Y2 is Y1*62 +10,
icon( H, _, fail(_), Ico, X2, Y2),
set(click(2, H, Ico, X, Y)).
m_click(X, Y, 2):-
close_window(_),
Xp is X//60,
Yp is Y//60,
click(_, H1, Ico1, X1, Y1),
ico(Xp,Yp,Ico2),
Xs is Xp*62 +10,
Ys is Yp*62 +10,
icon( H2, _, fail(_), Ico2, Xs, Ys),
if_equal(Ico1, Ico2, H1, H2, X1, Y1, X, Y).
m_click(X, Y, 3):-
click(_, H1, H2, X1, Y1, X2, Y2),
close_window(H1),
close_window(H2),
button( _, 1, but_func(_), "", X1, Y1, 60, 60),
button( _, 1, but_func(_), "", X2, Y2, 60, 60),
set(click(1|_)).
if_equal(Ico1, Ico2|_) :-
Ico1=Ico2,
set(click(1|_)).
if_equal(Ico1, Ico2, H1, H2, X1, Y1, X2, Y2) :-
set(click(3, H1, H2, X1, Y1, X2, Y2)).
add_icon(Ico):-
X is random(6),
Y is random(6),
not(ico(X,Y,_)),
assert(ico(X,Y,Ico)), !.
add_icon(Ico):-add_icon(Ico).
add_icon2(Ico):-
add_icon(Ico),
LOGIKA Depth-First Search (DFS)
Pencarian DFS dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
Kelebihan DFS adalah:
• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.
Kelemahan DFS adalah:
• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).
Aturan game Memory Block:
a.Buka dua kartu.
b.Periksa apakah gambar kedua kartu tersebut mempunyai gambar yang sama.
c.Jika kedua kartu tidak sama, maka kedua kartu tersebut akan tertutup lagi dengan sendirinya. Kemudian buka kartu
kartu selanjutnya Jika sama maka kartu akan terbuka.
d.lanjut ke kartu berikutnya yang belum terbuka.
0 comments:
Post a Comment