Heuristic algorithms là gì? Lấy ví dụ cụ thể 1 bài nào đó có sử dụng nó
Thầy biết các em đang học lớp 9, nên thầy sẽ cố gắng giải thích thật dễ hiểu, bám sát kiến thức các em đã được học và đặc biệt là không vượt quá chương trình.
Bây giờ, chúng ta cùng đi vào phần nội dung chính nhé!
1. Heuristic algorithms là gì?
Trong Tin học, khi chúng ta giải quyết một bài toán, mục tiêu thường là tìm ra giải pháp tối ưu nhất. Tuy nhiên, có những bài toán mà việc tìm ra giải pháp tối ưu lại đòi hỏi rất nhiều thời gian và tài nguyên tính toán, đôi khi là không khả thi trong thực tế.
Lúc này, Heuristic algorithms (hay còn gọi là thuật toán heuristic, thuật toán tìm kiếm heuristic) xuất hiện.
Nói một cách đơn giản, heuristic algorithm là một phương pháp hoặc kỹ thuật tập hợp các quy tắc kinh nghiệm, các phép phỏng đoán hoặc các phương pháp “thử và sai” có hướng dẫn để tìm ra một giải pháp gần tối ưu (hoặc chấp nhận được) cho một bài toán, thay vì cố gắng tìm bằng được giải pháp tối ưu tuyệt đối.
Hãy tưởng tượng thế này:
Nếu các em cần tìm đường đi ngắn nhất qua một mê cung lớn, cách tối ưu là phải thử tất cả các con đường có thể. Nhưng nếu mê cung quá lớn, cách này sẽ mất rất nhiều thời gian. Một thuật toán heuristic có thể sẽ là: “Luôn đi về phía có vẻ như dẫn đến đích hơn”, hoặc “Nếu gặp ngã ba, chọn nhánh nào có vẻ ít ngoằn ngoèo nhất”. Cách này có thể không phải là con đường ngắn nhất tuyệt đối, nhưng nó sẽ giúp các em thoát khỏi mê cung một cách nhanh chóng.
Đặc điểm chính của Heuristic algorithms:
* Tìm kiếm giải pháp gần tối ưu: Mục tiêu không phải là tối ưu tuyệt đối mà là một giải pháp tốt trong thời gian cho phép.
* Nhanh chóng và hiệu quả: Thường có hiệu suất tốt hơn các thuật toán tìm kiếm tối ưu cho các bài toán lớn.
* Dựa trên kinh nghiệm hoặc phỏng đoán: Sử dụng các quy tắc ngón tay cái (rules of thumb) hoặc các ước lượng.
* Có thể không đảm bảo tìm thấy giải pháp tối ưu: Đây là nhược điểm chính, nhưng thường được chấp nhận để đổi lấy tốc độ.
2. Lấy ví dụ cụ thể 1 bài nào đó có sử dụng Heuristic algorithm
Trong chương trình Tin học lớp 9, chúng ta đã được học về các bài toán liên quan đến tìm kiếm và sắp xếp. Tuy nhiên, để minh họa rõ ràng nhất về heuristic algorithm mà không vượt quá kiến thức, thầy sẽ lấy một ví dụ kinh điển trong lĩnh vực này, đó là bài toán “Người bán hàng rong” (Traveling Salesperson Problem – TSP).
Bài toán Người bán hàng rong (Traveling Salesperson Problem – TSP):
* Mô tả: Cho một danh sách các thành phố và khoảng cách giữa mỗi cặp thành phố. Một người bán hàng rong phải ghé thăm mỗi thành phố đúng một lần và sau đó quay trở lại thành phố xuất phát. Mục tiêu là tìm ra lộ trình có tổng quãng đường đi ngắn nhất.
* Tại sao đây là bài toán khó? Với số lượng thành phố \(n\) lớn, số lượng các lộ trình có thể tăng lên theo cấp số nhân (\((n-1)!/2\)). Việc thử tất cả các lộ trình để tìm ra cái ngắn nhất là không khả thi về mặt thời gian tính toán.
* Heuristic Algorithm cho bài toán TSP: Thuật toán “Láng giềng gần nhất” (Nearest Neighbor Algorithm)
Đây là một thuật toán heuristic rất phổ biến và dễ hiểu cho bài toán TSP.
Các bước thực hiện:
1. Chọn một thành phố xuất phát ngẫu nhiên (hoặc theo một quy tắc định trước). Đánh dấu thành phố này là đã ghé thăm.
2. Từ thành phố hiện tại, tìm thành phố chưa được ghé thăm nào gần nhất.
3. Di chuyển đến thành phố đó. Đánh dấu thành phố vừa đến là đã ghé thăm.
4. Lặp lại bước 2 và 3 cho đến khi tất cả các thành phố đều được ghé thăm.
5. Cuối cùng, quay trở lại thành phố xuất phát ban đầu.
Ví dụ minh họa:
Giả sử có 4 thành phố A, B, C, D và các khoảng cách giữa chúng như sau:
* A-B: 10
* A-C: 15
* A-D: 20
* B-C: 35
* B-D: 25
* C-D: 30
Chúng ta sẽ áp dụng thuật toán “Láng giềng gần nhất” bắt đầu từ thành phố A.
* Bước 1: Bắt đầu tại A. Đã ghé thăm: {A}. Lộ trình hiện tại: A.
* Bước 2: Từ A, tìm thành phố chưa ghé thăm gần nhất.
* A đến B: 10
* A đến C: 15
* A đến D: 20
Thành phố gần nhất là B (khoảng cách 10).
* Bước 3: Di chuyển đến B. Đã ghé thăm: {A, B}. Lộ trình hiện tại: A -> B.
* Bước 4: Từ B, tìm thành phố chưa ghé thăm gần nhất. Các thành phố chưa ghé thăm là C và D.
* B đến C: 35
* B đến D: 25
Thành phố gần nhất là D (khoảng cách 25).
* Bước 5: Di chuyển đến D. Đã ghé thăm: {A, B, D}. Lộ trình hiện tại: A -> B -> D.
* Bước 6: Từ D, tìm thành phố chưa ghé thăm gần nhất. Chỉ còn thành phố C chưa được ghé thăm.
* D đến C: 30
* Bước 7: Di chuyển đến C. Đã ghé thăm: {A, B, D, C}. Lộ trình hiện tại: A -> B -> D -> C.
* Bước 8: Tất cả các thành phố đã được ghé thăm. Quay trở lại thành phố xuất phát là A.
* C đến A: 15
* Hoàn thành lộ trình: A -> B -> D -> C -> A.
* Tổng quãng đường: 10 (A-B) + 25 (B-D) + 30 (D-C) + 15 (C-A) = 80.
Vậy, với thuật toán “Láng giềng gần nhất”, chúng ta tìm được một lộ trình có tổng quãng đường là 80.
Lưu ý: Thuật toán này có thể cho ra các kết quả khác nhau tùy thuộc vào thành phố xuất phát ban đầu. Nếu chúng ta bắt đầu từ C chẳng hạn, lộ trình có thể khác và tổng quãng đường cũng có thể khác. Điều quan trọng là nó đã đưa ra một giải pháp “chấp nhận được” và tương đối nhanh chóng, thay vì phải tính toán tất cả \( (4-1)!/2 = 3 \) lộ trình có thể có.
So sánh với giải pháp tối ưu (để các em thấy):
Trong ví dụ nhỏ này, chúng ta có thể dễ dàng kiểm tra các lộ trình còn lại:
* A -> C -> D -> B -> A: 15 + 30 + 25 + 10 = 80
* A -> B -> C -> D -> A: 10 + 35 + 30 + 20 = 95
* A -> C -> B -> D -> A: 15 + 35 + 25 + 20 = 95
* A -> D -> B -> C -> A: 20 + 25 + 35 + 15 = 95
* A -> D -> C -> B -> A: 20 + 30 + 35 + 10 = 95
Trong trường hợp này, chúng ta may mắn là thuật toán “Láng giềng gần nhất” đã tìm ra một trong những lộ trình tối ưu (cùng với lộ trình A -> C -> D -> B -> A). Tuy nhiên, điều này không luôn xảy ra với các bài toán lớn hơn.
Về cơ bản, heuristic algorithms là một công cụ mạnh mẽ để giải quyết các bài toán mà phương pháp tối ưu trở nên quá tốn kém. Các em có thể hình dung nó giống như việc “đoán mò thông minh” vậy đó.
Các em có câu hỏi gì về phần này không? Chúng ta có thể thảo luận thêm nhé.
Định nghĩa của Heuristic algorithms :
A heuristic algorithm is one that is designed to solve a problem in a faster and more efficient fashion than traditional methods by sacrificing optimality, accuracy, precision, or completeness for speed.
Mod av nào đó dịch hộ :
Thuật toán heuristic là một thuật toán được thiết kế để giải quyết vấn đề theo cách nhanh hơn và hiệu quả hơn các phương pháp truyền thống bằng cách hy sinh tính tối ưu, độ chính xác, độ chính xác hoặc tính đầy đủ cho tốc độ.
\(=>\) Dài quá, tóm gọn lại nà
\(-\) Là một cái gì đó đó là thuật toán
\(-\) Chú trọng thời gian chạy, ưu tiên thời gian code chạy phải nhanh, cho dù hy sinh tính chính xác hay độ tối ưu để đạt được thời gian chạy ngắn nhất
\(-\) Mấy còn lại anh tự hiểu nhé !! :))
\(***\) Ví dụ :
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
An example heuristic for this problem is a greedy algorithm, which sorts the items in descending order of value per weight, and then proceeds to insert them into the “sack”.
\(=>\)
Cho một nhóm mặt hàng, mỗi mặt hàng có trọng lượng và giá trị, hãy xác định số lượng của mỗi mặt hàng để đưa vào bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng một giới hạn nhất định và tổng giá trị càng lớn càng tốt.
Một ví dụ heuristic cho vấn đề này là một thuật toán tham lam, sắp xếp các mục theo thứ tự giảm dần của giá trị trên mỗi trọng lượng, sau đó tiến hành chèn chúng vào “bao tải”. Điều này đảm bảo các mặt hàng “dày đặc” có giá trị nhất sẽ được đưa vào bao tải trước.