Bagian ini membahas bagaimana
memecahkan suatu masalah denan teknik searching
atau pencarian. Langkah pertama yang
harus dilakukan adlaah mendefenisikan ruang
masalah untuk suatu masalah ayng
dihadapi. Ruang masalah ini dapat digambarkan sebagai himpunan keadaan (state) atau bisa juga sebagai himpunan
rute dari keadaan awal (Initial state) menuju keadaan tujuan (goal state). Langkah kedu adalah mendefenisikan aturan produksi
yang digunakan untuk mengubah suatu state
dan state lainnya. Langkah
terakhir adalah memilihi metode pencari yang tepat sehingga dapat menemukan
solusi terbaik dengan usaha yang minimal. Pada bagian ini juga dibahas sebagai
metode pencarian, yang dikelompokkan kedalam blind atau un-informed search (pencarian buta atau tidak berbekal
informasi). Juga dibahas analisa performansi dari masing-masing metode
pencarian tersebut, sehingga pembaca dapat menentukanmetode pencarian aoa yang
paling tepat untuk suatu masalah tertentu.
Ruang Masalah
Masalah utama dalam membangun
sistem berbasis AI adalah bagaimana mengoversi situasi yang diberikan ke dalam
situasi lain yang diinginkan menggunakan sekumpulan operasi tertentu. Untuk
melakukan hal ini, diperlukan sedikit kemampuan rekayasa. Perhatikan sebuah
masalah berikut ini.
Masalah : Jerigen air
Anda diberi dua jerigen air tanpa
skala ukuran, yang satu berkapasitas masksimum 4 galon dan yang lain
berkapasitas maksimum 3 galon. Terdapat sebuah kran yang dapat mengalirkan air
dengan jumlah yagn tidak terbatas yang dapat digunakan untuk mengisi
jerigen-jerigen tersebut. Bagaimana langkah anda untuk mendapatkan tepat 2
galon air di dalam jerigen berkapsitas 3 galon?
Solusi :
Untuk menyelesaiakan masalah jerigen air tersebut dengan
teknik pencarian di perlukan tiga langkah berikut :
a.
Definisikan
ruang masalah, initial state dan goal state
Ruang
masalah untuk masalah jerigen di atas dapat digambarkan sebagai himpunan
pasangan bilangan bulat (x,y) yang
berurut, sedemikian hingga x = 0, 1,
2, 3, atau 4 dan y = 0 1, 2, atau 3; x menyatakan jumlah air dalam jerigen berukuran 3 galon.
Dengan demikian, keadaan awal (Initial
state) dimana kedua jerigen masih kosong dinyatakan sebagai (0,0). Karena tujuannya adalah mendapat tepat
2 galon air di jerigen berukuran 3 galon (tidak peduli beraoa galon air yang
ada di jerigen berukuran 4 galon), makan goal
state dapat direpresentasikan sebagai (n,2) untuk setiap nilai n.
b.
Definisi
aturan produksi
Aturan
produksi dapat didefinisikan dengan menggambarkan struktur pohon dari
keadaan-keadaan yang telah didefinisikan diatas. Dengan merepresentasikan initial state (0,0) sebagai simpul akar (root) dari sebuah pohon, maka kita dapat
menelusuri simpul-simpul (keadaan-keadaan) berikutnya yang mungkin terjadi.
Operasi yang mungkin mengbah suatu state ke
state lainnya disebut sebagai aturan produksi. Penelusuran dilakukan sampai didapatkan semua
aturan produksi yang mungkin. Pertanyaan yang muncul adalah bagaimana kita tahu
bahwa aturan produksi yang kita definisikan tersebut sudah lengkap atau belum?
Suatu solusi mungkin tidak dapat ditemukan juka aturan produksinya tidak
terdefinisikan secara lengkap.
Aturan-aturan
produksi yang lengkapdan tidak dapat digunakan untuk memecahkan masalah jerigen
air ditunjukkan pada tabel dibawah ini.
a.
Pilih
metode pencarian yang tepat
Terdapat
berbagai macam metode pencarian yang dapat digunakan untuk masalah ini. Hal ini
akan dibahas satu per satu secara detail pada metode-metode pencarian
selanjutnya. Salah satu solusi untuk masalah tersebut terlihat pada tabel
dibawah. Pada solusi tersebut terdapat 4 aturan produksi yang di gunakan. Hal
ini berarti di perlukan 4 langkah untuk menyelesaikan masalah tersebut.
Sistem
Produksi
Pada masalah jerigen air diatas, metode pencarian
memainkan paranan penting dalam penyelasaian masalah. Untuk mempermudah
pemahaman sistem intelejensia berbasis teknik pencarian, marilah kita bahas
tentang Sistem Produksi yang terdiri dari :
a. Sebuah himpunan aturan, masing-masing terdiri dari sisi kiri yang
menentukan kemampuan aplikasi dari aturan tersebut dan sisi kanan yang
menggambarkan operasi yang dilakukan
jika aturan tesebut dilaksanakan.
b. satu atau
lebih pengetahuan atau bisnis data yang berisi informasi apa pun
untuk tujuan tertentu. Beberapa bagian basis data bisa permanen, dan bagian
yang lain bisa hanya merupakan solusi
untuk masalah saat ini. Informasi dalam basis data ini disusun secara tepat.
c. Strategi kontrol yang menspesifikasikan urutna dimana aturan
akan dibandingkan dengan basis data dan menspesifikasikan cara pemecahan
masalah jika beberapa aturan dapat dilakukan pada waktu yang sama.
Syarat-syarat strategi kontrol:
·
Cause motion
Perhatikan
kembali masalah jerigen air. Jika kita mengimplementasikan strategi kontrol sederhana dengan selalu memilih
aturan pertama pada daftar 12 aturan diartikel sebelumnya, maka kita tidak akan pernah memecahkan masalah. Strategi
kontrol yang tidak menyebabkan motion tidak
akan pernah mencapai solusi.
·
Systematic
Strategi
kontrol sederhana yang lain untuk mesalah jerigen air adalah: pada setiap
siklus, pilih secara random aturan-aturan yang dapat diaplikasikan. Strategi
ini lebih baik dari yang pertama, karena menyebabkan motion. Pada akhirnya strategi tersebut akan mencapai solusi. Tetapi,
mungkin kita akan mengunjungi beberapa state yang sama selama proses tersebut dan mungkin
menggunakan lebih banyak langkah daripada jumlah langkah minimum yang di
perlukan. Hal ini disebabkan strategi kontrol tersebut tidak sistematik.
Beberapa strategi kontrol yagn sistematik telah diusulkan, yang biasa disebut
sebagai metode-metode pencarian yang akan dibahas.
d. Pengaplikasi aturan (a rule applier) untuk mengaplikasikan aturan yang terpilih.
0 comments:
Post a Comment