Thuật toán tìm kiếm song song
Tìm kiếm là một trong những hoạt động cơ bản trong khoa học máy tính. Nó được sử dụng trong tất cả các ứng dụng mà chúng ta cần tìm xem một phần tử có trong danh sách đã cho hay không. Trong chương này, chúng ta sẽ thảo luận về các thuật toán tìm kiếm sau:
- Phân chia và chinh phục
- Tìm kiếm sâu-đầu tiên
- Breadth-First Search
- Tìm kiếm đầu tiên tốt nhất
Phân chia và chinh phục
Trong cách tiếp cận phân chia và chinh phục, vấn đề được chia thành nhiều vấn đề phụ nhỏ. Sau đó, các bài toán con được giải một cách đệ quy và kết hợp để có được lời giải của bài toán ban đầu.
Phương pháp phân chia và chinh phục bao gồm các bước sau ở mỗi cấp độ:
Divide - Bài toán ban đầu được chia thành các bài toán con.
Conquer - Các bài toán con được giải một cách đệ quy.
Combine - Các lời giải của các bài toán con được kết hợp với nhau để có được lời giải của bài toán ban đầu.
Tìm kiếm nhị phân là một ví dụ của thuật toán chia và chinh phục.
Mã giả
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)Tìm kiếm sâu-đầu tiên
Depth-First Search (hoặc DFS) là một thuật toán để tìm kiếm một cây hoặc một cấu trúc dữ liệu đồ thị vô hướng. Ở đây, khái niệm là bắt đầu từ nút bắt đầu được gọi làrootvà đi càng xa càng tốt trong cùng một nhánh. Nếu chúng ta nhận được một nút không có nút kế nhiệm, chúng ta quay lại và tiếp tục với đỉnh, đỉnh vẫn chưa được thăm.
Các bước tìm kiếm chuyên sâu-Đầu tiên
Xem xét một nút (gốc) chưa được truy cập trước đó và đánh dấu nó đã được truy cập.
Truy cập vào nút kế nhiệm liền kề đầu tiên và đánh dấu nó đã ghé thăm.
Nếu tất cả các nút kế thừa của nút được xem xét đã được truy cập hoặc nó không còn nút kế thừa nào nữa, hãy quay trở lại nút cha của nó.
Mã giả
Để cho v là đỉnh nơi bắt đầu tìm kiếm trong Đồ thị 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()Breadth-First Search
Breadth-First Search (hoặc BFS) là một thuật toán để tìm kiếm một cây hoặc một cấu trúc dữ liệu đồ thị vô hướng. Ở đây, chúng ta bắt đầu với một nút và sau đó truy cập tất cả các nút liền kề trong cùng một cấp và sau đó chuyển đến nút kế tiếp liền kề trong cấp tiếp theo. Điều này còn được gọi làlevel-by-level search.
Các bước của Tìm kiếm theo chiều rộng-Đầu tiên
- Bắt đầu với nút gốc, đánh dấu nó đã ghé thăm.
- Vì nút gốc không có nút nào ở cùng cấp, hãy chuyển sang cấp tiếp theo.
- Truy cập tất cả các nút liền kề và đánh dấu chúng đã được truy cập.
- Chuyển đến cấp độ tiếp theo và truy cập tất cả các nút liền kề chưa được sử dụng.
- Tiếp tục quá trình này cho đến khi tất cả các nút được truy cập.
Mã giả
Để cho v là đỉnh nơi bắt đầu tìm kiếm trong Đồ thị 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()Tìm kiếm đầu tiên tốt nhất
Best-First Search là một thuật toán duyệt qua biểu đồ để đạt được mục tiêu theo con đường ngắn nhất có thể. Không giống như BFS và DFS, Best-First Search tuân theo một chức năng đánh giá để xác định nút nào là thích hợp nhất để đi qua tiếp theo.
Các bước của Tìm kiếm Đầu tiên Tốt nhất
- Bắt đầu với nút gốc, đánh dấu nó đã ghé thăm.
- Tìm nút thích hợp tiếp theo và đánh dấu nó đã truy cập.
- Đi đến cấp độ tiếp theo và tìm nút thích hợp và đánh dấu nó đã truy cập.
- Tiếp tục quá trình này cho đến khi đạt được mục tiêu.
Mã giả
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