Algoritma pencarian: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
|||
Baris 7:
=== Pencarian List ===
Algoritma pencarian list mungkin adalah algoritma 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]] algoritma-algoritma tersebuh telah
[[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 algoritma 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''). Pengecualin ada pada tabel hash, yang tidak dapat melakukan pencarian tersebut secara efisien.
=== Pencarian Pohon ===
[[Algoritma pencarian pohon]] adalah jantung dari teknik-teknik pencarian. Algoritma 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 dieksplorasi dalam urutan yang berbeda-beda, dieksplore 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== Pencarian ''uninformed'' ==
Sebuah algoritma pencarian ''uninformed'' adalah algoritma yang tidak mempertimbangkan sifat alami dari permasalahan. Oleh karena itu algoritma 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.
=== Pencarian List ===
Algoritma pencarian list mungkin adalah algoritma 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]] algoritma-algoritma tersebuh telah dipelajri dengan baik. Algoritma paling sederhana adalah [[pencarian linear]], yang secara sederhana melihat setiap elemen dari list secara berurutan. [[Waktu pengerjaan]] algoritma ini adalah [[notasi O besar|O]](''n''), dimana ''n'' adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. Algoritma 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 [[algoritma 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. [[Algoritma Grover]] adalah sebuah [[komputer kuantum|algoritma 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.
Baris 15 ⟶ 27:
=== Pencarian Pohon ===
[[Algoritma pencarian pohon]] adalah jantung dari teknik-teknik pencarian. Algoritma 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 dieksplorasi dalam urutan yang berbeda-beda, dieksplore 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]].
=== Pencarian Graf ===
Banyak permasalahan dalam [[teori graf]] dapat dipecahkan dengan memanfaatkan algoritma pencarian, seperti [[algoritma Dijkstra]], [[algoritma Kruskal's]], [[algoritma tetangga terdekat]], dan [[algoritma Prim]].-first|pencarian iterative-deepening]], [[pencarian berbatas kedalaman]], [[pencarian dwiarah]] dan [[pencarian uniform-cost]].
=== Pencarian Graf ===
Banyak permasalahan dalam [[teori graf]] dapat dipecahkan dengan memanfaatkan algoritma pencarian, seperti [[algoritma Dijkstra]], [[algoritma Kruskal's]], [[algoritma tetangga terdekat]], dan [[algoritma Prim]].
'''
== Pencarian ''Informed'' ==
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 algoritma pencarian list ''informed'' yang dikenali. Salah satu anggota dari algoritma tersebut adalah sebuah hash tabel dengan sebuah fungsi ''hashing'', yaitu algoritma dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritma ''informed'' adalah
== Pencarian Adversarial ==
| |||