Metode-metode pencarian

Terdapat banyak metode pancarian yang telah diusulkan. Semua metode yang ada dapat dibedakan ke dalam dua jenis: pencarian buta/tanpa informasi (blind atau Un-informed search) dan pencarian heuristik/dengan informasi (heuristic atau  informed search). Setiap metode mempunyai karakteristik yang berbeda-beda dengan kelebihan dan kekurangannya masing-masing.

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

·    Completeness: apakah metode tersebut menjamin penemuan solusi  juka solusinya memang ada?

·         Time complexity : Berapa banyakwaktu  yang diperlukan?

·         Space complexity : Berapa banyak memory yang diperlukan?

·      Optimilaty : Apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda.

Blind/Un-informed Search

Disini digunakan istilah blind atau buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian. Di sini hanya akan dibahas enam metode yang tergolong blind search, yaitu: Breadth First Search (BFS),  Uniform Cost Search (UCS), Septh First Search (DFS), Depth-Limited Search (DLS),  Iterative-Deepening Search (IDS), dan Bi-directional search (DBS).

Breadth-First Search (BFS)

            Pencarian dilakukan pada semua simpul 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 cara seperti ini, BFS menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik. Dengan kata lain, BFS adalah complate  dan  optimal.  Tetapi, BFS harus meyimpan semua simpul yang pernah dibangkitkan. Hal ini harus dilakukan agar  BFS dapat melakukan penelusuran simpul-simpul samapai di level bawah. Jika b adalah faktor percabangan (jumlah simpul anak yang dimiliki oleh suatu simpul)  dan d  adalah kedalaman solusi, maka  jumlah simpul yang harus disimpan adalah sebanyak O(b^d). misalkan, untuk b = 10 dan d = 8, maka BFS harus membangkitkan dan menyimpan sebanyak 10⁰ + 10¹ + 10² +10³ + 10⁴ + 10⁵ + 10⁶ + 10⁷+ 10⁸ = 111.111.111 ≈10⁸ simpul. Jika diasumsikan bahwa dalam satu detik kompuer bisa membangkitkan dan menguji 10⁶ simpul, maka waktu proses yang diperlukan untuk menemukan solusi di level 8 adalah 100 detik (1,67 menit). Jika satu simpul direpresentasikan dalam struktur data sebesar 100 bytes, maka diperlukan memori sebersar 10¹⁰ bytes (atau 10 gigabytes). Dari segi kecepatan, hal ini mungkin bisa diterima. Tetapi dari sisi memori yang diperlukan, ini menjadi masalah yang serius. Dengan permasalahan dan komputer yang sama, waktu proses yang diperlukan untuk menemukan solusi di level 14 adalah 10⁸ detik (lebih dari 3 tahun), dan perlukan memori sebersar 10¹⁵ bytes (1.000 terabytes). Oleh karena itu, BFS sangat sulit diimplementasikan di dunia nyata.

Gambar dibawah ini mengilustrasikan pembangkitan pohon BFS untuk masalah jerigen air. Oleh karena BFS membangkitkan suksesor secara sekuensial dimulai dari aturan produksi  yang pertama kali ditemukan, maka pembangkitan suksesor dari suatu simpul bergantung pada urutan Aturan Produksi yang dibuat (lihat pada tabel). Jika urutan produksi 4 ditukar dengan aturan produksi 5, maka pohon BFS yang dibangkitkan akan berbeda.

Gambar : Pohon pencarian Breadth First Search (BFS) untuk masalah jerigen air.