Teknik Pemecahan Masalah

Banyak cara yang digunakan untuk membangun sistem yang dapat menyelesaikan masalah-masalah di AI. Teknik penyelesaian masalah yang dapat dipakai untuk menyelesaikan permasalahan di AI diantaranya:

1. Searching (pencarian)
2. Reasoning (penalaran)
3. Learning (Pembelajaran)

1. Searching (pencarian)

pemecahan masalah dengan teknik searching akan lebih mudah bila objek-objeknya direpresentasikan dalam graph. Representasi graph dilakukan dengan pertama tama membuat representasi objek masalah sebagai simpul serta representasi hubungan antar objek dengan menghubungkan simpul-simpul tersebut. Setelah itu setiap simpul dalam graph dikunjungi secara sistematis (traverse).

Teknik searching dibagi menjadi 2 yaitu:

• Pencarian buta (blind search)
• Pencarian terbimbing (heuristic search).

Pencarian buta (blind search)

Beberapa metode yang ada di pencarian buta (blind search) antara lain:

• Pencarian melebar pertama (breadth first search)
• Pencarian mendalam pertama (depth first search)

BREADTH FIRST SEARCH

Pada metode BFS, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node–node pada level n+1

Breadth first search

Dalam metode BFS, node anak yang telah dikunjungi disimpan dalam suatu QUEUE (antrian). QUEUE ini digunakan untuk mengacu simpul-simpul yang bertetangga dengan yang akan dikunjungi sesuai antrean.

Berikut adalah langkah-langkah algoritma BFS:

1. Masukkan node akar ke dalam QUEUE
2. Ambil node dari awal QUEUE, lalu cek apakah node merupakan solusi
3. Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan
4. Jika node bukan solusi, masukkan seluruh node anak ke dalam QUEUE
5. Jika QUEUE kosong dan setiap node sudah dicek, pencarian selesai.
6. Jika QUEUE tidak kosong, ulangi pencarian mulai dari poin 2.

Keuntungan metode BFS
Menjamin ditemukannya solusi yang paling baik (complete & optimal)

Kelemahan
Karena BFS harus menyimpan seluruh node yang dibangkitkan maka metode ini membutuhkan memori dan waktu yang cukup banyak

Kasus 1
Diketahui : pohon pelacakan yang ada pada gambar di samping ini :
Pertanyaan : implementasikan algoritma BFS untuk mencari solusi dari node awal (start) S sampai node G (goal)

Kasus 1

Iterasi ke – 1
masukkan node S ke QUEUE
gambar antriannya:

representasi ruang keadaan: (S)

keluarkan S dari QUEUE dan cek apakah S adalah goal?

ternyata S ≠ goal

S punya anak A dan B, masukkan ke dalam QUEUE

Representasi ruang keadaan 

Iterasi ke – 2

keluarkan A dari QUEUE dan cek apakah A adalah goal?

Ternyata A ≠ Goal

A punya anak C dan D, masukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 3

keluarkan B dari QUEUE dan cek apakah B adalah goal?

Ternyata B ≠ Goal

B punya anak E dan F, masukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 4

keluarkan C dari QUEUE dan cek apakah C adalah goal?

Ternyata C ≠ Goal

C tidak punya anak, jadi tidak ada yang dimasukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 5
keluarkan D dari QUEUE dan cek apakah D adalah goal?

Ternyata D ≠ Goal
D tidak punya anak, jadi tidak ada yang dimasukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 6

keluarkan E dari QUEUE dan cek apakah E adalah goal?

Ternyata E ≠ Goal

E punya anak H dan G, masukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 7
keluarkan F dari QUEUE dan cek apakah F adalah goal?

Ternyata F ≠ Goal
F tidak punya anak, jadi tidak ada yang dimasukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 8
keluarkan H dari QUEUE dan cek apakah H adalah goal?

Ternyata H ≠ Goal

H tidak punya anak, jadi tidak ada yang dimasukkan ke QUEUE

Representasi Ruang Keadaan

Iterasi ke – 9

keluarkan G dari QUEUE dan cek apakah G adalah goal?

Ternyata G = Goal

Pencarian Dihentikan.

Mencari Solusi :

G anaknya E, dan E anaknya B, dan B anaknya S

Karena S adalah node akar maka pencarian solusi dihentikan dan diperoleh  solusi

S – B – E – G