Strategi Pencarian

Strategi Pencarian

Terdapat empat kriteria dalam strategi pencarian, yaitu:

• Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?
• Time complexity: Berapa lama waktu yang diperlukan?
• Space complexity: Berapa banyak memori yang diperlukan?
• Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?

Depth-First Search (DFS)

Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai

ditemukan solusi. Jika solusi ditemukan maka tidak diperlukan proses backtracking (penelusuran balik untuk mendapatkan jalur yang dinginkan).

Kelebihan DFS adalah:

• Pemakain memori hanya sedikit, berbeda jauh dengan BFS yang harus menyimpan semua node yang pernah dibangkitkan.
• Jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Kelemahan DFS adalah:

• Jika pohon yang dibangkitkan mempunyai level yang dalam (tak terhingga), maka tidak ada jaminan untuk menemukan solusi (Tidak Complete).
• Jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka pada DFS tidak ada jaminan untuk menemukan solusi yang paling baik (Tidak Optimal).

                  

Gambar 2.5 Penelusuran Depth First Search untuk Water Jug Problem.

Breadth-First Search (BFS)

Pencarian dilakukan pada semua node 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 strategi ini, maka dapat dijamin bahwa solusi yang ditemukan adalah yang paling baik (Optimal). Tetapi BFS harus menyimpan semua node yang pernah dibangkitkan. Hal ini harus dilakukan untuk penelusuran balik jika solusi sudah ditemukan. Gambar 2.4 mengilustrasikan pembangkitan pohon BFS untuk masalah Water Jug. Pembangkitan suksesor dari suatu node bergantung pada urutan dari Aturan Produksi yang dibuat (lihat gambar 2.3). Jika urutan dari aturan 4 ditukar dengan aturan 5, maka pohon BFS yang dibangkitkan juga akan berubah.

         

            

Gambar 2.4 Pohon Breadth First Search untuk Water Jug Problem.

Berikut ini membahas metoda-metode yang terdapat dalam teknik pencarian yang berdasarkan pada panduan (Heuristic Search), yaitu Generate and Test, Simple Hill Climbing, Steepest-Ascent Hill Climbing, Simulated Annealing, Best First Search,Greedy Search, A Star (A*), Problem Reduction, Constraint Satisfaction, dan Means-Ends Analysis.

Generate-and-Test

Metode Generate-and-Test adalah metode yang paling sederhana dalam pencarian heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis, maka prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.

Algoritma Generate-and-Test adalah prosedur DFS karena solusi harus dibangkitkan secara lengkap sebelum dilakukan test. Algoritma ini berbentuk sistematis, pencarian sederhana yang mendalam dari ruang permasalahan. Generate & test juga dapat dilakukan dengan pembangkitan solusi secara acak, tetapi tidak ada jaminan solusinya akan ditemukan.

Algorithm: Generate-and-Test

1. Generate a possible solution. For some problems, this means generating a particular

point in the problem space. For others, it means generating a path from a start state.

2. Test to see if this is actually a solution by comparing the chosen point or endpoint of

the chosen path to the set of acceptable goal states.

3. If a solution has been found, quit. Otherwise, return to step 1.

Contoh kasus:

Untuk permasalahan sederhana maka tehnik generate & test adalah tehnik yang layak. Sebagai contoh, pada teka-teki yang terdiri dari empat kubus segi enam, dengan masingmasing sisi dari setiap kubus dicat dengan 4 warna. Solusi dari teka-teki terdiri dari susunan kubus dalam beberapa baris yang semuanya empat sisi dari satu blok baris yang menunjukkan nasing-masing warna. Masalah ini dapat diselesaikan dengan manusia

dalam beberapa menit secara sistematis dan lengkap dengan mencoba semua kemungkinan. Ini bisa diselesaikan dengan lebih cepat menggunakan prosedur generate & test. Pandangan sekilas pada empat blok yang tampak bahwa masih ada lagi, katakanlah bagian merah dari warna-warna lain yang ada. Sehingga ketika menempatkan

blok dengan beberapa bagian merah, ini akan menjadi ide yang baik untuk digunakan jika

sebagian darinya sebisa mungkin dibagian luar. Sebagian yang lain sebisa mungkin harus

ditempatkan pada blok berikutnya. Menggunakan aturan ini, banyak konfigurasi diperlukan tanpa di-explore dan sebuah solusi dapat ditemukan lebih cepat.

Posted in: AI