Pendefinisian Problema Sebagai Proses Pencarian Ruang Keadaan

Pendefinisian Problema Sebagai Proses Pencarian Ruang Keadaan (State Space Search)

• Aspek tingkah laku cerdas yang mendasari teknik penyelesaian problema disebut proses pencarian ruang keadaan (space state search).
• Struktur representasi ruang keadaan bersesuaian dengan struktur pemecahan problema dalam dua cara penting, yaitu:

Definisi formal dari sebuah problema diperbolehkan untuk digunakan sebagai kebutuhan untuk mengubah suatu situasi yang diberikan menjadi suatu situasi yang diinginkan dengan menggunakan seperangkat operasi yang diperkenankan.
Pendefinisian proses pemecahan problema khusus diijinkan untuk digunakan sebagai kombinasi teknik-teknik yang telah dikenal dan proses pencarian, teknik umum dalam mengamati ruang tersebut untuk mencoba menemukan suatu jalan keluar dari keadaan saat ini menuju keadaan yang dituju. 

• Proses pencarian ruang keadaan itu sendiri tidaklah cukup untuk mengotomatisasikan tingkah laku pemecahan problema secara otomatis. 
• Proses pencarian ruang keadaan pencarian mendalam (exhaustive search) melakukan pencarian terhadap seluruh ruang keadaan serangkaian langkah yang paling dimungkinkan untuk menghasilkan kemenangan. Metode ini dapat diterapkan pada setiap ruang keadaan, namun ukuran ruang keadaan yang sangat ‘besar’ membuat pendekatan ini secara praktis tidak dimungkinkan. Misalnya, dalam permainan catur, terdapat 10120 keadaan atau konfigurasi papan yang berbeda.
• Kita tidak menggunakan exhaustive search tetapi menjalankan langkah-langkah yang terbukti efektif yang didasarkan pada aturan-aturan tertentu yang memandu proses pencarian ke arah ruang keadaan yang paling menjanjikan. Aturan inilah yang dikenal sebagai heuristik (heuristic dari bahasa Yunani yang artinya menemukan).

Performance searching

• Evaluasi sebuah pencarian sangat kompleks.
• Dasar pengukuran pencarian :

Seberapa cepat search menemukan penelesaian
Seberapa cepat pencarian menemukan penyelesaian yang baik

• Kecepata pencarian ditentukan oleh :

Panjang lintasan
Jumlah sesungguhnya penelusuran node

• Untuk mengukur performansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1. Completeness, apakah solusi pasti ditemukan ?
2. Time complexity, berapa lama waktu yang diperlukan
3. Space complexity, berapa banyak memori yang dibutuhkan
4. Optimally, apakah solusi yang ditemukan adalah solusi yang terbaik

Time & space complexity diukur berdasarkan 

• b -> faktor percabangan dari search tree
• d -> depth (kedalaman) dari solusi optimal
• m -> kedalaman maksimum dari search tree

Hal penting dalam menentukan keberhasilan sistem berdasar kecerdasan adalah kesuksesan dalam pencarian dan pencocokan.

Pada dasarnya ada 2 teknik pencarian dan pelacakan, yaitu pencarian buta (blind search) dan pencarian terbimbing (heuristic search).

Jenis-jenis metode pencarian

• Blind Search
• Breadth-first Search
• Depth-first Search
• Heuristic Search
• Generate and Test
• Hill Climbing
• Simple Hill Climbing
• Steepest-Ascent Hill Climbing
• Best-first Search
• OR Graph
• Algoritma A*
• Simulate Annealing

Blind search : 1. Pencarian Melebar Pertama (Breadth-First Search)

Pencarian dimulai dari Simpul Akar (Level 0) terus ke Level 1 dari kiri ke kanan sampai semua simpul pada Level tersebut dikunjungi, dan seterusnya ke Level 2, 3, ... sampai ditemukannya solusi.

Semua simpul pada Level n akan dikunjungi terlebih dahulu sebelum mengunjungi simpul-simpul pada Level n+1.

Pencarian Melebar Pertama (Breadth-First Search)

Algoritma

Buat sebuah antrian, inisialisasi node pertama dengan root dari tree

Bila node pertama jika tidak sama dengan GOAL, maka diganti dengan anak-anaknya dan diletakkan di belakang PER LEVEL

Bila node pertaman sama dengan GOAL, maka selesai

Pencarian Melebar Pertama (Breadth-First Search)

Keuntungan:

Tidak akan menemui jalan buntu

Jika hanya ada satu solusi, maka akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan:

Membutuhkan memori yang cukup banyak, karena menyimpan semua simpul dalam satu pohon.

Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke (n+1).

Blind search : 2. Pencarian Mendalam Pertama (Depth-First Search)

Pencarian dilakukan dari Simpul Akar ke simpul yang memiliki level lebih tinggi (Simpul Anak).

Proses pencarian dilakukan pada semua Simpul Anak sebelum dilakukan pencarian ke simpul-simpul yang selevel.

Pencarian Mendalam Pertama (Depth-First Search)

Algoritma :

Buat sebuah antrian, inisialisasi node pertama dengan ROOT dari tree

Bila node pertama tidak sama dengan GOAL, node dihapus dan diganti dengan anak-anaknya dengan urutan Lchild

Bola node pertama sama dengan GOAL, maka selesai

Pencarian Mendalam Pertama (Depth-First Search)

Keuntungan:

Membutuhkan memori yang relatif kecil, karena hanya simpul-simpul pada linatasan yang aktif saja yang disimpan.

Secara kebetulan, metode ini akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaaan.

Kelemahan:

Memungkinkan tidak ditemukannya tujuan yang diharapkan.

Hanya akan mendapatkan 1 solusi pada setiap pencarian.

Pencarian buta tidak selalu dapat diterapkan dengan baik. 

Hal ini karena waktu aksesnya yang cukup lama serta besarnya memori yang diperlukan. 

Kelemahan ini sebenarnya dapat diatasi dengan memberikan informasi tambahan dr domain yang bersangkutan.

Misalnya: 8-puzzle. Ada 4 operator yang dapat digunakan:

1. Ubin kosong digeser ke kiri
2. Ubin kosong digeser ke kanan
3. Ubin kosong digeser ke bawah
4. Ubin kosong digeser ke atas

Pada langkah pertama, hanya 3 operator yang bisa digunakan, yaitu ubin kosong geser kek kiri, ke atas atau ke kanan.

Apabila digunakan pencarian buta, kita tidak perlu mengetahui operasi apa yang akan dikerjakan (sembarang operasi bisa digunakan).

Pada pencarian heuristik, perlu diberikan informasi khusus dalam domain tersebut, antara lain:

Jumlah ubin yang menempati posisi yang benar. Jumlah yang lebih tinggi adalah jumlah yang lebih diharapkan (lebih baik).

Jumlah ubin yang menempati posisi yang salah. 

Jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Menghitung total gerakan yang diperlukan untuk mencapai tujuan.

Jumlah yang lebih kecil adalah yang diharapkan (lebih baik).

Daftar Pustaka

Louis E. Frenzel, Jr., Crash Course in Artificial Intelligence and Expert System, Howard W. Sams & Co., Indianapolis, USA.

Rich, Elaine and Knight, Kevin. 1991.  Artificial Intelligence. Mc-Graw Hill Book Co. New York.

Michalewicz, Zbigniew. 1996. Genetic Algorithms + Data Structures = Evolution Programs. Springler Verlag.

Suparman, Mengenal Artificial Intelligence, Penerbit Andi Offset Yogyakarta, Edisi pertama, 1991.

Sandi Setiawan, Artificial Intelligence, Penerbit Andi Offset Yogyakarta, Edisi pertama, 1993.

Kusumadewi, Sri. 2003. Artificial Intelligence, Teknik dan Aplikasinya. Yogyakarta: Graha Ilmu.

Uung Ungkawa, Bahasa Pemrograman Logika Turbo Prolog, Penerbit Andi Offset Yogyakarta, Edisi pertama 1992.

Tjendry Harianto, Bahasa Turbo Prolog, Penerbit Andi Offset Yogyakarta, Edisi pertama 1992.

Tavri Deviyan, Pemrograman Deklaratif dengan Turbo Prolog 2.0, Elex-Media Komputindo, Jakarta.

Prolog Tutorial by A. Aaby, http://cs.wwc.edu/KU/PR/Prolog.html