Algoritma Pencarian Paralel
Pencarian adalah salah satu operasi fundamental dalam ilmu komputer. Ini digunakan di semua aplikasi di mana kita perlu menemukan apakah suatu elemen ada dalam daftar yang diberikan atau tidak. Pada bab ini, kita akan membahas algoritma pencarian berikut -
- Memecah dan menaklukkan
- Pencarian Kedalaman-Pertama
- Pencarian Luas-Pertama
- Pencarian Terbaik-Pertama
Memecah dan menaklukkan
Dalam pendekatan divide and conquer, masalah dibagi menjadi beberapa sub-masalah kecil. Kemudian sub-masalah diselesaikan secara rekursif dan digabungkan untuk mendapatkan solusi dari masalah aslinya.
Pendekatan divide and conquer melibatkan langkah-langkah berikut di setiap level -
Divide - Masalah asli dibagi menjadi sub-sub masalah.
Conquer - Sub-masalah diselesaikan secara rekursif.
Combine - Solusi dari sub masalah digabungkan untuk mendapatkan solusi dari masalah aslinya.
Pencarian biner adalah contoh algoritma divide and conquer.
Pseudocode
Binarysearch(a, b, low, high)
if low < high then
return NOT FOUND
else
mid ← (low+high) / 2
if b = key(mid) then
return key(mid)
else if b < key(mid) then
return BinarySearch(a, b, low, mid−1)
else
return BinarySearch(a, b, mid+1, high)
Pencarian Kedalaman-Pertama
Depth-First Search (atau DFS) adalah algoritma untuk mencari pohon atau struktur data grafik yang tidak diarahkan. Di sini, konsepnya dimulai dari simpul awal yang dikenal sebagairootdan melintasi sejauh mungkin di cabang yang sama. Jika kita mendapatkan simpul tanpa simpul penerus, kita kembali dan melanjutkan dengan simpul, yang belum dikunjungi.
Langkah-Langkah Penelusuran Mendalam-Pertama
Pertimbangkan node (root) yang tidak dikunjungi sebelumnya dan tandai sebagai dikunjungi.
Kunjungi node penerus pertama yang berdekatan dan tandai sebagai dikunjungi.
Jika semua node penerus dari node yang dipertimbangkan sudah dikunjungi atau tidak memiliki node penerus lagi, kembali ke node induknya.
Pseudocode
Membiarkan v menjadi puncak di mana pencarian dimulai pada Grafik G.
DFS(G,v)
Stack S := {};
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w of u
push S, w;
end if
end while
END DFS()
Pencarian Luas-Pertama
Breadth-First Search (atau BFS) adalah algoritma untuk mencari pohon atau struktur data grafik yang tidak diarahkan. Di sini, kita mulai dengan sebuah node dan kemudian mengunjungi semua node yang berdekatan di tingkat yang sama dan kemudian pindah ke node penerus yang berdekatan di tingkat berikutnya. Ini juga dikenal sebagailevel-by-level search.
Langkah-langkah Pencarian Luas-Pertama
- Mulailah dengan simpul akar, tandai itu dikunjungi.
- Karena node root tidak memiliki node di level yang sama, lanjutkan ke level berikutnya.
- Kunjungi semua node yang berdekatan dan tandai sebagai dikunjungi.
- Pergi ke tingkat berikutnya dan kunjungi semua node yang berdekatan yang belum dikunjungi.
- Lanjutkan proses ini sampai semua node dikunjungi.
Pseudocode
Membiarkan v menjadi puncak di mana pencarian dimulai pada Grafik G.
BFS(G,v)
Queue Q := {};
for each vertex u, set visited[u] := false;
insert Q, v;
while (Q is not empty) do
u := delete Q;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbor w of u
insert Q, w;
end if
end while
END BFS()
Pencarian Terbaik-Pertama
Best-First Search adalah algoritme yang melintasi grafik untuk mencapai target di jalur yang sesingkat mungkin. Tidak seperti BFS dan DFS, Best-First Search mengikuti fungsi evaluasi untuk menentukan node mana yang paling tepat untuk dilintasi berikutnya.
Langkah-Langkah Pencarian Terbaik-Pertama
- Mulailah dengan simpul akar, tandai itu dikunjungi.
- Temukan node yang sesuai berikutnya dan tandai sebagai dikunjungi.
- Pergi ke tingkat berikutnya dan temukan node yang sesuai dan tandai sebagai dikunjungi.
- Lanjutkan proses ini hingga target tercapai.
Pseudocode
BFS( m )
Insert( m.StartNode )
Until PriorityQueue is empty
c ← PriorityQueue.DeleteMin
If c is the goal
Exit
Else
Foreach neighbor n of c
If n "Unvisited"
Mark n "Visited"
Insert( n )
Mark c "Examined"
End procedure