Materi 3

Metode Pencarian dan Pelacakan

Hal penting dalam menentukan keberhasilan sistem cerdas adalah kesuksesan dalam pencarian.

1. Pencarian = suatu proses mencari solusidari suatu permasalahan melalui sekumpulan kemungkinan ruang keadaan (state space).
2. Ruang keadaan = merupakan suatu ruang yang berisi semua keadaan yang mungkin.

Untuk mengukur perfomansi metode pencarian, terdapat empat kriteria yang dapat digunakan :

• Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?
• Time complexity : berapa lama waktu yang diperlukan?
• Space complexity : berapa banyak memori yang diperlukan
• Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda

Dua teknik pencarian dan pelacakan

• Pencarian buta (blind search) :
  
• Pencarian melebar pertama (Breadth – First Search)
• Pencarian mendalam pertama (Depth – First Search)

• Pencarian terbimbing (heuristic search) :
• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)