Memahami jenis-jenis algoritma pencarian itu penting adanya. Algoritma pencarian bernilai krusial karena memecahkan berbagai masalah dalam kecerdasan buatan. Ada berbagai algoritma pencarian di AI.
Baca Juga : Cara Kerja Algoritma Instagram Terbaru Perlu Diketahui
Tulisan ini akan membawa kalian mempelajari algoritma pencarian, termasuk kepentingan dan propertinya. Ini juga akan memberikan klasifikasi algoritma pencarian dan mengidentifikasi algoritma pencarian populer di AI.
Lebih Mengerti tentang Jenis-jenis Algoritma Pencarian
Sebelum masuk lebih detail membahas jenis-jenis algoritma pencarian, kita akan mengulas dulu tentang definisi algoritma pencarian itu sendiri. Hal ini penting agar memiliki pemahaman yang serupa dalam membahas tema yang sama.
Algoritma pencarian merupakan algoritma yang membantu dalam menyelesaikan permasalahan pencarian. Masalah pencarian terdiri dari ruang pencarian, keadaan awal, dan keadaan tujuan.
Tanpa algoritma ini, mesin dan aplikasi AI tidak dapat mengimplementasikan fungsi pencarian dan menemukan solusi yang tepat. Inilah mengapa pada zaman ini, kehadiran algoritma begitu penting adanya.
Mengapa Kehadiran Algoritma Pencarian Penting Adanya
Untuk lebih menjawab tentang pentingnya algoritma pencarian, poin-poin berikut akan menjelaskan bagaimana dan mengapa algoritma pencarian penting dalam kecerdasan buatan. Nantinya, penjelasan ini juga jadi pengantar untuk lebih mengenal jenis-jenis algoritma pencarian lebih rinci.
Pemecahan Masalah
Algoritma pencarian meningkatkan pemecahan masalah dalam kecerdasan buatan. Tentunya, melalui mekanisme pencarian logis seperti definisi masalah, tindakan, dan ruang pencarian.
Pemrograman Pencarian
Banyak tugas AI yang dapat diprogram dalam istilah pencarian. Ini meningkatkan perumusan solusi untuk masalah tertentu.
Agen Berbasis Tujuan
Algoritma pencarian meningkatkan pengoperasian agen berbasis tujuan yang efektif. Agen-agen ini memecahkan masalah dengan mencari rangkaian tindakan paling ideal yang dapat memberikan solusi terbaik terhadap suatu masalah.
Berikut Ini Properti Algoritma Pencarian
Aspek lainnya yang juga perlu kalian pelajari adalah properti algoritma pencarian. Algoritma pencarian memiliki properti utama sebagai berikut:
Kelengkapan
Suatu algoritma pencarian dapat dikatakan lengkap jika algoritma tersebut memberikan solusi untuk masukan tertentu. Utamanya, ketika terdapat setidaknya satu solusi untuk masukan tersebut.
Optimalitas
Algoritma pencarian juga dicirikan oleh solusi optimal. Ini adalah solusi terbaik yang diberikan oleh jenis-jenis algoritma pencarian dengan biaya jalur terendah.
Kompleksitas Waktu
Algoritma ini memiliki waktu maksimum yang dibutuhkan untuk menyelesaikan suatu tugas atau memberikan solusi. Waktu yang dibutuhkan biasanya didasarkan pada kompleksitas tugas.
Kompleksitas Ruang
Algoritma memiliki memori atau ruang penyimpanan maksimum yang diperlukan saat melakukan operasi pencarian. Memori ini juga didasarkan pada kompleksitas tugas.
2 Cara Kerja dari Algoritma Pencarian
Kecerdasan buatan dimungkinkan melalui agen AI. Agen-agen ini melakukan tugas-tugas untuk mencapai tujuan tertentu dan menetapkan tindakan yang dapat menghasilkan tujuan yang diinginkan. Rangkaian tindakan tersebut memberikan solusi terhadap permasalahan tersebut.
Agen AI menemukan solusi terbaik untuk masalah tersebut dengan mencari semua kemungkinan alternatif atau solusi. Di sini algoritma pencarian berfungsi krusial dalam keberlangsungan proses pencarian.
Algoritma pencarian bekerja dalam dua fase utama yaitu mendefinisikan masalah dan mencari di ruang pencarian. Meski ada beragam jenis-jenis algoritma pencarian, fase-fase tersebut selalu dilalui dalam melangsungkan proses pencarian.
Mendefinisikan Masalahnya
Sebelum merumuskan masalah, berbagai faktor perlu didefinisikan agar algoritma pencarian dapat melakukan tindakan yang diperlukan. Mendefinisikan faktor-faktor ini memberikan dasar untuk mencari dan memberikan solusi. Berikut ini adalah faktor-faktor yang perlu didefinisikan:
- Status awal: Ini adalah status awal saat pencarian dimulai.
- Ruang keadaan: Ini semua kemungkinan keadaan yang dapat dicapai dari keadaan awal melalui serangkaian tindakan.
- Tindakan: Ini adalah langkah, aktivitas, atau operasi yang dilakukan oleh agen AI di negara bagian tertentu.
- Status tujuan: Ini adalah titik akhir atau keadaan yang diinginkan.
- Tes tujuan: Ini adalah tes yang dilakukan untuk menentukan apakah suatu keadaan tertentu merupakan keadaan tujuan.
- Biaya jalur: Ini adalah biaya yang terkait dengan jalur tertentu yang diambil oleh agen.
Mencari di Ruang Pencarian
Setelah menentukan faktor-faktor yang dijelaskan di atas, agen menggunakan algoritma pencarian untuk melakukan pencarian di ruang pencarian. Ruang pencarian adalah konfigurasi abstrak yang terdiri dari pohon pencarian solusi yang mungkin.
Pohon pencarian digunakan untuk mengonfigurasi serangkaian tindakan. Keadaan awal dikonfigurasi sebagai akar pohon pencarian. Cabang adalah tindakan sedangkan node adalah hasil dari tindakan.
Ketika kita mempunyai masalah tertentu di AI, algoritma pencarian akan mengidentifikasi keadaan awal, ruang keadaan, tindakan, keadaan tujuan, dan biaya jalur. Dari keadaan awal, serangkaian tindakan akan dilakukan saat jenis-jenis algoritma pencarian yang bekerja mencari keadaan tujuan.
Untuk setiap keadaan yang dicapai oleh agen AI, algoritma pencarian akan melakukan tes tujuan untuk menentukan apakah keadaan tersebut merupakan keadaan yang diinginkan. Jika keadaan tertentu yang dicapai oleh agen bukan merupakan keadaan tujuan, maka algoritma pencarian akan terus mencari sampai keadaan tujuan tercapai.
2 Jenis Algoritma Pencarian Dibagi Menjadi 2 Kategori
Algoritma pencarian dapat dibagi menjadi dua kategori besar, yakni algoritma pencarian tanpa informasi dan algoritma pencarian informasi. Jelas ada perbedaan mendasar, dan berikut uraian mendetailnya.
Algoritma Pencarian tanpa Informasi (Uninformed Search)
Algoritma ini disebut juga algoritma buta. Hal ini karena jenis algoritma ini tidak memiliki informasi tambahan yang dapat membantunya mencapai tujuan akhir selain informasi yang diberikan dalam definisi masalah. Algoritma ini selanjutnya dapat dikategorikan ke dalam algoritma berikut:
- Pencarian yang Mengutamakan Luas (Breadth-first search)
Di antara jenis-jenis algoritma pencarian yang lain, ini adalah algoritma yang digunakan untuk mencari struktur data grafik atau pohon. Ini dimulai dari akar pohon atau kunci pencarian. Berikutnya, akan melintasi semua node tetangga di tingkat kedalaman saat ini sebelum berlanjut ke node yang ada di tingkat kedalaman berikutnya.
- Pencarian yang Mengutamakan Kedalaman (Depth-first search)
Ini adalah algoritma yang digunakan untuk mencari struktur data grafik atau pohon, yang mana, berbeda dengan pencarian luas pertama, pencarian ini dimulai dari simpul akar. Ini melintasi node cabang dan kemudian mundur. Struktur data pencarian ini menggunakan konsep LIFO (last in first out).
- Pencarian Biaya Seragam (Uniform cost search)
Algoritma ini berbeda dari jenis-jenis algoritma pencarian yang mengutamakan luas dan mengutamakan kedalaman dalam hal mereka mempertimbangkan biaya. Ketika terdapat jalur yang berbeda untuk mencapai tujuan yang diinginkan, solusi optimal dari algoritma biaya seragam adalah solusi yang berhubungan dengan biaya paling sedikit.
Algoritma Pencarian Informasi (Informed Search)
Ini adalah algoritma heuristik yang terdiri dari definisi masalah dan informasi tambahan yang membantu mencapai keadaan tujuan yang diinginkan. Di antara jenis-jenis algoritma pencarian lainnya, algoritma ini lebih baik dalam memecahkan masalah yang kompleks dibandingkan algoritma yang tidak mempunyai informasi.
Algoritma pencarian informasi selanjutnya dapat dikategorikan ke dalam algoritma berikut:
- Pencarian Serakah (Greedy Search)
Dalam algoritma pencarian serakah, node terdekat dengan node tujuan diperluas. Faktor kedekatan dihitung menggunakan fungsi heuristik h(x). h(x) merupakan perkiraan jarak antara satu node dengan node akhir atau tujuan.
Semakin rendah nilai h(x) maka semakin dekat titik akhir dengan titik akhir. Ketika jenis-jenis algoritma pencarian serakah sedang mencari jalur terbaik menuju node tujuan, ia akan memilih node dengan nilai serendah mungkin.
- Pencarian Pohon A*
Algoritma ini menggabungkan atribut dari algoritma biaya seragam dan algoritma serakah. Di sini, heuristik hanyalah penggabungan dari biaya pencarian serakah (h(x)) dan biaya dalam algoritma biaya seragam (g(x)). Biaya kumulatif dilambangkan dengan f(x).
h(x) dikenal sebagai biaya maju sedangkan g(x) adalah biaya mundur (backward cost). Biaya maju memperkirakan jarak antara node saat ini dan node tujuan. Biaya mundur digunakan untuk menentukan biaya keseluruhan (overall cost) antara sebuah node dan node akar.
Jenis-jenis algoritma pencarian pohon A* akan optimal ketika biaya penerusan (h (x)) lebih kecil atau sama dengan biaya aktual (h* (x)) untuk semua node. Ini disebut properti penerimaan algoritma pohon A*. Strateginya adalah memilih node dengan nilai total biaya terendah (f(x)).
- Pencarian Grafik A*
Kelemahan utama dari algoritma pohon A* adalah adanya pemborosan waktu akibat eksplorasi ulang cabang yang awalnya dieksplorasi. Kelemahan ini telah diatasi dengan algoritma grafik A*, yang mengonfigurasi aturan yang mencegah eksplorasi ulang cabang yang awalnya dieksplorasi.
Solusi optimal dalam algoritma grafik A* dicapai ketika biaya maju dari dua node yang berurutan lebih kecil atau sama dengan backward cost-nya. Properti ini disebut sebagai properti konsistensi dari algoritma ini.
Baca Juga : Pengertian Factory Reset beserta Cara Melakukannya
Algoritma memberikan solusi pencarian melalui serangkaian tindakan yang mengubah keadaan awal menjadi keadaan tujuan. Agen AI untuk mencapai tujuan melalui penilaian skenario dan alternatif dibantu jenis-jenis algoritma pencarian yang relevan.
