Hal penting dalam menentukan keberhasilan sistem
berdasarkan kecerdasan adalah dalam pencarian dan pencocokan. Pada dasarnya ada
2 teknik pencarian dan pelacakan yang digunakan, yaitu pencarian buta (blind
search) dan pencarian terbimbing (heuristic search).
Exhaustive search –
adalah proses pencarian terhadap seluruh ruang keadaan serangakaian langkah
yang paling dimungkinkan untuk menghasilkan kemenangan. Walaupun metode ini
dapat diterapkan pada setiap ruang keadaan, namum ukuran ruang keadaan yang
sangat besar membuat pendekatan ini secara praktis tidak dimungkinkan (dalam
permainan catur terdapat 10120 keadaan ). Bila kasus ini diimplementasikan ke
dalam sisten komputermaka akan membutuhkan memori yang sangat besar, dan waktu
pencarian yang sangat lama.
1. Pencarian Parsial (Blind Search)
·
Pencarian melebar pertama (Breadth – First
Search)
·
Pencarian mendalam pertama (Depth – First
Search)
-
Algoritma
Buat suatu variabel Node_List dan tetapkan
sebagai keadaan awal. Kerjakan langkah-langkah berikut ini sampai tujuan
tercapai atau Node_List dalam keadaan kosong. Hapus elemen pertama dari
Node_List, sebut dengan nama C, jika Node_List kosong, maka keluar.
Pada setiap langkah yang aturannya cocok
dengan C maka kerjakan. Aaplikasi aturan tersebut untuk membentuk suatu keadaan
baru. Jika keadaan awal adalah tujuan yang diharapkan, sukses dan keluar. Jika
tidak demikian, tambahkan keadaan awal yang baru tersebut pada akhir Node_List.
-
Keuntungan
Tidak akan menemui jalan buntu, menjamin
ditemkannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti
yang paling baik. Jika ada satu solusi maka bread first search akan
menemukannya.
-
Kelemahannya
Membutuhkan memori yang sangat banyak. Membutuhkan
waktu yang cukup lama karna akan menguji dan level untuk mendapatkan solusi
pada level yang ke-(n+1).
2. Pencarian Heuristik (Heuristic Search)
-
Generate and Test
-
Hill Climbing
-
Best First Search
`Keuntungan :
-
Memori yang relatif kecil
-
Secara kebetulan, akan menemukan solusi
tanpa harus menguji lebih banyak lagi
3. Pencarian Heuristik
Pencarian buta tidak selalu dapat
diterapkan dengan baik
-
Waktu aksesnya yang cukup lama
-
Besarnya memori yang diperlukan
·
Metode heuristic search diharapkan bisa
menyelesaikan permasalahan yang lebih besar.
·
Metode heuristic search menggunakan suatu
fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu
menuju ke simpul tujuan disebut fungsi heuristic
·
Aplikasi yang menggunakan fungsi heuristic
: Google, Deep Blue Chess Machine
·
Contoh pada masalah 8 puzzle
Keadaan
awal tujuan
Keadaan Awal Tujuan Pencarian
Heuristik
·
Operator
-
Ubin kosong geser ke kanan
-
Ubin kosong geser ke kiri
-
Ubin kosong geser ke atas
-
Ubin kosong geser ke bawah
Sumber:
0 komentar:
Posting Komentar