METODE PENCARIAN DAN PELACAKAN (Blind Search)

• Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.
• Pencarian = suatu proses mencari solusi dari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).
• Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.s
• Untuk mengukur perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1. Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?
2. Space complexity : berapa banyak memori yang diperlukan
3. Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]
4. Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

Dua teknik pencarian dan pelacakan

A. PENCARIAN BUTA (Blind Search)

1. Pencarian melebar pertama (Breadth – First Search)
2. Pencarian mendalam pertama (Depth – First Search)

B. PENCARIAN TERBIMBING (Heuristic search)

1. Pembangkit & Pengujian (Generate and Test)
2. Pendakian Bukit (Hill Climbing)

Blind Search

Pencarian Melebar Pertama (Breadth-First Search)

1. Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1
2. Mulai dari akar terus ke level 1 dari kiri ke kanan
3. Kemudian ke level selanjutnya hingga solusi ditemukan

• Keuntungan

1. Tidak akan menemui jalan buntu
2. Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik
3. Jika ada satu solusi maka bread-first search akan menemukannya

• Kelemahannya

1. Membutuhkan memori yang cukup banyak
2. Membutuhkan waktu yang cukup lama

Pencarian mendalam pertama (Depth-First Search)

Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel.

• Keuntungan

1. Memori yang relatif kecil
2. Secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi

Source : https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/