Thuật toán vét cạn là một trong những phương pháp được ứng dụng rộng rãi trong lập trình thực tế. Nhưng thuật toán vét cạn là gì? Khi nào chúng ta nên sử dụng nó? Và làm thế nào để áp dụng thuật toán này? Trong bài viết này, chúng ta sẽ cùng khám phá.
Thuật toán vét cạn: Ý tưởng và cách thức hoạt động
Ý tưởng của thuật toán vét cạn là tạo ra tất cả các lời giải có thể của một bài toán và sau đó lựa chọn giải pháp tốt nhất hoặc đếm số lượng lời giải, tuỳ thuộc vào bài toán cụ thể.
Thuật toán vét cạn được sử dụng phổ biến khi dữ liệu đầu vào không quá lớn và có đủ thời gian để duyệt qua tất cả các lời giải mà không tốn quá nhiều thời gian xử lý. Việc tìm kiếm thường dễ dàng thực thi và luôn cho ra lời giải chính xác. Tuy nhiên, nếu thuật toán vét cạn quá chậm, chúng ta có thể sử dụng các thuật toán tham lam hoặc quy hoạch động.
Thông thường, các bài toán sử dụng thuật toán vét cạn cũng sử dụng phương pháp quay lui (backtracking) để duyệt qua tất cả các lời giải có thể. Bạn có thể tìm hiểu thêm về quay lui trong bài viết: Tìm hiểu về Thuật toán quay lui (Backtracking).
Với những điểm này, thuật toán vét cạn sẽ giúp chúng ta tìm ra tất cả các lời giải của một bài toán. Để hiểu rõ hơn, hãy cùng xem một số ví dụ cụ thể.
Ví dụ: Liệt kê dãy nhị phân độ dài n
Một bài toán điển hình sử dụng phương pháp vét cạn là liệt kê tất cả các dãy nhị phân độ dài n. Điều này có nghĩa là chúng ta sẽ liệt kê tất cả các dãy từ 000..0 (với n số 0) đến 111..1 (với n số 1). Ví dụ, liệt kê danh sách dãy nhị phân độ dài 3:
000, 001, 010, 011, 100, 101, 110, 111
Đây là một ví dụ rõ ràng cho phương pháp vét cạn và chúng ta sẽ sử dụng thuật toán quay lui để thực hiện.
Dưới đây là code minh họa:
# Code minh họa thuật toán vét cạn
def vet_can(dau, cuoi, n, a):
if dau == cuoi:
print(a)
else:
for i in range(n):
a[dau] = i
vet_can(dau + 1, cuoi, n, a)
n = 3
a = [0] * n
vet_can(0, n, 2, a)Kết quả khi chạy chương trình:
000 001 010 011 100 101 110 111
Như vậy, chúng ta đã liệt kê thành công tất cả các dãy nhị phân có độ dài n. Đó chính là thuật toán vét cạn mà chúng ta đã thực hiện.
Ví dụ: Tìm đường đi dài nhất - Duyệt đồ thị
Tìm đường đi dài nhất trong đồ thị cũng là một bài toán áp dụng phương pháp vét cạn. Để giải quyết bài toán này, chúng ta sẽ duyệt qua tất cả các đường đi có thể trong đồ thị và sau đó so sánh từng đường đi để tìm ra đường đi dài nhất.
Dưới đây là một ví dụ cụ thể: Chúng ta nhập một ma trận đồ thị và hai đỉnh u và v. Sau đó, chúng ta sẽ tìm đường đi dài nhất từ u đến v.
Bạn có thể thử chạy chương trình để xem kết quả và nếu bạn quên điệu hướng của ma trận đồ thị thì hãy xem lại bảng bên dưới!
Cảm ơn bạn đã đọc bài viết này. Chúc bạn học tốt!
[Xem tất cả bài viết chủ đề C/C++ tại đây]