Phần 1.Thuật toán QUY HOẠCH ĐỘNG

Xin chào các bạn! Hôm nay chúng ta sẽ cùng nhau khám phá một chút về thuật toán qui hoạch động – một kỹ thuật thiết kế thuật toán thú vị.

Giới thiệu về thuật toán Qui Hoạch Động

Thuật toán qui hoạch động là một phương pháp chia bài toán lớn thành các bài toán con nhỏ hơn, sau đó sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu. Khác với phương pháp chia để trị, thuật toán qui hoạch động tính toán trước lời giải của các bài toán con và lưu vào bộ nhớ, sau đó sử dụng lời giải này để giải bài toán lớn hơn.

Bạn đang xem: Phần 1.Thuật toán QUY HOẠCH ĐỘNG

Ví dụ: Giả sử chúng ta có bài toán kinh điển về dãy Fibonacci – tìm số Fibonacci thứ n, ký hiệu là F(n). Để giải quyết bài toán này, chúng ta có thể sử dụng thuật toán qui hoạch động.

Chia để trị: Một phương pháp không lý tưởng

Xem thêm : 40 lời chia tay đồng nghiệp nghỉ việc, chuyển công tác ý nghĩa nhất

Trước khi tìm hiểu về qui hoạch động, chúng ta hãy cùng nhìn vào phương pháp chia để trị. Dưới đây là đoạn code minh họa cho thuật toán chia để trị trong việc tính số Fibonacci:

Function Fib(n) {
  if n < 2 then return n;
  else return Fib(n-1) + Fib(n-2);
}

Như bạn có thể thấy, khi sử dụng chia để trị, chúng ta phải tính lại các bài toán con rất nhiều lần. Điều này rõ ràng không phải là phương pháp tối ưu.

Qui hoạch động: Tối ưu hơn nhiều

Thay vì tính toán lại các bài toán con nhiều lần, chúng ta sử dụng một mảng để lưu trữ kết quả của bài toán con. Điều này giúp cho việc tính toán trở nên đơn giản hơn rất nhiều.

Xem thêm : Bài 8: Các kiểu dữ liệu và cách sử dụng

Bạn có thể tự thử suy nghĩ giữa hai cách tiếp cận này và so sánh bộ nhớ và thời gian thực hiện. Qui hoạch động sẽ tối ưu hơn khi tính toán với các con số lớn. Hãy thử tính F[1 tỷ] bằng phương pháp chia để trị, máy tính của bạn sẽ “đơ” luôn đấy ????. Hãy tự trải nghiệm để cảm nhận sự khác biệt.

Tóm tắt ý tưởng qui hoạch động

• Phân rã: Chia bài toán cần giải thành những bài toán con nhỏ hơn, có thể giải trực tiếp hoặc không.
• Giải các bài toán con và ghi nhận lời giải: Lưu trữ lời giải của các bài toán con vào một bảng để sử dụng về sau.
• Tổng hợp lời giải: Tổng hợp lời giải các bài toán con kích thước nhỏ hơn thành lời giải bài toán lớn hơn. Tiếp tục cho đến khi thu được lời giải của bài toán ban đầu.

Kết luận

Đây là những kiến thức cơ bản về qui hoạch động mà chúng ta đã tìm hiểu. Còn rất nhiều bài toán phức tạp khác mà qui hoạch động có thể áp dụng. Hãy đợi phần tiếp theo để khám phá thêm nhé!

Cảm ơn các bạn đã theo dõi bài viết này. Hẹn gặp lại các bạn ở những bài viết tiếp theo!

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập