Tìm hiểu thuật toán vét cạn trong lập trình – Tuicocach.com
Chào mừng bạn đến với pgdgiolinhqt.edu.vn trong bài viết về Phương pháp vét cạn chúng tôi sẽ chia sẻ kinh nghiệm chuyên sâu của mình cung cấp kiến thức chuyên sâu dành cho bạn.
Vét cạn là một trong những thuật toán được áp dụng tương đối nhiều trong các bài toán thực tế, vậy thuật toán vét cạn là gì, khi nào cần dùng, làm sao áp dụng thì chúng ta sẽ cùng tìm hiểu trong bài viết này.
Thuật toán vét cạn
Ý tưởng của vét cạn là tạo ra hết tất cả các lời giải có thể có của một bài toán, và sau đó lựa chọn một giải pháp tốt nhất hoặc đếm số lượng lời giải phụ thuộc vào từng bài toán cụ thể.
Tìm kiếm vét cạn là một kỹ thuật tốt nếu dữ liệu đầu vào không quá lớn và đủ thời gian để đi qua hết tất cả các lời giải mà không tốn quá nhiều thời gian xử lý, vì việc tìm kiếm thường dễ để thực thi và nó luôn cho ra lời giải chính xác. Nếu tìm kiếm vét cạn là quá chậm, thì lúc đó ta sẽ nghĩ tới các thuật toán tham lam hoặc quy hoạch động.
Và thông thường các bài toán vét cạn sẽ sử dụng quay lui (backtracking) để vét được toàn bộ những lời giải có thể sảy ra. Mình có một bài viết riêng về backtracking, bạn đọc thăm khảo thêm nhé: Tìm hiểu về Thuật toán quay lui (Backtracking).
Nói tóm lại, thì vét cạn chính là việc ta đi tìm tất cả lời giải của một bài toán. Lý thuyết là vậy, bây giờ cùng đi vào một số bài toán ví dụ cụ thể nhé.
Xét bài toán cụ thể
Bài toán liệt kê dãy nhị phân độ dài n
Bài toán liệt kê dãy nhị phân độ dài n, có nghĩa là ta đi liệt kê hết tất cả các dãy nhị phân từ 000..0(n số 0) cho tới 111..1(n số 1). Ví dụ liệt kê dãy nhị phân độ dài 3.
000, 001, 010, 011, 100, 101, 110, 111
Đây là một bài toán điển hình 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.
Ta viết code như sau:
Kết quả khi thực hiện chương trình.
Như vậy ta đã liệt kê được hết các dãy nhị phân có độ dài là n, như vậy chính là vét cạn đó ạ.
Tìm đường đi dài nhất – Duyệt đồ thị
Tìm đường đi dài nhất trong đồ thị, đây cũng là một bài toán áp dụng phương pháp vét cạn. Với bài toán này, chúng ta sẽ duyệt và tìm kiếm tất cả các đường đi có thể của đồ thị, sau đó so sánh từng đường đi và tìm ra đường đi dài nhất của đồ thị đã cho.
Mình sẽ làm một ví dụ cụ thể, ta sẽ nhập vào ma trận đồ thị, và 2 đỉnh u và v. Sau đó tìm đường đi dài nhất từ u tới v.
Bạn tự chạy thử chương trình để xem kết quả nhé, và có thể bạn sẽ quên ma trận đồ thị là thế nào thì xem lại bảng bên dưới này nhé!.
Cảm ơn bạn đã đọc bài viết chúc bạn học tốt!
[Xem tất cả bài viết chủ đề C/C++ tại đây]
