Algoritma pencarian: Perbedaan antara revisi

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]]. Algortima pencarianAlgoritme [[pencarian brute-force]] atau pencarian naif/''uninformed'' menggunakan metode yang sederhana dan sangat [[intuitif]]

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 tersebuhtersebut telah dipelajridipelajari dengan baik. Algoritme paling sederhana adalah [[pencarian linear]], yang secara sederhana melihat setiap elemen dari list secara berurutan. [[Waktu pengerjaan]] algoritme ini adalah [[notasi O besar|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 [[notasi O besar|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 [[komputer kuantum|algoritme kuantum]] yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut.

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''). PengecualinPengecualian 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 (teori graf)|pohon]], terlepas apakah pohon tersebut eksplisit atau implisit (dibangkitkan saat pengerjaan). Prinsip dasarnya adalah sebuah [[node (ilmu komputer)|node]] diambil dari sebuah [[struktur data]], suksesornya diperiksa dan ditambahkan pada struktur data. Dengan memanipulasi struktur data, pohon dieksplorasiditelusuri dalam urutan yang berbeda-beda, dieksploreditelusuri 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 depth-first|pencarian iterative-deepening]], [[pencarian berbatas kedalaman]], [[pencarian dwiarah]] dan [[pencarian uniform-cost]].

Terdapat beberapa algoritme pencarian list ''informed'' yang dikenali. Salah satu anggota dari algoritme tersebut adalah sebuah hash 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 [[Algoritme Pencarian A Bintang|A*]]. Sebagaimana algoritme ''uninformed'', algoritme ''informed'' dapat dikembangkan untuk bekerja pada graf.

* [[Teorema No-Free-Lunchtidak ada makan siang gratis]] berhubungan dengan keumuman dari algoritme pencarian untuk kebutuhan pengetahuan ranah.