Metode Pencarian dan Pelacakan 1

Metode Pencarian dan Pelacakan 1 Perkuliahan Minggu ke-4




4.1 Metode Pencarian Buta (Blind Search)

4.1.1 Breadth First Search

Breadth-first search (BFS) melakukan proses searching pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses searching pada node di level berikutnya.
Breadth-first search adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada ras d+1.
Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi. Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya. Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.

4.1.2 Depth First Search

Depth-first search (DFS) adalah proses searching sistematis buta yang melakukan ekpansi sebuah path (jalur) menuju penyelesaian masalah sebelum melakukan ekplorasi terhadap path yang lain. Proses searching mengikuti sebuah path tunggal sampai menemukan goal atau dead end. Apabila proses searching menemukan dead-end, DFS akan melakukan penelusuran balik ke node terakhir untuk melihat apakah node tersebut memiliki path cabang yang belum dieksplorasi. Apabila cabang ditemukan, DFS akan melakukan cabang tersebut. Apabila sudah tidak ada lagi cabang yang dapat dieksplorasi, DFS akan kembali ke node parent dan melakukan proses searching terhadap cabang yang belum dieksplorasi dari node parent sampai menemukan penyelesaian masalah.
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).

4.2 Metode Pencarian Heuristik

4.2.1 Generate And Test

   Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana
dari semua pendekatan yang akan dibicarakan.

 Pendekatan ini meliputi langkah–langkah sebagai berikut :

1. Buatlah/bangkitkan sebuah solusi yangmemungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titikkhusus dalam ruang problema.
2.  Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
3. Jika telah diperoleh sebuah solusi, langkah– langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi–solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya, (bila ada). Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama. Metode generate and test ini kurang efisien untuk masalah yang besar atau kompleks

4.2.2 Hill Climbing

  Hill climbing (mendaki bukit) merupakan salahsatu variasi metode buat dan uji (generate and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk memutuskan arah gerak dalam ruang pencarian (search). Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak.  Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :

1. . Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya. Pengantar Inteligensia Buatan – Heuristic Searching 3/8
2. Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru. 
3. Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :

•    Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi,
• berhentilah Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.
• Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.
• Kembalilah ke langkah 2. 

Masalah-masalah yang mungkin timbul pada prosedur Hill Climbing :

- Pengantar Inteligensia Buatan – Heuristic Searching 4/8
- Maksimum lokal adalah suatu keadaan yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari suatu keadaan lain yang jauh letaknya darinya.
- Daratan (Plateau) adalah suatu daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan tetangganya memiliki nilai yang sama.
- Punggung (Ridge) adalah suatu daerah ruang pencarian (search) yang lebih tinggi daripada
daerah sekitarnya, namun tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.

Solusinya:

- Melakukan langkah balik (backtracking) ke simpul yang lebih awal dan mencoba bergerak
ke arah yang lain.
- Melakukan lompatan besar ke suatu arah untuk mencoba bagian ruang pencarian yang baru.
Pengantar Inteligensia Buatan – Heuristic Searching 5/8
- Menerapkan dua atau lebih aturan sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah sekaligus.

Sumber : http://solikhaton.blogspot.co.id/2014/08/makalah-membahas-tentang-algoritma.html

http://andikunc02.blogspot.co.id/2010/04/kecerdasan-buatan.html