Algoritma Pencarian: Pengertian, Karakteristik, dan Jenis-Jenisnya

 Pengertian Algoritma Pencarian

Dalam ilmu komputer, algoritma pencarian adalah algoritma yang dirancang untuk memecahkan masalah pencarian.


Algoritma pencarian bekerja untuk mengambil informasi yang disimpan dalam struktur data tertentu, atau dihitung dalam ruang pencarian domain masalah, baik dengan nilai diskrit atau kontinu.

Karakteristik Algoritma Pencarian


Berikut adalah empat sifat penting dari algoritma pencarian untuk membandingkan efisiensi dari sebuah algoritma:


Completeness: Algoritma pencarian dikatakan lengkap jika menjamin untuk mengembalikan solusi jika setidaknya ada solusi untuk setiap input random.

Optimality: Jika solusi yang ditemukan untuk suatu algoritma dijamin sebagai solusi terbaik (biaya jalur terendah) di antara semua solusi lainnya, maka solusi untuk tersebut dikatakan sebagai solusi optimal.

Time Complexity: Ukuran waktu bagi suatu algoritma untuk menyelesaikan tugasnya.

Space Complexity: Ruang penyimpanan maksimum yang diperlukan pada setiap titik selama pencarian, sebagai kompleksitas masalah.

Jenis-jenis Algoritma Pencarian

Berdasarkan jenis operasi pencarian, algoritma ini umumnya diklasifikasikan menjadi dua jenis kategori:

  1. Sequential Search: algoritma ini membandingkan setiap elemen array satu per satu secara berurutan, mulai dari elemen pertama, sampai elemen yang dicari ditemukan atau sampai semua elemen diperiksa. Jika elemen ditemukan, ia mengembalikan indeksnya, jika tidak -1. Contoh: Linear Search.

    Sumber: geeksforgeeks.org
  2. Interval Search: Algoritma ini digunakan untuk mencari elemen tertentu pada array/list dengan elemen yang berurutan yang mana elemen yang berada di dalam array harus diurutkan terlebih dahulu. Algoritma pencarian ini bekerja berdasarkan prinsip menemukan nilai tengah (M) pada array kemudian membagi menjadi dua bagian. Selanjutnya menentukan apakah nilai yang dicari lebih kecil (L) atau lebih besar (H) dari nilai yang ingin dicari. Apabila ditemukan kecocokan nilai maka akan mengembalikan output, jika tidak pencarian akan terus berlanjut hingga akhir dari pembagian jumlah elemen tersebut. Contoh: Binary Search.

Komentar

Posting Komentar

Postingan populer dari blog ini

Algoritma A* (A Star): Pengertian, Cara Kerja, dan Kegunaannya

Gambar
  Pengertian Algoritma A* (A star) Algoritma A* (A Star) adalah algoritma pencarian yang digunakan untuk menemukan jalur terpendek antara titik awal dan akhir. Algoritma ini sering digunakan untuk penjelajahan peta guna menemukan jalur terpendek yang akan diambil. Cara Kerja Algoritma A* A* menggunakan  Best First Search (BFS) dan menemukan jalur dengan biaya terkecil (least-cost path) dari node awal (initial node) yang diberikan ke node tujuan (goal node). Algoritma ini menggunakan fungsi heuristik jarak ditambah biaya (biasa dinotasikan dengan f(x)) untuk menentukan urutan di mana search-nya melalui node-node yang ada pada tree. Notasi yang dipakai oleh algoritma A* adalah sebagai berikut: f(n) = g(n) + h(n) dimana f(n)  = biaya estimasi terendah g(n)  = biaya dari node awal ke node n h(n)  = perkiraan biaya dari node n ke node akhir Sumber: wikipedia.org Adapun langkah-langkah yang dilakukan oleh algoritma A* adalah sebagai berikut: Inisialisasi OPEN LIST Letakkan simpul awal pada O
Baca selengkapnya

Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya.

  Pengertian Graph Graph adalah jenis struktur data umum yang susunan datanya tidak berdekatan satu sama lain (non-linier). Graph terdiri dari kumpulan simpul berhingga untuk menyimpan data dan antara dua buah simpul terdapat hubungan saling keterkaitan. Struktur Data Graph: Pengertian, Jenis, dan Kegunaannya Simpul pada graph disebut dengan verteks (V), sedangkan sisi yang menghubungkan antar verteks disebut edge (E). Pasangan (x,y) disebut sebagai edge, yang menyatakan bahwa simpul x terhubung ke simpul y. Fungsi dan Kegunaan Graph Fungsi dan kegunaan graph di antaranya: Graph digunakan untuk merepresentasikan aliran komputasi. Digunakan dalam pemodelan grafik. Graph dipakai pada sistem operasi untuk alokasi sumber daya. Google maps menggunakan graph untuk menemukan rute terpendek. Graph digunakan dalam sistem penerbangan untuk optimasi rute yang efektif. Pada state-transition diagram, graph digunakan untuk mewakili state dan transisinya. Di sirkuit, graph dapat digunakan untuk mewak
Baca selengkapnya