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:
- Searching (pencarian)
- Reasoning (penalaran)
- 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:
- Masukkan node akar ke dalam QUEUE
- Ambil node dari awal QUEUE, lalu cek apakah node merupakan solusi
- Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan
- Jika node bukan solusi, masukkan seluruh node anak ke dalam QUEUE
- Jika QUEUE kosong dan setiap node sudah dicek, pencarian selesai.
- 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
