LẬP TRÌNH ĐỘNG: ĐẶC ĐIỂM, VÍ DỤ, ƯU ĐIỂM, NHƯỢC ĐIỂM - CÔNG NGHỆ - 2026

Các lập trình năng động là một thuật toán mô hình mà giải quyết một vấn đề phức tạp bởi chia nó thành bài toán, lưu trữ các kết quả đó để tránh việc phải tính toán lại kết quả.

Lịch trình này được sử dụng khi bạn gặp vấn đề có thể được chia thành các bài toán con tương tự, để có thể sử dụng lại kết quả của chúng. Phần lớn, lịch trình này được sử dụng để tối ưu hóa.

Lập trình năng động. Các bài toán con được xếp chồng lên nhau trong dãy Fibonacci. Nguồn: Wikimedia commons, vi: Người dùng: Dcoatzee, được truy nguyên bởi Người dùng: Stannered / Miền công cộng

Trước khi giải bài toán con có sẵn, thuật toán động sẽ cố gắng kiểm tra kết quả của các bài toán con đã giải trước đó. Các giải pháp cho các bài toán con được kết hợp để đạt được giải pháp tốt nhất.

Thay vì tính toán lặp đi lặp lại cùng một bài toán con, bạn có thể lưu trữ giải pháp của mình trong một bộ nhớ nào đó, khi bạn gặp bài toán con này lần đầu tiên. Khi nó xuất hiện lại trong quá trình giải bài toán con khác, giải pháp đã được lưu trong bộ nhớ sẽ được thực hiện.

Đây là một ý tưởng tuyệt vời để cố định thời gian bộ nhớ, trong đó việc sử dụng thêm dung lượng có thể cải thiện thời gian cần thiết để tìm ra giải pháp.

Các tính năng của lập trình động

Các đặc điểm cơ bản sau đây là những gì bạn phải gặp vấn đề trước khi có thể áp dụng lập trình động:

Cấu trúc con tối ưu

Đặc điểm này thể hiện rằng một vấn đề tối ưu hóa có thể được giải quyết bằng cách kết hợp các giải pháp tối ưu của các vấn đề thứ cấp bao gồm nó. Các cấu trúc con tối ưu này được mô tả bằng đệ quy.

Ví dụ, trong một đồ thị, một cấu trúc con tối ưu sẽ được trình bày trong đường đi ngắn nhất r đi từ đỉnh s đến đỉnh t:

Tức là trong đường đi ngắn nhất này r có thể lấy bất kỳ đỉnh trung gian nào. Nếu r thực sự là tuyến đường ngắn nhất, thì nó có thể được chia thành các tuyến con r1 (từ s đến i) và r2 (từ i đến t), sao cho chúng lần lượt là các tuyến ngắn nhất giữa các đỉnh tương ứng.

Do đó, để tìm các đường đi ngắn nhất, giải pháp có thể dễ dàng được xây dựng một cách đệ quy, đó là những gì thuật toán Floyd-Warshall thực hiện.

Bài toán con chồng chéo

Không gian bài toán con phải nhỏ. Có nghĩa là, bất kỳ thuật toán đệ quy nào giải quyết một vấn đề sẽ phải giải quyết các bài toán con giống nhau lặp đi lặp lại, thay vì tạo ra các bài toán con mới.

Ví dụ, để tạo chuỗi Fibonacci, chúng ta có thể xem xét công thức đệ quy này: Fn = F (n - 1) + F (n - 2), coi như một trường hợp cơ sở mà F1 = F2 = 1. Khi đó chúng ta sẽ có: F33 = F32 + F31 và F32 = F31 + F30.

Như bạn có thể thấy, F31 đang được phân giải thành các cây con đệ quy của cả F33 và F32. Mặc dù tổng số bài toán con thực sự nhỏ, nhưng nếu bạn áp dụng một giải pháp đệ quy như thế này, bạn sẽ kết thúc việc giải các bài toán giống nhau lặp đi lặp lại.

Điều này được tính đến bởi lập trình động, vì vậy nó chỉ giải quyết mỗi vấn đề con một lần. Điều này có thể được thực hiện theo hai cách:

Cách tiếp cận từ trên xuống

Nếu lời giải cho bất kỳ bài toán nào có thể được lập công thức đệ quy bằng cách sử dụng lời giải của các bài toán con của nó và nếu các bài toán con này trùng nhau, thì lời giải của các bài toán con có thể dễ dàng được ghi nhớ hoặc lưu trữ trong một bảng.

Mỗi khi tìm kiếm lời giải bài toán con mới, bảng sẽ được kiểm tra xem nó đã được giải trước đó chưa. Trong trường hợp một giải pháp được lưu trữ, nó sẽ được sử dụng thay vì tính toán lại. Nếu không, bài toán con sẽ được giải quyết, lưu trữ lời giải trong bảng.

Cách tiếp cận từ dưới lên

Sau khi giải pháp của một vấn đề được xây dựng đệ quy theo các bài toán con của nó, có thể cố gắng định dạng lại vấn đề theo hướng nâng lên: đầu tiên, chúng tôi sẽ cố gắng giải các bài toán con và sử dụng các giải pháp của chúng để đi đến lời giải cho các bài toán con lớn hơn.

Điều này cũng thường được thực hiện ở dạng bảng, tạo lặp đi lặp lại các giải pháp cho các bài toán con lớn hơn và lớn hơn bằng cách sử dụng các giải pháp cho các bài toán con nhỏ hơn. Ví dụ, nếu các giá trị của F31 và F30 đã được biết trước, thì giá trị của F32 có thể được tính trực tiếp.

So sánh với các kỹ thuật khác

Một đặc điểm quan trọng của một vấn đề có thể được giải quyết bằng lập trình động là nó phải có các bài toán con chồng lên nhau. Đây là những gì phân biệt lập trình động với kỹ thuật chia và chinh phục, nơi không cần thiết phải lưu trữ các giá trị đơn giản nhất.

Nó tương tự như đệ quy, vì khi tính toán các trường hợp cơ sở, giá trị cuối cùng có thể được xác định một cách quy nạp. Cách tiếp cận từ dưới lên này hoạt động tốt khi một giá trị mới chỉ phụ thuộc vào các giá trị đã được tính toán trước đó.

Thí dụ

Các bước tối thiểu để đạt được 1

Đối với bất kỳ số nguyên dương "e", bất kỳ bước nào trong ba bước sau đều có thể được thực hiện.

- Trừ 1 cho số. (e = e-1).

- Nếu chia hết cho 2 thì chia hết cho 2 (nếu e% 2 == 0 thì e = e / 2).

- Nếu chia hết cho 3 thì chia hết cho 3 (nếu e% 3 == 0 thì e = e / 3).

Dựa trên các bước ở trên, số bước tối thiểu cần được tìm thấy để đưa e về 1. Ví dụ:

- Nếu e = 1, kết quả: 0.

- Nếu e = 4, kết quả: 2 (4/2 = 2/2 = 1).

- Khi e = 7, kết quả: 3 (7-1 = 6/3 = 2/2 = 1).

Tiêu điểm

Người ta có thể nghĩ đến việc luôn chọn bước làm cho n càng thấp càng tốt và tiếp tục như vậy, cho đến khi nó đạt 1. Tuy nhiên, có thể thấy rằng chiến lược này không hoạt động ở đây.

Ví dụ, nếu e = 10, các bước sẽ là: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 bước). Tuy nhiên, dạng tối ưu là: 10-1 = 9/3 = 3/3 = 1 (3 bước). Do đó, tất cả các bước có thể thực hiện được đối với mỗi giá trị của n tìm được phải được thử, chọn số khả năng tối thiểu.

Tất cả bắt đầu bằng đệ quy: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} nếu e> 1, coi như trường hợp cơ sở: F (1) = 0. Có phương trình lặp lại, bạn có thể bắt đầu viết mã đệ quy.

Tuy nhiên, có thể thấy rằng nó có những bài toán con chồng chéo lên nhau. Hơn nữa, giải pháp tối ưu cho một đầu vào nhất định phụ thuộc vào giải pháp tối ưu cho các bài toán con của nó.

Như trong phần ghi nhớ, nơi các lời giải của các bài toán con đã giải được lưu trữ để sử dụng sau này. Hoặc như trong lập trình động, bạn bắt đầu ở phía dưới, làm việc theo cách của bạn lên đến e đã cho. Sau đó, cả hai mã:

Ghi nhớ

Lập trình động từ dưới lên

Lợi thế

Một trong những ưu điểm chính của việc sử dụng lập trình động là nó tăng tốc độ xử lý, vì các tham chiếu đã được tính toán trước đó được sử dụng. Vì nó là một kỹ thuật lập trình đệ quy, nó làm giảm các dòng mã trong chương trình.

Thuật toán phàm ăn và lập trình động

Các thuật toán tham lam tương tự như lập trình động ở chỗ cả hai đều là công cụ để tối ưu hóa. Tuy nhiên, thuật toán tham lam tìm kiếm một giải pháp tối ưu ở mỗi bước cục bộ. Đó là, nó tìm kiếm một sự lựa chọn tham lam với hy vọng tìm thấy một sự tối ưu toàn cầu.

Do đó, các thuật toán tham lam có thể đưa ra một giả định có vẻ tối ưu vào thời điểm đó, nhưng sẽ trở nên đắt đỏ trong tương lai và không đảm bảo là tối ưu toàn cầu.

Mặt khác, lập trình động tìm ra giải pháp tối ưu cho các bài toán con và sau đó đưa ra lựa chọn sáng suốt bằng cách kết hợp kết quả của các bài toán con đó để thực sự tìm ra giải pháp tối ưu nhất.

Nhược điểm

- Cần nhiều bộ nhớ để lưu kết quả tính toán của mỗi bài toán con mà không thể đảm bảo rằng giá trị đã lưu sẽ được sử dụng hay không.

- Nhiều khi, giá trị đầu ra được lưu trữ mà không bao giờ được sử dụng trong các bài toán con sau trong quá trình thực thi. Điều này dẫn đến việc sử dụng bộ nhớ không cần thiết.

- Trong lập trình động, các hàm được gọi là đệ quy. Điều này giúp bộ nhớ ngăn xếp không ngừng tăng lên.

Đệ quy và lập trình động

Nếu bạn có bộ nhớ hạn chế để chạy mã và tốc độ xử lý không phải là vấn đề đáng lo ngại, bạn có thể sử dụng đệ quy. Ví dụ: nếu bạn đang phát triển một ứng dụng di động, bộ nhớ rất hạn chế để chạy ứng dụng.

Nếu bạn muốn chương trình chạy nhanh hơn và không bị hạn chế về bộ nhớ, bạn nên sử dụng lập trình động.

Các ứng dụng

Lập trình động là một phương pháp hiệu quả để giải quyết các vấn đề mà nếu không có vẻ cực kỳ khó giải quyết trong một khoảng thời gian hợp lý.

Các thuật toán dựa trên mô hình lập trình động được sử dụng trong nhiều lĩnh vực khoa học, bao gồm nhiều ví dụ trong trí tuệ nhân tạo, từ lập kế hoạch giải quyết vấn đề đến nhận dạng giọng nói.

Các thuật toán dựa trên lập trình động

Lập trình động khá hiệu quả và hoạt động rất tốt cho một loạt các vấn đề. Nhiều thuật toán có thể được coi là ứng dụng thuật toán tham lam, chẳng hạn như:

- Dãy số Fibonacci.

- Tháp Hà Nội.

- Tất cả các cặp tuyến đường ngắn hơn qua Floyd-Warshall.

- Vấn đề ba lô.

- Lập kế hoạch dự án.

- Con đường ngắn nhất qua Dijkstra.

- Điều khiển máy bay và điều khiển robot.

- Các bài toán tối ưu hóa toán học.

- Timeshare: lên lịch công việc để CPU sử dụng tối đa.

Chuỗi số Fibonacci

Số Fibonacci là những số được tìm thấy trong dãy số sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, v.v.

Trong thuật ngữ toán học, dãy Fn của các số Fibonacci được xác định bằng công thức lặp lại: F (n) = F (n -1) + F (n -2), trong đó F (0) = 0 và F ( 1) = 1.

Cách tiếp cận từ trên xuống

Trong ví dụ này, một mảng tìm kiếm với tất cả các giá trị ban đầu được khởi tạo bằng -1. Bất cứ khi nào cần lời giải cho một bài toán con, ma trận tìm kiếm này sẽ được tìm kiếm đầu tiên.

Nếu giá trị được tính ở đó, thì giá trị đó sẽ được trả về. Nếu không, kết quả sẽ được tính toán để lưu trữ trong mảng tìm kiếm để có thể sử dụng lại sau này.

Cách tiếp cận từ dưới lên

Trong trường hợp này, đối với cùng một chuỗi Fibonacci, f (0) được tính trước, sau đó đến f (1), f (2), f (3), v.v. Do đó, các giải pháp của các bài toán con đang được xây dựng từ dưới lên.

Người giới thiệu

1. Vineet Choudhary (2020). Giới thiệu về Lập trình động. Developer Insider. Lấy từ: Developerinsider.co.
2. Alex Allain (năm 2020). Lập trình động trong C ++. Lập trình C. Lấy từ: cprogramming.com.
3. Sau Học viện (2020). Ý tưởng về Lập trình động. Lấy từ: afteracademy.com.
4. Aniruddha Chaudhari (2019). Lập trình động và đệ quy - Sự khác biệt, Ưu điểm với Ví dụ. Ngăn xếp CSE. Lấy từ: csestack.org.
5. Code Chef (2020). Hướng dẫn Lập trình Động. Lấy từ: codechef.com.
6. Programiz (2020). Lập trình năng động. Lấy từ: programmiz.com.