3 pencarian buta

22
Pencarian Buta (Blind Search) Danar Retno Sari STMIK – STIKOM Balikpapan 2015

Upload: danar-retno-sari

Post on 05-Aug-2015

98 views

Category:

Education


2 download

TRANSCRIPT

Pencarian Buta (Blind Search)Danar Retno Sari

STMIK – STIKOM Balikpapan 2015

Tujuan Pembelajaran

• Mahasiswa mampu memahami dan mengimplementasikan beberapa metode pencarian dalam ruang keadaan.

Kusumadewi; Sri. 2003. Artificial Intelligence (Teknik & Aplikasinya). Yogyakarta: Graha Ilmu.

Rich,E. dan Knight, K. 1991. Artificial Intelligence. Edisi 2. New York: McGraw-Hill Inc

Pencarian Buta(Blind Search)

Breadth First Search

Pada metode Breadth First Search, pencarian dilakukan pada node di level n terlebih dahulu, sebelum melanjutkan pencarian pada node di level n+1

Pencarian dilakukan dari node Parent (paling atas) kemudian dilanjutkan ke node di level setelah parent (n+1).

Pencarian dilakukan dari kiri ke kanan, dengan melakukan pengecekan apakah node yang di lewati memiliki child

Pola Pencarian Breadth First Search

MM

AA BB CC

DD EE FF GG

HH II JJ KK

Pencarian di level 0

MM

M adalah node parent

Notasi penulisan :Open list : MClose list : -

• Pencarian berawal di node M (parent), kemudian pencarian akan menampilkan child dari node M

• Child dari node M adalah A – B – C

MM

AA BB CC

Notasi penulisan :Open list : A, B, CClose list : M

Pencarian di level 1

• Kemudian dilakukan pencarian pada node A, B, C

• Jika node A, B, C mempunyai child, maka pencarian akan menampilkan node child tersebut, dan menutup node yang menjadi parentnya

MM

AA BB CC

DD EE

Notasi penulisan :Open list : B, C, D, EClose list : M, A

MM

AA BB CC

DD EE

Notasi penulisan :Open list : C, D, EClose list : M, A, B

MM

AA BB CC

DD EE FF GG

Notasi penulisan :Open list : D, E, F, GClose list : M, A, B, C

Pencarian di level 2

MM

AA BB CC

DD EE FF GG

Notasi penulisan :Open list : E, F, GClose list : M, A, B, C, D

MM

AA BB CC

DD EE FF GG

HH II

Notasi penulisan :Open list : F, G, H, IClose list : M, A, B, C, D, E

MM

AA BB CC

DD EE FF GG

HH II

Notasi penulisan :Hasil : M, C, F

F merupakan tujuan

Saat pencarian sampai pada node yang merupakan tujuan maka, pencarian akan berhenti.

Depth First Search

Pada Depth-First Search, proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel

Pencarian dimulai dari node parent (yang paling atas), kemudian dilanjutkan ke node child

Pola Pencarian Depth First Search

MM

AA BB CC

DD EE FF GG

HH II JJ KK

Pencarian di level 0

MM

M adalah node parent

Notasi penulisan :Open list : MClose list : -

MM

AA BB CC

Notasi penulisan :Open list : A, B, CClose list : M

MM

AA BB CC

DD EE

Notasi penulisan :Open list : B, C, D, EClose list : M, A

MM

AA BB CC

DD EE

Notasi penulisan :Open list : B, C, EClose list : M, A, D

MM

AA BB CC

DD EE

HH II

Notasi penulisan :Open list : B, C, H, IClose list : M, A, D, E

MM

AA BB CC

DD EE

HH II

Notasi penulisan :Open list : B, C, IClose list : M, A, D, E, H

MM

AA BB CC

DD EE

HH II I merupakan keadaan tujuan

Saat pencarian sampai pada node yang merupakan tujuan maka, pencarian akan berhenti.

Notasi penulisan :Hasil : M, A, E, I