Lập trình năng động

Lập trình năng động

Lập trình động là một phương pháp thiết kế các thuật toán.

Một thuật toán được thiết kế bằng Lập trình động sẽ chia bài toán thành các bài toán con, tìm giải pháp cho các bài toán con đó và kết hợp chúng lại với nhau để tạo thành một giải pháp hoàn chỉnh cho bài toán mà chúng ta muốn giải.

Chúng ta đã thấy Lập trình động trong hướng dẫn này, trong các kỹ thuật ghi nhớ và lập bảng cũng như để giải các bài toán như Bài toán chiếc ba lô 0/1 hoặc để tìm đường đi ngắn nhất bằng thuật toán Bellman-Ford .

Sử dụng lập trình động để tìm số Fibonacci thứ \(n\)

Giả sử chúng ta muốn một thuật toán tìm số Fibonacci thứ \(n\). Chúng tôi chưa biết cách tìm số Fibonacci thứ \(n\), ngoại trừ việc chúng tôi muốn sử dụng Lập trình động để thiết kế thuật toán.

Vậy làm thế nào chúng ta có thể sử dụng Lập trình động để thiết kế một thuật toán tìm số Fibonacci thứ \(n\)th?

Không có quy tắc chính xác nào về cách thiết kế thuật toán bằng Lập trình động, nhưng đây là gợi ý có thể áp dụng được trong hầu hết các trường hợp:

1. Kiểm tra xem sự cố có "các bài toán con chồng chéo" và "cấu trúc con tối ưu" hay không.
2. Giải các bài toán con cơ bản nhất.
3. Tìm cách kết hợp các lời giải của bài toán con lại với nhau để tạo thành lời giải cho các bài toán con mới.
4. Viết thuật toán (quy trình từng bước).
5. Thực hiện thuật toán (kiểm tra xem nó có hoạt động không).

Hãy làm nó.

Bước 1: Kiểm tra xem vấn đề có "các bài toán con chồng chéo" và "cấu trúc con tối ưu" hay không.

Trước khi thử tìm một thuật toán bằng Lập trình động, trước tiên chúng ta phải kiểm tra xem bài toán có hai thuộc tính "bài toán con chồng chéo" và "cấu trúc con tối ưu" hay không.

Các vấn đề phụ chồng chéo?

Đúng. Số Fibonacci thứ \(6\)là sự kết hợp của số Fibonacci thứ \(5\) và \(4\)th: \(8=5+3\). Và quy tắc này cũng áp dụng cho tất cả các số Fibonacci khác. Điều này cho thấy bài toán tìm số Fibonacci thứ \(n\)th có thể được chia thành các bài toán con.

Ngoài ra, các bài toán con trùng lặp vì \(F(5)\) dựa trên \(F(4)\) và \(F(3)\) và \(F(6)\) dựa trên \(F (5)\) và \(F(4)\).

\[ \begin{equation} \begin{aligned} F(5) {} & =\underline{F(4)}+F(3) \\ 5 & =\underline{3}+2 \\\\ & và \\\\ F(6) & =F(5)+\underline{F(4)} \\ 8 & =5+\underline{3} \end{aligned} \end{equation} \]

Bạn thấy không? Cả hai nghiệm của các bài toán con \(F(5)\) và \(F(6)\) đều được tạo bằng cách sử dụng nghiệm của \(F(4)\), và có nhiều trường hợp như vậy, do đó các bài toán con cũng trùng nhau .

Cấu trúc nền tảng tối ưu?

Đúng, dãy số Fibonacci có cấu trúc rất rõ ràng, vì hai số trước đó được cộng lại để tạo ra số Fibonacci tiếp theo và điều này đúng với tất cả các số Fibonacci ngoại trừ hai số đầu tiên. Điều này có nghĩa là chúng ta biết cách kết hợp một giải pháp bằng cách kết hợp các giải pháp cho các bài toán con.

Ta có thể kết luận bài toán tìm số Fibonacci thứ \(n\)thỏa mãn hai yêu cầu, nghĩa là ta có thể sử dụng Lập trình động để tìm ra thuật toán giải quyết bài toán.

Bước 2: Giải các bài toán con cơ bản nhất.

Bây giờ chúng ta có thể bắt đầu thử tìm một thuật toán bằng Lập trình động.

Việc giải các bài toán con cơ bản nhất trước tiên là nơi tốt để bắt đầu có ý tưởng về cách chạy thuật toán.

Trong bài toán tìm số Fibonacci thứ \(n\)th, việc tìm các bài toán con cơ bản nhất không khó lắm, vì chúng ta đã biết rằng

\[ F(0)=0 \\ F(1)=1 \\ F(2)=1 \\ F(3)=2 \\ F(4)=3 \\ F(5)=5 \\ F(6)=8 \\ ... \]

Bước 3: Tìm cách ghép các lời giải của bài toán con lại với nhau để tạo thành lời giải của bài toán con mới.

Ở bước này, đối với bài toán của chúng ta, cách ghép các bài toán con lại với nhau khá đơn giản, chúng ta chỉ cần cộng hai số Fibonacci trước đó để tìm số tiếp theo.

Vì vậy, ví dụ: số Fibonacci \(2\)nd được tạo bằng cách cộng hai số trước đó \(F(2)=F(1)+F(0)\), và đó cũng là quy tắc chung, như đã đề cập trước đó: \(F(n)=F(n-1)+F(n-2)\).

Bước 4: Viết thuật toán (quy trình từng bước).

Thay vì viết ngay văn bản cho thuật toán, có thể bạn nên thử viết một quy trình để giải quyết một vấn đề cụ thể trước tiên, chẳng hạn như tìm số Fibonacci thứ \(6\).

Để tham khảo, 8 số Fibonacci đầu tiên là: \(0,\; 1,\; 1,\; 2,\; 3,\; 5,\; \underline{8},\; 13\).

Tìm số Fibonacci thứ \(6\), chúng ta có thể bắt đầu với hai số đầu tiên \(0\) và \(1\), xuất hiện ở vị trí 0 và 1 trong dãy và đặt chúng vào một mảng, tại chỉ mục 0 và 1. Sau đó, chúng ta có thể cộng hai số đầu tiên trong mảng để tạo số tiếp theo và đẩy số mới đó làm phần tử mới vào mảng. Nếu chúng ta tiếp tục như vậy cho đến khi mảng dài 7 phần tử, chúng ta sẽ dừng và trả về F[6] . Điều đó sẽ hiệu quả, phải không?

Sau khi giải quyết vấn đề cụ thể ở trên, việc viết thuật toán thực tế trở nên dễ dàng hơn.

Thuật toán tìm số Fibonacci thứ \(n\), sử dụng Lập trình động làm phương pháp thiết kế, có thể được mô tả như sau:

Bước 5: Thực hiện thuật toán (kiểm tra xem nó có hoạt động không)

Để triển khai thuật toán ở trên, chúng tôi giả sử rằng đối số n của hàm là một số dương (số Fibonacci thứ \(n\)), chúng tôi sử dụng vòng lặp for để tạo các số Fibonacci mới và chúng tôi trả về các trường hợp cơ sở F[0] và F[1] ngay lập tức nếu hàm được gọi với đối số là 0 hoặc 1 .

Việc thực hiện thuật toán cũng có nghĩa là chúng ta có thể kiểm tra xem nó có hoạt động hay không.

 def nth_fibo(n):     if n==0: return 0     if n==1: return 1      F = [None] * (n + 1)     F[0] = 0     F[1] = 1      for i in range(2, n + 1):         F[i] = F[i - 1] + F[i - 2]      return F[n] 
n = 6
result = nth_fibo(n)
print(f"The {n}th Fibonacci number is {result}")

Nó đây rồi!

Chúng tôi đã sử dụng Lập trình động làm phương pháp thiết kế để tạo ra thuật toán tìm số Fibonacci thứ \(n\).

Chúng tôi cũng đã triển khai thuật toán để chứng minh rằng nó hoạt động và khi làm như vậy, chúng tôi đã vô tình sử dụng một kỹ thuật đã được thiết lập tốt trong Lập trình động được gọi là lập bảng , trong đó giải pháp được tìm thấy bằng cách giải các bài toán con từ dưới lên, sử dụng một số loại bảng.

Hơn nữa, chúng tôi đã tránh tính toán nhiều lần các bài toán con chồng chéo giống nhau, chẳng hạn như F[3] , mà cuối cùng chúng tôi có thể đã làm khác, chẳng hạn như với cách tiếp cận đệ quy bạo lực .

Một kỹ thuật khác được sử dụng trong Lập trình động được gọi là ghi nhớ . Trong trường hợp này, việc sử dụng tính năng ghi nhớ về cơ bản sẽ giải quyết vấn đề một cách đệ quy bằng vũ lực, nhưng lưu trữ các giải pháp của bài toán con cho lần sau khi thuật toán chạy để tránh thực hiện các phép tính tương tự nhiều lần.

Các kỹ thuật được sử dụng trong lập trình động

Có thể khó thiết kế một thuật toán bằng Lập trình động, nhưng khái niệm Lập trình động thực ra không khó đến thế: Giải quyết vấn đề, nhưng vì các bài toán con chồng lên nhau nên hãy thực hiện một cách thông minh sao cho chỉ cần giải quyết một bài toán con cụ thể. giải quyết một lần.

Để có thể sử dụng lời giải cho các bài toán con đã được giải quyết trước đó trong Lập trình động, các lời giải được tìm thấy trước đó phải được lưu trữ bằng cách nào đó và việc đó có thể được thực hiện bằng cách sử dụng tính năng ghi nhớ hoặc lập bảng .

Ghi nhớ là một kỹ thuật được sử dụng trong Lập trình động, trong đó giải pháp được tìm thấy theo cách đệ quy. Khi thuật toán chạy, giải pháp cho các bài toán con được lưu trữ và trước khi thử tính giải pháp cho một bài toán con, trước tiên nó sẽ kiểm tra xem giải pháp đó đã được tính toán chưa, để tránh thực hiện cùng một phép tính nhiều lần.

Kỹ thuật ghi nhớ được gọi là "từ trên xuống" vì lệnh gọi hàm ban đầu dành cho vấn đề chính và nó dẫn đến các lệnh gọi hàm mới để giải các bài toán con ngày càng nhỏ hơn.

Lập bảng là một kỹ thuật được sử dụng trong Lập trình động, trong đó lời giải cho các bài toán con chồng chéo được lưu trữ trong một bảng (mảng), bắt đầu bằng các bài toán con cơ bản nhất.

Kỹ thuật lập bảng không đệ quy và được gọi là "từ dưới lên" do cách xây dựng lời giải cuối cùng bằng cách giải các bài toán con cơ bản nhất trước tiên. Vì các lời giải của bài toán con cơ bản nhất được lưu trữ trong bảng trước nên khi giải một bài toán con sau dựa trên các bài toán con trước đó, thuật toán có thể chỉ cần chọn các lời giải này ngay từ bảng mà không cần tính toán lại.

Để hiểu rõ hơn về cách hoạt động của tính năng ghi nhớ và được coi là "từ trên xuống" cũng như cách hoạt động của việc lập bảng và "từ dưới lên", hãy xem hai hình ảnh bên dưới.

Như bạn có thể thấy trong các hình ảnh trên, phương pháp lập bảng bắt đầu ở dưới cùng bằng cách giải F(0) trước, trong khi phương pháp ghi nhớ bắt đầu ở trên cùng với F(10) và chia nó thành các bài toán con ngày càng nhỏ hơn từ đó.