ALGORITMA SEARCH
Algoritma pencarian
Dalam ilmu komputer , sebuah algoritma pencarian, secara umum, adalah algoritma untuk mencari item dengan sifat tertentu antara koleksi item. Item dapat disimpan secara individual sebagaicatatan dalam database yang , atau mungkin menjadi elemen dari sebuah ruang pencarian didefinisikan oleh rumus matematika atau prosedur, seperti akar dari suatu persamaan dengan bilangan bulatvariabel , atau kombinasi dari dua, seperti Hamiltonian sirkuit dari grafik .
Untuk ruang pencarian maya
Algoritma untuk mencari ruang virtual yang digunakan dalam masalah kepuasan kendala , di mana tujuannya adalah untuk menemukan satu set nilai ke variabel tugas tertentu yang akan memuaskan matematis tertentu persamaan dan inequations . Mereka juga digunakan ketika tujuannya adalah untuk menemukan tugas variabel yang akan memaksimalkan atau meminimalkan fungsi tertentu dari variabel tersebut. Algoritma untuk masalah ini termasuk dasar pencarian brute force (juga disebut "naif" atau "kurang informasi" pencarian), dan berbagai heuristik yang mencoba untuk memanfaatkan pengetahuan parsial tentang struktur ruang, seperti relaksasi linier , generasi kendala , dan kendala propagasi .
Subclass penting adalah pencarian lokal metode, yang melihat unsur-unsur ruang pencarian sebagai simpul dari suatu graf, dengan tepi yang didefinisikan oleh satu set heuristik berlaku untuk kasus ini, dan scan ruang dengan bergerak dari item ke item sepanjang tepi , misalnya menurut keturunan curam atau terbaik pertama kriteria, atau dalam pencarian stokastik . Kategori ini mencakup berbagai besar umum metaheuristic metode, seperti simulated annealing , pencarian tabu , A-tim, dan pemrograman genetik , yang menggabungkan heuristik sewenang-wenang dengan cara tertentu.
Kelas ini juga mencakup berbagai algoritma pencarian pohon , yang melihat unsur-unsur sebagai simpul dari pohon , dan melintasi pohon itu di beberapa pesanan khusus. Contoh terakhir ini termasuk metode lengkap seperti depth-first search dan breadth-first search , serta berbagai heuristik berbasis pemangkasan pohon pencarian metode seperti kemunduran dan cabang dan terikat . Tidak seperti metaheuristics umum, yang di tempat kerja terbaik hanya dalam arti probabilistik, banyak dari pohon-cari metode dijamin untuk menemukan solusi yang tepat atau optimal, jika diberikan cukup waktu.
Sub-kelas lain yang penting terdiri dari algoritma untuk menjelajahi pohon permainan dari beberapa pemain game, seperti catur atau backgammon , yang terdiri dari semua node situasi permainan kemungkinan yang bisa dihasilkan dari situasi saat ini. Tujuan dalam masalah ini untuk menemukan gerakan yang menyediakan kesempatan terbaik untuk menang, dengan mempertimbangkan semua kemungkinan bergerak lawan (s). Masalah serupa terjadi ketika manusia atau mesin harus membuat keputusan yang berurutan yang hasil tidak sepenuhnya di bawah kendali seseorang, seperti dalamrobot bimbingan atau dalam pemasaran , keuangan atau militer perencanaan strategi. Masalah seperti ini telah dipelajari secara ekstensif dalam konteks kecerdasan buatan . Contoh algoritma untuk kelas ini adalah algoritma minimax , alpha-beta pruning , dan algoritma A * .
Untuk sub-struktur dari struktur yang diberikan
Nama pencarian kombinatorial umumnya digunakan untuk algoritma yang mencari struktur sub-spesifik yang diberikan struktur diskrit , seperti grafik, sebuah tali , sebuah terbatas kelompok , dan sebagainya. Istilah optimasi kombinatorial biasanya digunakan ketika tujuannya adalah untuk menemukan struktur sub-dengan nilai (atau minimum) maksimum beberapa parameter. (Karena struktur sub-biasanya diwakili dalam komputer dengan satu set variabel integer dengan kendala, masalah ini dapat dipandang sebagai kasus khusus dari kepuasan kendala atau optimasi diskrit, tetapi mereka biasanya dirumuskan dan diselesaikan dalam pengaturan lebih abstrak dimana representasi internal tidak disebutkan secara eksplisit.)
Subclass penting dan ekstensif dipelajari adalah algoritma grafik , khususnya grafik traversal algoritma, untuk mencari sub-struktur yang spesifik dalam grafik yang diberikan - seperti subgraphs , jalan ,sirkuit , dan sebagainya. Contohnya termasuk algoritma Dijkstra , algoritma Kruskal , yang algoritma tetangga terdekat , dan algoritma Prim .
Subclass lain penting dari kategori ini adalah algoritma pencarian string yang , yang mencari pola dalam string. Dua contoh terkenal adalah Boyer-Moore dan Knuth-Morris-Pratt algoritma , dan beberapa algoritma berdasarkan akhiran pohon struktur data.
Untuk komputer kuantum
Ada juga mencari metode yang dirancang untuk komputer kuantum , seperti algoritma Grover , yang secara teoritis lebih cepat daripada pencarian linear atau brute force bahkan tanpa bantuan struktur data atau heuristik.
Algoritma pencarian biner
Umumnya, untuk mencari nilai dalam array disortir, kita harus melihat melalui elemen dari sebuah array satu per satu, sampai nilai dicari ditemukan. Dalam hal nilai dicari tidak ada dari array, kita melalui semua elemen. Rata-rata, kompleksitas algoritma tersebut sebanding dengan panjang array.
Situasi perubahan signifikan, ketika array diurutkan. Jika kita tahu itu, kemampuan akses acak dapat dimanfaatkan sangatefisien untuk menemukan nilai dicari cepat. Biaya dari algoritma pencarian untuk logaritma biner mengurangi panjang array.Untuk referensi, log 2 (1 000 000) ≈ 20. Ini berarti, bahwa dalam kasus terburuk, algoritma membuat 20 langkah untuk menemukan nilai dalam array diurutkan dari satu juta elemen atau mengatakan, bahwa hal itu tidak hadir array.
Algoritma
Algoritma ini cukup sederhana. Hal ini dapat dilakukan baik secara rekursif atau iteratif:
- mendapatkan elemen tengah;
- jika elemen tengah sama dengan nilai dicari, algoritma akan berhenti;
- sebaliknya, dua kasus yang mungkin:
- mencari nilai kurang, dari elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian dari array, sebelum elemen tengah.
- mencari nilai lebih besar, dari elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian dari array, setelah elemen tengah.
Sekarang kita harus mendefinisikan, saat iterasi harus berhenti. Kasus pertama adalah ketika elemen dicari ditemukan.Yang kedua adalah ketika subarray tidak memiliki elemen. Dalam kasus ini, kita dapat menyimpulkan, bahwa nilai dicari tidak hadir dalam array.
Contoh
Contoh 1. Cari 6 di {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Langkah 1 (elemen tengah adalah 19> 6): -1 5 6 18 19 25 46 78 102 114
Langkah 2 (elemen tengah adalah 5 <6): -1 5 6 18 19 25 46 78 102 114
Langkah 3 (elemen tengah adalah 6 == 6): -1 5 6 18 19 25 46 78 102 114
Contoh 2. Cari 103 di {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Langkah 1 (elemen tengah adalah 19 <103): -1 5 6 18 19 25 46 78 102 114
Langkah 2 (elemen tengah adalah 78 <103): -1 5 6 18 19 25 46 78 102 114
Langkah 3 (elemen tengah adalah 102 <103): -1 5 6 18 19 25 46 78 102 114
Langkah 4 (elemen tengah adalah 114> 103): -1 5 6 18 19 25 46 78 102 114
Langkah 5 (nilai dicari tidak ada): -1 5 6 18 19 25 46 78 102 114
Kompleksitas analisis
Keuntungan besar dari algoritma ini adalah bahwa kompleksitas itu tergantung pada ukuran array logaritmis dalam kasus terburuk. Dalam prakteknya ini berarti, algoritma yang akan dilakukan di log yang paling 2 (n) iterasi, yang merupakan jumlah yang sangat kecil, bahkan untuk array besar. Hal ini dapat terbukti sangat mudah. Memang, di setiap langkah ukuran bagian dicari berkurang setengahnya. Algoritma berhenti, ketika tidak ada unsur untuk mencari masuk Oleh karena itu, pemecahan kesenjangan berikut dalam bilangan bulat:
n / 2 iterasi> 0
mengakibatkan
iterasi <= log 2 (n).
Ini berarti, bahwa algoritma pencarian biner kompleksitas waktu adalah O (log 2 (n)).
Potongan kode.
Anda dapat melihat solusi rekursif untuk Java dan iteratif untuk C + + di bawah ini.
Java
/ **
* pencarian untuk sebuah nilai di diurutkan susunan
*
* @ Param susunan
* susunan untuk pencarian di
* @ Param nilai
* mencari nilai
* @ Param kiri
* Indeks dari kiri batas
* @ Param benar
* Indeks dari benar batas
* @ Return posisi dari mencari nilai, jika itu menyajikan di yang susunan atau - 1, jika
* itu adalah absen
* /
int binarySearch (int [] array, nilai int, int kiri, kanan int) {
jika (kiri> kanan)
return -1;
int tengah = (kiri + kanan) / 2;
if (array [tengah] == nilai)
kembali menengah;
lain if (array [tengah]> nilai)
kembali binarySearch (array, nilai, kiri, tengah - 1);
lain
kembali binarySearch (array, nilai, tengah + 1, kanan);
}
C + +
/ *
* Mencari nilai dalam array diurutkan
* Arr adalah array untuk mencari di
* Nilai dicari nilai
* Kiri adalah indeks batas kiri
* Tepat adalah indeks dari batas kanan
* Mengembalikan nilai posisi dicari, jika menyajikan dalam array
* Atau -1, jika ada
* /
int binarySearch (int arr [], int nilai, int kiri, kanan int) {
sementara (kiri <= kanan) {
int tengah = (kiri + kanan) / 2;
if (arr [tengah] == nilai)
kembali menengah;
else if (arr [tengah]> nilai)
kanan = tengah - 1;
lain
kiri = tengah + 1;
}
return -1;
}
Tidak ada komentar:
Posting Komentar