Dalam ilmu komputer, sebuah algoritme
pencarian dijelaskan secara luas adalah sebuah algoritme yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritme yang dipelajari oleh ilmuwan komputer adalah algoritme
pencarian. Himpunan semua kemungkinan solusi dari sebuah masalah disebut ruang
pencarian. Algoritme
pencarian brute-force atau
pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif
pada ruang
pencarian, sedangkan algoritme
pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang
pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam
pencarian.
Sebuah algoritme
pencarian uninformed adalah algoritme yang tidak mempertimbangkan sifat alami dari permasalahan. Oleh karena itu algoritme tersebut dapat diimplementasikan secara umum, sehingga dengan implementasi yang sama dapat digunakan pada lingkup permasalahan yang luas, hal ini berkat abstraksi. Kekurangannya adalah sebagian besar ruang
pencarian adalah sangat besar, dan sebuah
pencarian uninformed (khususnya untuk pohon) membutuhkan banyak waktu walaupun hanya untuk contoh yang kecil. Sehingga untuk mempercepat proses, kadang-kadang hanya
pencarian informed yang dapat melakukannya.
=
Algoritme
pencarian list mungkin adalah algoritme
pencarian paling dasar. Tujuannya adalah mencari sebuah elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi yang terkait dengan kunci). Oleh karena hal ini adalah masalah yang lazim dalam ilmu komputer, kompleksitas komputasi algoritme-algoritme tersebut telah dipelajari dengan baik. Algoritme paling sederhana adalah
pencarian linear, yang secara sederhana melihat setiap elemen dari list secara berurutan. Waktu pengerjaan algoritme ini adalah O(n), dimana n adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. Algoritme
pencarian list yang lebih canggih adalah
pencarian biner; waktu pengerjaannya adalah O(log n). Waktu pengerjaannya jauh lebih baik daripada
pencarian linear untuk list yang memiliki data banyak, tetapi sebelum dilakukan
pencarian list terlebih dahulu harus terurut (lihat algoritme pengurutan) dan juga harus dapat diakses secara acak (pengaksesan acak).
pencarian interpolasi adalah lebih baik dari
pencarian biner untuk list terurut yang sangat besar dan terdistribusi merata. Algoritme Grover adalah sebuah algoritme kuantum yang menawarkan percepatan kuadrat dibandingkan
pencarian linear klasik untuk list tak terurut.
Tabel hash juga digunakan untuk
pencarian list, hanya memerlukan waktu yang konstan untuk mencari pada kasus rata-rata, tetapi memiliki overhead ruang yang lebih dan pada kasus terburuk waktu pengerjaannya adalah O(n).
pencarian lain yang berdasarkan struktur data khusus, menggunakan pohon
pencarian biner yang self-balancing (self-balancing binary search tree) dan membutuhkan waktu
pencarian O(log n); hal ini dapat dipandang sebagai pengembangan dari ide utama
pencarian biner untuk memungkinkan penyisipan dan penghapusan yang cepat. Lihat array asosiatif untuk diskusi lanjut dari struktur data
pencarian list.
Sebagian besar algoritme
pencarian, seperti
pencarian linear,
pencarian biner dan pohon
pencarian biner yang self-balancing, dapat dikembangkan dengan sedikit tambahan cost untuk menemukan semua nilai yang kurang dari atau lebih dari sebuah kunci, operasi ini disebut
pencarian jangkauan (range search). Pengecualian ada pada tabel hash, yang tidak dapat melakukan
pencarian tersebut secara efisien.
=
Algoritme
pencarian pohon adalah jantung dari teknik-teknik
pencarian. Algoritme tersebut mencari node dari pohon, terlepas apakah pohon tersebut eksplisit atau implisit (dibangkitkan saat pengerjaan). Prinsip dasarnya adalah sebuah node diambil dari sebuah struktur data, suksesornya diperiksa dan ditambahkan pada struktur data. Dengan memanipulasi struktur data, pohon ditelusuri dalam urutan yang berbeda-beda, ditelusuri dari satu tingkat ke tingkat berikutnya (
pencarian Breadth-first) atau mengunjungi node pucuk terlebih dahulu kemudian lacak balik/backtracking (
pencarian Depth-first). Contoh lain dari
pencarian pohon antara lain
pencarian iterative-deepening,
pencarian berbatas kedalaman,
pencarian dwiarah dan
pencarian uniform-cost.
=
Banyak permasalahan dalam teori graf dapat dipecahkan dengan memanfaatkan algoritme
pencarian, seperti algoritme Dijkstra, algoritme Kruskal's, algoritme tetangga terdekat, dan algoritme Prim.-first|
pencarian iterative-deepening]],
pencarian berbatas kedalaman,
pencarian dwiarah dan
pencarian uniform-cost.
Pada
pencarian informed, sebuah heuristik yang khusus untuk permasalahan tertentu digunakan sebagai pedoman. Sebuah heuristik yang baik dapat membuat sebuah
pencarian informed bekerja secara dramatis melebihi
pencarian uninformed.
Terdapat beberapa algoritme
pencarian list informed yang dikenali. Salah satu anggota dari algoritme tersebut adalah sebuah tabel hash dengan sebuah fungsi hashing, yaitu algoritme dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritme informed adalah mengeksplore pohon. Termasuk di dalamnya adalah
pencarian Breadth-first, dan A*. Sebagaimana algoritme uninformed, algoritme informed dapat dikembangkan untuk bekerja pada graf.
Dalam permainan seperti catur, terdapat sebuah pohon permainan dari semua kemungkinan gerak dari kedua pemain dan konfigurasi hasil dari papan catur, dan kita dapat mencari pada pohon tersebut untuk menemukan strategi permainan yang efektif. Tipe permasalahan ini memiliki karakteristik unik yang mengharuskan kita memperhatikan semua kemungkinan gerak dari lawan yang mungkin terjadi. Untuk melakukannya, program permainan komputer, atau bentuk lain dari kecerdasan buatan seperti perencanaan mesin, biasanya menggunakan algoritme
pencarian seperti algoritme minimaks, pemangkasan pohon
pencarian dan pemangkasan alpha-beta.
Pemenuhan Kendala
Ini adalah satu jenis
pencarian yang memecahkan permasalahan pemenuhan kendala dimana, bukan dengan melihat sebuah jalur, solusinya adalah sebuah himpunan nilai yang diberikan pada sebuah himpunan peubah. Karena peubah-peubah dapat diproses dengan urutan apa saja, algoritme
pencarian pohon biasa adalah tidak efisien. Metode pemecahan permasalahan kendala memuat
pencarian kombinatorial dan lacak balik, keduanya mengambil keuntungan dari kebebasan yang diasosiasikan dengan permasalahan kendala.
Bayangkan perihal mencari sebuah kata dalam sebuah kamus. Diberikan sembarang kata, anda memiliki beberapa ide perihal dimana membuka kamus untuk mendapatkan huruf pertama dari kata. Dari sana, anda akan memiliki ide untuk membuka beberapa halaman lagi untuk mendapatkan kota yang hampir mirip denan kata. Dan seterusnya, ini adalah ide dasar dari
pencarian interpolasi.
Jenis Lain
Algoritme
pencarian string mencari pola dalam string; salah satu struktur data yang populer yang membuat lebih efisien adalah pohon sufiks.
Algoritme genetika menggunakan ide dari evolusi sebagai heuristik untuk mengurangi ruang
pencarian.
Simulated annealing adalah sebuah algoritme pencariaan probabilistik.
pencarian Tabu adalah sebuah teknik untuk mencekah
pencarian diskrit menjadi terhenti pada minimum lokal.
pencarian Federated
Lihat pula
Algoritme Pemilihan
Teorema tidak ada makan siang gratis berhubungan dengan keumuman dari algoritme
pencarian untuk kebutuhan pengetahuan ranah.
Permasalahan Sekretaris adalah sebuah masalah
pencarian online (yaitu dipresentasikan secara sekuens) dengan informasi tak lengkap, dan sebuah strategi statistik yang optimal.