Teknik Searching -Problem Solving

Penyelesaian Masalah Berdasarkan Teknik AI
Untuk membangun sistem yang mampu menyelesaikan suatu masalah perlu mempertimbangkan 4 hal,
yaitu:
1. Mendefinisikan masalah dengan jelas
2. Menganalisis masalah
3. Mengumpulkan dan merepresentasikan knowledge
4. Memilih teknik pemecah masalah terbaik dan gunakan untuk masalah tertentu.

Ada 4 teknik dalam menyelesaikan masalah, yaitu:
1. Searching
2. Reasoning
3. Planning
4. Learning

Pendefinisian Masalah Sebagai Pencarian Ruang Keadaan
Masalah utama dalam membangun sistem berbasis AI adalah bagaimana mengkonversikan situasi yang diberikan ke dalam situasi lain yang diinginkan menggunakan sekumpulan operasi tertentu.

A Water Jug Problem
Anda diberi dua buah gelas, yang satu ukuran 4 galon dan yang satunya 3 galon. Kedua gelas tidak memiliki skala ukuran. Terdapat pompa yang dapat digunakan untuk mengisi gelas tersebut. Bagaimana Anda mendapatkan tepat 2 galon air di dalam gelas 4 ukuran galon?
Ruang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0, 1, 2, 3, atau 4 dan y = 0, 1, 2, atau 3; x menyatakan jumlah air dalam gelas ukuran 4 galon, dan y menyatakan jumlah air dalam gelas ukuran 3 galon. Keadaan mula-mula adalah (0,0). State tujuan adalah (2,n) untuk setiap
Karakteristik Masalah Dalam AI :
• Apakah masalahnya dapat didekomposisi menjadi himpunan sub masalah yang (hampir) independen lebih kecil atau lebih mudah ?
• Dapatkah langkah penyelesaian diacuhkan paling tidak dibatalkan ketika dapat dibuktikan hal tersebut tidak bijaksana ?
• Apakah universe masalahnya dapat diprediksi ?
• Apakah solusi yang baik dari masalah tertentu jelas tanpa membandingkan dengan seluruh solusi lain yang mungkin ?
• Apakah solusi yang diinginkan sebuah keadaaan dari dunia atau sebuah jalur dari keadaan ?
• Apa peran dari pengetahuan ?
• Apakah pekerjaan memerlukan interakasi dengan manusia ?
Sistem Produksi
Sistem produksi terdiri dari:
* Himpunan aturan, masing-masing terdiri dari sisi kiri (pola) yang menentukan kemampuan aplikasi dari aturan tersebut dan sisi kanan yang menggambarkan operasi yang dilalukan jika aturan dilaksanakan.
* Satu atau lebih pengetahuan atau basis data yang berisi informasi apapun untuk tugas 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.
* Strategi kontrol yang menspesifikasikan urutan dimana aturan akan dibandingkan dengan basis data dan menspesifikasikan cara pemecahan masalah yang timbul ketika beberapa aturan sesuai sekaligus pada waktu yang sama.
* A rule applier (pengaplikasi aturan).
Strategi Kontrol
Syarat-syarat strategi kontrol:
* cause motion. Perhatikan kembali water jug problem. Jika kita mengimplementasikan strategi kontrol sederhana dengan selalu memilih aturan pertama pada daftar 12 aturan yang telah dibuat, 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 water jug problem: 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 dari jumlah langkah yang diperlukan. Hal ini disebabkan strategi kontrol tersebut tidak sistematik. Beberapa strategi kontrol yang sistematik telah diusulkan, yang biasa disebut sebagai metoda-metoda dalam teknik searching.

Strategi Pencarian (Teknik Searching)
Teknik pencarian, yaitu teknik penyelesaian masalah yang mempresentasikan masalah ke dalam ruang keadaan (state) dan secara sistematis melakukan pembangkitan dan pengujian state-state dari initial state sampai ditemukan suatu goal state.
Searching : digunakan dalam pencarian rute optimum untuk memandu seseorang di perjalanan, misal di swedia setiap taksi dilengkapi dengan GPS (Global Positioning System).

Terdapat empat kriteria dalam strategi pencarian, yaitu:
* Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?
* Time complexity: Berapa lama waktu yang diperlukan?
* Space complexity: Berapa banyak memori yang diperlukan?
* Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?

Teknik Pencarian dibedakan ke dalam dua jenis, yaitu:
1. Pencarian buta/tanpa informasi (Blind atau Un-Informed Search)
2. Pencarian heuristik/dengan informasi (Heuristic atau Informed Search)
>>Pencarian Buta/Tanpa Informasi (Blind atau Un-Informed Search)
 Digunakan istilah blind atau buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Depth-First Search (DFS)
Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).
Kelebihan DFS adalah:
* Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
* Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.
Kelemahan DFS adalah:
* Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
* Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

Breadth-First Search (BFS)
Pencarian dilakukan pada semua node dalam setiap level secara berurutan dari kiri ke kanan. Jika pada satu level belum ditemukan solusi, maka pencarian dilanjutkan pada level berikutnya. Demikian seterusnya sampai ditemukan solusi. Dengan strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus dilakukan untuk penelusuran balik jika solusi sudah ditemukan. Gambar dibawah mengilustrasikan pembangkitan pohon BFS untuk masalah Water Jug. Pembangkitan suksesor dari suatu node bergantung pada urutan dari Aturan Produksi yang dibuat. Jika urutan dari aturan 4 ditukar dengan aturan 5, maka pohon BFS yang dibangkitkan juga akan berubah.

>>Pencarian Heuristic/dengan Informasi (Heuristic atau Informed Search)
Generate-and-Test
Metode Generate-and-Test adalah metode yang paling sederhana dalam pencarian heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis, maka prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.
Algoritma Generate-and-Test adalah prosedur DFS karena solusi harus dibangkitkan secara lengkap sebelum dilakukan test. Algoritma ini berbentuk sistematis, pencarian sederhana yang mendalam dari ruang permasalahan. Generate & test juga dapat dilakukan dengan pembangkitan solusi secara acak, tetapi tidak ada jaminan solusinya akan ditemukan.

Hill Climbing
Hill Climbing berbeda Generate-and-Test, yaitu pada feedback dari prosedur test untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang pencarian. Dalam prosedur Generate & test , respon fungsi pengujian hanya ya atau tidak. Tapi jika pengujian ditambahkan dengan atauran fungsi-fungsi yang menyediakan estimasi dari bagaimana mendekati state yang diberikan ke state tujuan, prosedur pembangkit dapat mengeksplorasi ini sebagaimana ditunjukkan di bawah. HC sering digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah gedung yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah jarak yang terpendek.

Best-First Search
Merupakan metode yang membangkitkan suksesor dengan mempertimbangkan harga (didapat dari fungsi heuristik tertentu) dari setiap node, bukan dari aturan baku seperti DFS maupun BFS. Gambar 3.4 mengilustrasikan langkah-langkah yang dilakukan oleh algoritma Best First Search. Pertama kali, dibangkitkan node A. Kemudian semua suksesor A dibangkitan, dan dicari harga paling minimal. Pada langkah 2, node D terpilih karena harganya paling rendah, yakni 1. Langkah 3, semua suksesor D dibangkitkan, kemudian harganya akan dibandingkan dengan harga node B dan C. Ternyata harga node B paling kecil dibandingkan harga node C, E, dan F. Sehingga B terpilih dan selanjutnya akan dibangkitkan semua suksesor B. Demikian seterusnya sampai ditemukan node tujuan.

Referensi:
Suyanto. 2007. Artificial Intelligence. Bandung : Informatika Bandung
hanz-kampus.blogspot.com/…/teknik-pencarian-kecerdasan-buatan.html
www.ittelkom.ac.id
www.ephi.web.id/kumpulan-artikel-mainmenu-50/54.html
http://blog.uin-malang.ac.id/alan/2010/10/16/teknik-searching/