Thuật toán dò tìm triệt để

Dò Tìm Triệt Để là gì và tại sao chúng ta lại dùng nó?

Ở trò chơi “Siêu Robot ném bóng rổ”, ở mỗi vị trí bạn Robot đang đứng, sẽ có một cặp số “Vận tốc ném bóng cao” và “Vận tốc ném bóng xa” duy nhất mà khi bạn Robot chọn đúng cặp tham số này để ném bóng thì sẽ đưa được bóng vào rổ.

Có nhiều cách làm để bạn Robot tìm ra được cặp tham số này, nhưng cách dễ hiểu nhất là dùng thuật toán Dò Tìm Triệt Để. Thuật toán Dò Tìm Triệt Để, hay còn có tên gọi khác thuật toán “Trâu Bò”, là một dạng thuật toán chạy qua tất cả các trường hợp có thể xảy ra để tìm phương án cho một vấn đề nào đó.

Cách sử dụng Dò Tìm Triệt Để

Dùng Dò Tìm Triệt Để lập trình cho Siêu Robot ném bóng rổ

Trong bài Lập trình Siêu Robot ném bóng rổ chúng ta đã từng áp dụng thuật toán Dò Tìm Triệt Để. Bạn Robot sẽ thử từng giá trị của “Ném bóng cao” với từng giá trị của “Ném bóng xa” cho đến khi bóng ném trúng tâm Rổ.

Sau đây là một ví dụ cho trường hợp bóng sẽ được ném vào Rổ nếu giá trị “ném Bóng cao” = 6 và “ném Bóng xa” = 4:

Khi bắt đầu ném bóng, bạn Robot sẽ không biết được với giá trị “ném Bóng cao” và “ném Bóng xa” nào thì bóng sẽ vào Rổ. Do đó, bạn phải thử lần lượt từng trường hợp một bằng cách ghép hai biến số với giá trị từ nhỏ đến lớn như hình minh hoạ dưới đây. 

Phân tích cách bạn Robot dùng Dò Tìm Triệt Để một cách chi tiết hơn: 

Sau khi đã hiểu được những bước cơ bản, chúng ta hãy cùng nhau tìm hiểu cách lập trình thuật toán này cho bạn Robot nào:

Một ví dụ khác: Tìm hai bạn sinh đôi ở hai lớp khác nhau

Nếu ví dụ trên hơi khó hiểu, chúng ta hãy cùng nghĩ đến một cách áp dụng khác của phương pháp Dò Tìm Triệt Để trong đời sống hàng ngày để dễ hình dung hơn.

Cách dễ nhất là với mỗi bạn ở lớp 2A bắt đầu từ bạn có số báo danh nhỏ nhất, chúng ta lại so sánh với tất cả những bạn ở lớp 2B cũng theo thứ tự số báo danh từ nhỏ đến lớn. Làm như vậy chúng ta sẽ không bỏ lỡ một trường hợp nào. 

Cứ lặp lại cách so sánh đó cho đến khi nào tìm được hai bạn giống nhau, thì đó chính là hai bạn sinh đôi mà mình muốn tìm.

Dò Tìm Triệt Để có điểm mạnh và điểm yếu gì?

Điểm mạnh:

Vì thuật toán Dò Tìm Triệt Để là một thuật toán đi qua tất cả các trường hợp có thể xảy ra. Do đó khi dùng thuật toán này, chúng ta sẽ luôn luôn tìm ra câu trả lời cho tất cả những vấn đề mình cần giải quyết, nếu như đáp án đó tồn tại.

Thuật toán này nhìn chung tương đối dễ hiểu, và dễ lập trình. 

Điểm yếu:

Tuy nhiên, như đã nói ở trên, vì thuật toán này xét tất cả các trường hợp, cho nên nó sẽ bao gồm cả trường hợp đúng và sai. Vì thế, việc tìm ra đáp án sẽ mất rất nhiều thời gian. 

Để xem trò chi tiết cách thuật toán dò tìm triệt để được lập trình trong trò chơi “Siêu robot ném bóng rổ”, con có thể tham khảo link sau nhé: http://bit.ly/RobotBongRo

— — —

STEAM for Vietnam Foundation là tổ chức phi lợi nhuận 501(c)(3) được thành lập tại Hoa Kỳ với sứ mệnh thúc đẩy các hoạt động liên quan tới giáo dục STEAM (Science — Khoa học, Technology — Công nghệ, Engineering — Kỹ thuật, Arts — Nghệ thuật, Mathematics — Toán học) tại Việt nam. STEAM for Vietnam được thành lập và vận hành bởi đội ngũ tình nguyện viên là du học sinh và chuyên gia người Việt trên khắp thế giới.

— — —

📧Email: hello@steamforvietnam.org

🌐Website: www.steamforvietnam.org

🌐Fanpage: STEAM for Vietnam

📺YouTube:  http://bit.ly/S4V_YT

🌐Zalo: Zalo Official