Algoritma pencarian: Perbedaan antara revisi

Dalam [[ilmu komputer]], sebuah '''algoritmaalgoritme pencarian''' dijelaskan secara luas adalah sebuah algoritmaalgoritme yang menerima [[masukan]] berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Sebagian besar algoritmaalgoritme yang dipelajari oleh ilmuwan komputer adalah algoritmaalgoritme 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]]

pada ruang pencarian, sedangkan algoritmaalgoritme pencarian ''informed'' menggunakan [[heuristik]] untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.

== Pencarian ''uninformedUninformed'' ==

Sebuah algoritmaalgoritme pencarian ''uninformed'' adalah algoritmaalgoritme yang tidak mempertimbangkan sifat alami dari permasalahan. Oleh karena itu algoritmaalgoritme tersebut dapat diimplementasikan secara umum, sehingga dengan implementasi yang sama dapat digunakan pada lingkup permasalahan yang luas, hal ini berkat [[Abstraksi (ilmu komputer)|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.

AlgoritmaAlgoritme pencarian list mungkin adalah algoritmaalgoritme 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]] algoritmaalgoritme-algoritmaalgoritme tersebuhtersebut telah dipelajridipelajari dengan baik. AlgoritmaAlgoritme paling sederhana adalah [[pencarian linear]], yang secara sederhana melihat setiap elemen dari list secara berurutan. [[Waktu pengerjaan]] algoritmaalgoritme ini adalah [[notasi O besar|O]](''n''), dimana ''n'' adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. AlgoritmaAlgoritme 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 [[algoritmaalgoritme 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. [[AlgoritmaAlgoritme Grover]] adalah sebuah [[komputer kuantum|algoritmaalgoritme kuantum]] yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut.

Sebagian besar algoritmaalgoritme 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.

[[AlgoritmaAlgoritme pencarian pohon]] adalah jantung dari teknik-teknik pencarian. AlgoritmaAlgoritme 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]].

Banyak permasalahan dalam [[teori graf]] dapat dipecahkan dengan memanfaatkan algoritmaalgoritme pencarian, seperti [[algoritmaalgoritme Dijkstra]], [[algoritmaalgoritme Kruskal's]], [[algoritmaalgoritme tetangga terdekat]], dan [[algoritmaalgoritme Prim]].-first|pencarian iterative-deepening]], [[pencarian berbatas kedalaman]], [[pencarian dwiarah]] dan [[pencarian uniform-cost]].

Terdapat beberapa algoritmaalgoritme pencarian list ''informed'' yang dikenali. Salah satu anggota dari algoritmaalgoritme tersebut adalah sebuah hash tabel hash dengan sebuah fungsi ''hashing'', yaitu algoritmaalgoritme dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritmaalgoritme ''informed'' adalah mengeksplore pohon. Termasuk di dalamnya adalah [[pencarian Breadth-first]], dan [[AlgoritmaAlgoritme Pencarian A Bintang|A*]]. Sebagaimana algoritmaalgoritme ''uninformed'', algoritmaalgoritme ''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 algoritmaalgoritme pencarian seperti [[algoritmaalgoritme minimaks]], [[pemangkasan pohon pencarian]] dan [[pemangkasan alpha-beta]].

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, algoritmaalgoritme 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]].

* [[AlgoritmaAlgoritme pencarian string]] mencari pola dalam [[string (ilmu komputer)|string]]; salah satu struktur data yang populer yang membuat lebih efisien adalah [[pohon sufiks]].

* [[AlgoritmaAlgoritme genetika]] menggunakan ide dari [[evolusi]] sebagai heuristik untuk mengurangi ruang pencarian.

* [[Simulated annealing]] adalah sebuah algoritmaalgoritme pencariaan [[probabilistik]].

* [[AlgoritmaAlgoritme Pemilihan]]

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

[[Kategori:AlgoritmaAlgoritme]]