pelacakan n pencarian

Metode Pencarian dan Pelacakan

Metode pencarian dan pelacakan adalah hal penting dalam kecerdasan buatan atau kita sebut dengan AI. Dalam kecerdasan buatan lebih di fokuskan dalam hal pencarian, karena AI harus dapat mencari solusi / jawaban atas suatu permasalahn dalam sekumpulan kemungkinan ruang keadaan.

Terdapat 4 kriteria yang dapat mengukur dalam hal pencarian dalam kecerdasan buatan :
1) Completeness
2) Time complexity
3) Space Complexity
4) Optimality

Di dalam kecerdasan buatan kita mengenal 2 metode pencarian dan pelacakan diantaranya adalah :

1) Pencarian buta(Blind Search) : Dalam metode pencarian buta ini dibagi menjadi 2 yaitu :
Breadth - First Search : Metode ini akan mulai mencari dari node yang paling kiri, kemudian berpindah ke-node se-level dengannya, dan berulang - ulang trus hingga menemukan solusi yang dimaksud.
Depth - Fisth Search : Metode ini dimulai dari semua node-node anaknya kemudian berpindah ke node-node se-level nya.

- Keuntungan metode Breadth-First Search adalah : pasti menemukan solusi yang dicari, tidak akan mengalami jalan buntu / tidak menemukan solusi.

- Kelemahan metode Breadth-First Search adalah : memerlukan memori yang cukup besar, karena metode ini mengecek keseluruhan node yang ada dan membutuhkan waktu yang lebih untuk mengecek semua node yang ada tersebut.

2) Pencarian terbimbing (Heuristic search) : Dalam metode pencarian terbimbing atau kita sebut Heuristic search terbagi menjadi 4 macam yaitu :
- Pembangkit & Pengujian
- Hill Climbing
- Best First Search (BFS)
- Simulated Annealing

Pembangkit & Pengujian

Pembangkit & Pengujian : Pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Terdapat kelemahan dalam metode ini :
- Perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian
- Membutuhkan waktu yang cukup lama dalam pencariannya

Hill Climbing

Hill Climbing adalah metode ini hampir sama dengan metode pembangkitan & pengujian, namun memiliki perbedaan dalam hal proses pengujian dilakukan. Hill Climbing menggunakan fungsi heuristik dalam hal pencarian.

Algoritma Simple Hill Climbing :
1.Mulai dari keadaan awal, lakukan pengujian: jika merupakan tujuan, maka berhenti; dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2.Kerjakan langkah-langkah berikut sampai solusinya ditemukan, atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang:
3.Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.
4.Evaluasi keadaan baru tersebut.
5.Jika keadaan baru merupakan tujuan, keluar.
6.Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7.Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Algoritma Steepest Ascent Hill Climbing :
Steepest-ascent hill climbing sebenarnya hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristik terbaik. Dalam hal ini urutan penggunaan operator tidak menentukan penemuan solusi.