TEKNIK PENCARIAN (Searching)

TEKNIK PENCARIAN (SEARCHING) dalam kecerdasan buatan

Sistem yang menggunakan kecerdasan buatan akan memberikan output berupa solusi dari suatu masalah berdasarkan kumpulan pengetahuan yang ada.

Untuk membangun sebuah sistem yang digunakan untuk menyelesaikan suatu problem, dibutuhkan 3 hal sbb :

1.      Mendefinisikan ruang masalah untuk masalah yang dihadapi : spesifikasi kondisi awal dan solusi yang diharapkan.

2.      Mendefinisikan  aturan produksi yang digunakan untuk mengubah state ke state lainnya

3.      Memilih metode pencarian yang tepat sehingga menemukan solusi terbaik dengan usaha yang minimal

Metode yang dapat digunakan untuk memecahkan masalah :

—  Pencarian buta atau tidak berbekal informasi (blind or un-informed search)

—  Pencarian dengan panduan ( heuristic or informed search)

1)      Masalah pertama yang akan kita bahas kali ini adalah masalah Ember.

Contoh permasalahan :

Diberikan 2 ember air yang berkapasitas 8 liter dan 6 liter. Kita dapat mengisi satu ember dari ember lainnya dan proses penakaran hanya dengan memakai 2 ember tersebut.

Bagaimana kita bisa mengisikan tepat 4 liter dalam ember 8 liter?      

Sistem penyelesaian masalah :

Menentukan aksi-aksi (problem space) yang bisa mengubah kondisi pada kedua ember dalam bentuk rule atau tree-diagram. Contoh kemungkinan aksi-aksi:

a) Isi ember 8 liter

b) Isi ember 6 liter

c) Kosongkan ember 8 liter

d) Kosongkan ember 6 liter

e) Isikan seluruh air dalam ember 8 liter ke 6 liter.

     f)  Isikan seluruh air dalam ember 6 liter ke 8 liter.

     g) Penuhi ember 8 liter dari 6 liter.

     h) Penuhi ember 6 liter dari 8 liter.

Membuat pohon pelacakan, seperti di bawah ini :

tujuan telah tercapai yaitu mengisi tepat 4 liter dalam ember berkapasitas 8 liter.

2)      Masalah jerigen air

Contoh masalah :

Anda diberikan dua buah jirigen air tanpa skala ukuran, yang satu berkapasitas maksimum 4 galon  dan yang lain berkapasitas maksimum 3 galon. Terdapat sebuah kran yang dapat mengalirkan air dengan jumlah tidak terbatas yang dapat digunakan untuk mengisi jirigen tersebut. Bagaimana langkah anda untuk mendapatkan tepat 2 galon air didalam jirigen berkapasitas 3 galon?

Langkah penyelesaian :

—  Definisikan ruang masalah, initial state, goal state

            x : jumlah air dalam jirigen 4 galon

            y : jumlah air dalam jirigen 3 galon

            initial state : (0,0)

            goal state  : (n, 2)

—  Definisikan aturan produksi

            Aturan produksi adalah : operasi yang mengubah suatu state ke state lainnya.

—  Contoh aturan produksi untuk permasalahan diatas

—  Pilih metode pencarian yang tepat

Salah satu solusi untuk masalah diatas adalah :

3)      Kasus petani, serigala dan sayuran

Pada suatu hari ada seorang petaniyang mempunyai seekor kambing dan serigala. Pada suatu hari petani itu memanen sayuran, karena membutuhkan uang petani hendak menjual kambing, serigala dan sayurannya ke pasar. Untuk sampai di pasar ia harus menyebrangi sebuah sungai. Permasalahannya adalah di sungai itu hanya ada satu perahu yang hanya bisa memuat petani dan satu penumpang lain.

Penyelesaian :

•      Identifikasi ruang keadaan

Permasalahan dilambangkan dengan (x: Kambing, y: Srigala, z: Sayuran, w: Perahu).

•      Keadaan awal :Daerah asal= (1,1,1,1), dan

                        Daerah seberang=(0,0,0,0).

Keadaan Tujuan: Daerah asal= (0,0,0,0), dan

                        Daerah seberang=(1,1,1,1).

•      Tentukan kumpulan aturannya :

Solusinya adalah :