SEARCH

Untuk kali ini saya akan menulis informasi yang berisi rangkuman materi pertemuan 4 tentang Pencarian yang terdiri dari :  

1. Konsep Pencarian

2. Teknik Pencarian dan Penjelasannya

3. Karakteristik Masalah

4. Teknik Search

5. Metode Breadth-First-Search

6. Metode Depth-Fisrt-Search

• KONSEP PENCARIAN

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

1. Completeness

2. Time complexity

3. Space complexity

4. Optimality

Konsep pencarian dikatakan penting untuk perencanaan karena dalam sebuah permainan akan menentukan apa yang harus dilakukan, dimana setiap state menggambarkan kemungkinan posisi pada suatu saat. Konsep pencarian adalah bagian dari kesimpulan, dimana setiap state menggambarkan hipotesis dalam sebuah rangkaian deduktif

• TEKNIK PENCARIAN DAN PENJELASANNYA

Pada saat menentukan suatu keberhasilan pada sistem kecerdasan yaitu melalui kesuksesan pencarian  dan pencocokan. Adapun  2 (dua)  teknik pencarian / pelacakan yang dipakai,  yaitu:

1.    Pencarian  Buta  (Blind search)

Blind Search atau Uninformed Search secara umum mengartikan bahwa saat proses pencarian kita tidak memiliki clue/hint apakah hasil yang ditemukan lebih baik daripada yang lainnya, sehingga kita tidak mengetahui apakah hasil dari eksplorasi tersebut bermanfaat secara maksimal atau tidak.

Pendekatan ini kurang efisien dan merupakan pemaksaan (brute force search). Dalam memecahkan masalah yang sangat besar sejumlah keadaan baru muncul, sehingga alternatif yang perlu dipertimbangkan pun menjadi lebih banyak. Akibatnya diperlukan waktu yang lama untuk menemukan 1 solusi.

2.    Pencarian Terbimbing (Heuristic search).

Pencarian heuristik adalah teknik pencarian AI yang menggunakan heuristik untuk pergerakannya(berpindah). Heuristik sendiri merupakan aturan praktis yang mungkin mengarah pada solusi. Heuristik membantu mengurangi jumlah alternatif dari bilangan eksponensial menjadi bilangan polinomial. Secara umum, istilah heuristik digunakan untuk saran yang sering efektif, namun tidak  dalam setiap kasus. Dalam pencarian heuristik setiap state diberi sebuah “heuristic value “(h-value) yang digunakan pencarian dalam memilih  langkah terbaik selanjutnya.

• KARAKTERISTIK MASALAH

Pencarian heuristic adalah metode yang sangat umum yang dapat diterapkan dalam begitu banyak masalah, meliputi begitu banyak variasi teknik yang spesifik, dimana masing-masing efektif untuk penyelesaian masalah tertentu yang lebih spesifik.

Untuk memilih metode mana/kombinasi metode manayang akan digunakan untuk menyelesaikan masalah, penting untuk menganalisa masalah pada beberapa dimensi kunci atau karakteristik sebagai berikut :

1. Dapatkah masalah disederhanakan kedalam kelompok terpisah yang lebih kecil atau subprogram yang lebih mudah ?

2. Dapatkah satu tahap penyelesaian solusi diabaikan atau setidaknya tidak dilakukan jika terbukti tidak layak ?

3. Apakah ruang lingkup masalah dapat diprediksi ?

4. Apakah sejumlah pengatahuan mutlak diperlukan untuk menyelesaikan masalah atau pengetahuan hanya diperlukan untuk membatasi pencarian ?

5. Dapatkah komputer yang diberikan permasalahan langsung memberikan solusi atau pemecahan masalah memerlukan interaksi antara komputer dan manusia ?

• TEKNIK SEARCH

1. Arah search

Dapat dilakukan :

Maju, bermula dari keadaan awal

(start state) Mundur, diawali dari keadaan tujuan (goal state)

2. Topologi proses search

Ada dua macam penggambaran problem, yaitu dalam

bentuk :

a. Pohon (tree)

Untuk menghindari kemungkinan adanya proses pelacakan suatu node secara berulang,maka digunakan struktur pohon. Struktur pohon digunakan untuk menggambarkan keadaan secara hirarkis. Pohon juga terdiri dari beberapa node yaitu Node Akar Menunjukkan keadaan awal yang biasanya merupakan topik atau objek. Node akar mempunya beberapa percabangan yang sering disebut “Anak” dan node yang tidak mempunyai anak sering disebut node “Daun” yang menunjukkan akhir dari suatu pencarian dapat berupa (goal) atau jalan buntu (dead end)

b.Graf (graph) : Graf berarah dan Graf tidak berarah

Graph Terdiri dari node-node yang menunjukkan keadaan, yaitu keadaan awal dan keadaan baru yang akan dicapai dengan menggunakan operator. Node-node dalam graph keadaan saling dihubungkan dengan menggunakan arc (busur) yang diberi panah untuk menunjukkan arah dari suatu keadaan ke keadaan berikutnya. Metode pencarian akan berusaha menemukan kombinasi dari item-item yang dimulai dari state menuju ke goal

• Metode Breadth-First-Search

Pada metode Breadth-First Search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai  dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian  pula  dari kiri  ke kanan hingga ditemukannya solusi.

Kelebihan Breadth-First-Search :

1. Breadth-First-Search tidak akan terjebak untuk menelusuri satu jalur tertentu saja

2. Jika solusi memang ada, maka dijamin Breadth-First-Search akan menemukannya.

Kekurangan Breadth-First-Search :

1. Memerlukan memori lebih besar karena harus menyimpan semua simpul dari tree yang ditelusuri

2. Harus menelusuri semua bagian tree pada level yang sama sebelum beralih ke level berikutnya.

Contoh Breadth-First Search.Dapat dilihat pada contoh ini bahwa gerakan kebawah meproses tingkat demi tingkat hingga tujuannya tercapai. Maka urutan proses seaching Bread-First Search ditunjukkan pada gambar adalah dimulai  dari S-A-D-B-D-A-E-C-E-E-B-B-F-D-F-B-F-D-E-A-C dan berakhir pada G.

• Metode Depth-Fisrt-Search

Metode Depth-First Search ini akan dilakukan pada proses pencarian semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level  yang lebih tinggi. Proses ini  akan terus diulangi hingga mendapatkan solusi.

Kelebihan Depth-First-Search :

1. Depth-First-Search memerlukan ruang memori lebih kecil karena hanya menyimpan simpul-simpul dari path/jalur yang sedang dikerjakan.

2. Dapat menemukan solusi tanpa menelusuri terlalu banyak ruang search.

Kekurangan Depth-First-Search :

1. Ada kemungkinan terjebak pada satu jalur sampai terlalu jauh, bahkan selamanya, sebelum jalur tsb mendapatkan stata yang tidak lagi memiliki successor (buntu).

2. Mungkin menemukan jalur panjang ke solusi pada satu bagian dari tree, sementara jalur terpendek tersedia pada bagian lain tree yang belum ditelusuri.

Contoh Depth-First Search. Contoh ini merupakan depth-first karena hanya satu alternatif dipilih dan didesak pada setiap simpul sampai tujuan tercapai atau simpul tercapai bila gerak yang jauh lebih ke bawah tidak mungkin. Pada saat gerak yang jauh lebih kebawah itu tidak mungkin, maka dalam pencariannya dimulai kembali pada simpul nenek moyang yang terdekat memiliki anak-anak yang tidak diselidiki. Pada urutan proses seaching Depth-First Search ditunjukkan pada gambar adalah dimulai  dari S-A-B-C-E-D-F- dan berakhir di G.