Algoritma Pencarian

Pencarian adalah suatu proses untuk menemukan sesuatu. Pencarian tidak hanya mencari benda, tetapi dapat berupa pencarian penyelesaian masalah, pencarian ongkos terkecil, pencarian jalur tenyaman, dan lain-lain dengan tujuan yang sama yaitu mencapai tujuan. Beberapa algoritma pencarianpun berkembang dan berikut beberapa istilah yang sering disebutkan dalam algoritma pencarian:

• Search Space: Ruang pencarian mewakili satu set solusi yang mungkin, yang mungkin dimiliki suatu sistem.
• Start State: Kondisi suatu agen saat memulai pencarian.
• Goal Test: Fungsi untuk menguji apakah tujuan telah tercapai atau belum.
• Search Tree: Sebuah representasi pohon dari masalah pencarian.
• Actions: Daftar isi beberapa aksi yang dapat dilakukan.
• Transition Model: Deskripsi tentang apa yang dapat dilakukan setiap tindakan.
• Path Cost: Ini adalah fungsi yang menetapkan ongkos numerik untuk setiap jalur.
• Solution: Ini adalah urutan tindakan yang mengarah dari node awal ke node tujuan.
• Optimal Solution: Jika suatu solusi memiliki ongkos terendah di antara semua solusi.
• Completeness: Sebuah algoritma pencarian dikatakan lengkap jika menjamin untuk mengembalikan solusi jika setidaknya ada solusi untuk setiap input acak.
• Optimality: Jika solusi yang ditemukan untuk suatu algoritma dijamin menjadi solusi terbaik (biaya jalur terendah) di antara semua solusi lainnya, maka solusi untuk tersebut dikatakan sebagai solusi optimal.
• Time Complexity: Kompleksitas waktu adalah ukuran waktu bagi suatu algoritma untuk menyelesaikan tugasnya.
• Space Complexity: Ini adalah ruang penyimpanan maksimum yang diperlukan pada setiap titik selama pencarian, sebagai kompleksitas masalah.

Jenis Algoritma Pencarian

Jenis algoritma pencarian secara umum dapat dibagi menjadi dua yaitu Uninformed atau Blind Search dan Informed atau Dicerning Search. Dalam Bahasa Indonesia dapat diterjemahkan menjadi pencarian tidak diberi tahu dan pencarin yang diberi tahu, pencarian buta dan pencarian mengenal, pencarian tanpa diarahkan dan pencarian diarahkan, atau pencarian dengan petunjuk atau pencarian dengan petunjuk.

Uninformed Search

Breadth First Search

Breadth artinya melebar, disini induknya dulu baru ke anak-anaknya.

Depth First Search

Depth artinya mendalam, disini 1 keluarga dulu induk dan anak-anaknya baru ke keluarga berikutnya.

Depth Limited Search

Kedalamannya dibatasi contohnya kita tidak akan menginterogasi anak-anaknya.

Uniform Cost Search

Dipilih jalur terpendek terlebih dahulu dan selanjutnya.

Bidirectional Search

Bila terdapat multi-processing maka dapat melakukan 2 pencarian sekaligus.

Informed Search

Best First Search

Diketahui peta jalur dari Jalan Bulu Indah ke Rektorat UNUD.

Diketahui jarak vektor masing-masing jalan ke Rektorat UNUD

Dibuka dan dimulai dari titik awal JL Bulu Indah.

Titik awal ditutup dan dibuka titik berikutnya.

Titik dengan vektor terdekat ditutup dan dibuka titik lanjutannya.

Titik yang baru dibuka tetap dibanding dengan titik yang masih dibuka lalu ditutup titik dengan jarak vektor terkecil.

Proses terus diulang, dan akhirnya jalur ditentukan

A First Search

Kelemahan dari Best First Search adalah tidak mempertimbangkan ongkos antar jalan. Contohnya, bagaimana kalau terjadi macet di Imam Bonjol? Walaupun secara vektor merupakan jarak terdekat, tetapi melewati jalur tersebut akan memakan waktu yang paling lama.

Oleh karena itu A First Search juga mempertimbangkan ongkos masing-masing jalur dengan cara yang hampir sama dengan Best First Search yaitu open pada titik awal.

Close titik awal dan open titik-titik berikutnya.

Perbedaannya ongkos untuk mencapai titik tersebut ditambahkan tetapi tetap hasil terkecil dipilih yaitu tidak melewati Imam Bonjol karena macet.