Lập trình động là một khái niệm được phát triển bởi Richard Bellman, một nhà toán học và kinh tế học.
Vào thời điểm đó, Bellman đang tìm cách giải quyết các vấn đề tối ưu hóa phức tạp. Các vấn đề tối ưu hóa yêu cầu bạn phải chọn giải pháp tốt nhất từ một tập hợp các tùy chọn.
Một ví dụ về bài toán tối ưu hóa là bài toán người bán hàng du lịch. Mục tiêu là tìm ra con đường ngắn nhất để người bán có thể ghé thăm mỗi thành phố đúng một lần và quay lại thành phố xuất phát.
Cách tiếp cận của Bellman đối với những vấn đề này là chia chúng thành các bài toán con nhỏ hơn và giải các bài toán con từ nhỏ nhất đến lớn nhất. Sau đó, ông lưu kết quả của các bài toán con và sử dụng lại chúng để giải các bài toán con lớn hơn. Đây là ý tưởng chính của lập trình động.
Lập trình động là gì?
Lập trình động giải quyết các vấn đề tối ưu hóa bằng cách chia chúng thành các bài toán con nhỏ hơn, giải từng bài toán con một lần và lưu trữ lời giải của chúng để có thể sử dụng lại và kết hợp để giải quyết bài toán lớn hơn. Các vấn đề được giải quyết từ nhỏ nhất đến lớn nhất, cho phép tái sử dụng các giải pháp.
Lập trình động hoạt động như thế nào?
Giải bài toán bằng quy hoạch động bao gồm các bước sau:
Để thấy được điều này trong thực tế, chúng ta tính số Fibonacci thứ sáu, F(6) bằng cách sử dụng quá trình này.
Đầu tiên, xác định các vấn đề con cần giải quyết.
F(n) = F(n-1) + F(n-2) với n > 1
Vì vậy: F(6) = F(5) + F(4)
fa(5) = f(4) + f(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
fa(2) = f(1) + f(0)
F(1) = 1
F(0) = 0
Bước thứ hai liên quan đến việc giải từng bài toán con bằng cách sử dụng hàm đệ quy hoặc quy trình lặp. Chúng ta giải các bài toán con từ nhỏ nhất đến lớn nhất, sử dụng lại kết quả của các bài toán con nhỏ hơn. Điều này mang lại cho chúng tôi:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Khi giải từng bài toán con, chúng ta lưu trữ lời giải trong một mảng hoặc bảng để chúng có thể được sử dụng lại khi giải các bài toán con lớn hơn, chẳng hạn như:
Sau khi giải quyết tất cả các bài toán con, chúng ta sử dụng các lời giải để xây dựng lời giải cho bài toán ban đầu.
Trong trường hợp này, lời giải của bài toán ban đầu là số Fibonacci thứ sáu, có thể tìm được bằng cách tính tổng các kết quả của F(5) và F(4), các bài toán con được xác định từ bài toán lớn nhất. Kết quả cho chúng ta 8.
Lập trình động được sử dụng ở đâu và tại sao?
Lập trình động được sử dụng trong các lĩnh vực mà chúng ta gặp các vấn đề có thể chia thành các vấn đề phụ nhỏ hơn và giải pháp của chúng được sử dụng để giải quyết các vấn đề lớn hơn.
Những lĩnh vực này bao gồm khoa học máy tính, kinh tế, toán học và kỹ thuật. Trong khoa học máy tính, nó được sử dụng để giải các bài toán liên quan đến dãy số, đồ thị, số nguyên và trong lập trình cạnh tranh.
Trong kinh tế, nó được sử dụng để giải quyết các vấn đề tối ưu hóa về tài chính, sản xuất và phân bổ nguồn lực. Trong toán học, quy hoạch động được sử dụng trong lý thuyết trò chơi, thống kê và xác suất trong đó nó được sử dụng để giải các bài toán tối ưu hóa.
Trong kỹ thuật, nó được sử dụng để giải quyết các vấn đề liên quan đến hệ thống phân bổ nguồn lực, lập kế hoạch, sản xuất, truyền thông và điều khiển.
Sử dụng quy hoạch động để giải các bài toán tối ưu hóa có một số ưu điểm:
Khi giải quyết các bài toán tối ưu hóa, quy hoạch động là một công cụ rất hữu ích để đảm bảo tính hiệu quả của lời giải.
Các phương pháp được sử dụng trong lập trình động
Trong quy hoạch động, có hai cách tiếp cận được sử dụng để giải các bài toán tối ưu hóa. Đó là cách tiếp cận từ trên xuống và cách tiếp cận từ dưới lên.
Cách tiếp cận từ trên xuống
Cách tiếp cận này còn được gọi là ghi nhớ. Ghi nhớ là một kỹ thuật tối ưu hóa chủ yếu được sử dụng để tăng tốc các chương trình máy tính bằng cách lưu trữ kết quả của các lệnh gọi hàm trong bộ đệm và trả về kết quả từ bộ đệm vào lần tiếp theo thay vì tính toán lại chúng.
Cách tiếp cận từ trên xuống liên quan đến đệ quy và bộ nhớ đệm. Đệ quy liên quan đến một hàm gọi chính nó với các phiên bản đơn giản hơn của vấn đề làm đối số. Đệ quy được sử dụng để chia một bài toán thành các bài toán con nhỏ hơn và giải quyết các bài toán con.
Sau khi một vấn đề phụ được giải quyết, kết quả của nó sẽ được lưu vào bộ nhớ đệm và sử dụng lại bất cứ khi nào vấn đề tương tự xảy ra. Cách tiếp cận từ trên xuống rất dễ hiểu và dễ thực hiện và chỉ giải quyết được vấn đề phụ một lần. Tuy nhiên, nhược điểm là nó chiếm nhiều bộ nhớ do phải đệ quy. Điều này có thể dẫn đến lỗi tràn ngăn xếp.
Cách tiếp cận từ dưới lên
Cách tiếp cận từ dưới lên, còn được gọi là tab, loại bỏ đệ quy bằng cách thay thế nó bằng phép lặp, do đó tránh được lỗi tràn ngăn xếp.
Theo cách tiếp cận này, một bài toán lớn được chia thành các bài toán con nhỏ hơn và giải pháp cho các bài toán con đó được sử dụng để giải quyết bài toán lớn hơn.
Các bài toán con nhỏ hơn được giải trước tiên từ lớn nhất đến nhỏ nhất và kết quả của chúng được lưu trữ trong một ma trận, mảng hoặc bảng, do đó có tên là lập bảng.
Kết quả đã lưu giải quyết được các bài toán lớn hơn phụ thuộc vào các bài toán con. Sau đó, kết quả của bài toán ban đầu được tìm thấy bằng cách giải bài toán con lớn nhất bằng cách sử dụng các giá trị được tính toán trước đó.
Cách tiếp cận này có ưu điểm là tiết kiệm bộ nhớ và thời gian bằng cách loại bỏ đệ quy.
Ví dụ về các vấn đề có thể giải quyết bằng quy hoạch động
Dưới đây là một số vấn đề lập trình có thể được giải quyết bằng lập trình động:
# 1. Vấn đề về ba lô
Nguồn: Wikipedia
Ba lô là một chiếc túi làm bằng vải, nylon hoặc da, thường được buộc chặt ở phía sau và được binh lính và khách du lịch sử dụng để đựng đồ tiếp tế.
Trong bài toán ba lô, bạn có một chiếc ba lô, và với khả năng chuyên chở của nó, bạn cần chọn những món đồ mà mỗi món đồ đều có một giá trị. Lựa chọn của bạn phải sao cho bạn nhận được tổng giá trị tối đa của các món đồ đã chọn và trọng lượng của món đồ đó nhỏ hơn hoặc bằng sức chứa của ba lô của bạn.
Một ví dụ về bài toán chiếc ba lô được đưa ra dưới đây:
Hãy tưởng tượng rằng bạn đang đi bộ đường dài và bạn có một chiếc ba lô có sức chứa 15 kg. Bạn có một danh sách các đồ vật có thể mang theo bên mình, cùng với giá trị và trọng lượng của chúng, như thể hiện trong bảng bên dưới:
Mặt hàngGiá trịTrọng lượngLều2003Túi ngủ1502Bếp501Thức ăn1002Bình nước100.5Bộ sơ cứu251
Chọn một tập hợp nhỏ các đồ vật cần mang theo sao cho tổng giá trị đồ đạc là lớn nhất và tổng trọng lượng nhỏ hơn hoặc bằng sức chứa của ba lô là 15 kg.
Các ứng dụng thực tế của bài toán ba lô liên quan đến việc lựa chọn chứng khoán để thêm vào danh mục đầu tư nhằm giảm thiểu rủi ro và tối đa hóa lợi nhuận, đồng thời tìm ra những cách ít lãng phí nhất để giảm nguyên liệu thô.
#2. Vấn đề về lịch trình
Bài toán lập kế hoạch là một bài toán tối ưu hóa trong đó mục tiêu là phân công các nhiệm vụ một cách tối ưu cho một tập hợp các nguồn lực. Nguồn lực có thể là máy móc, nhân sự hoặc các nguồn lực khác được sử dụng để hoàn thành nhiệm vụ.
Sau đây là một ví dụ về bài toán lập kế hoạch:
Hãy tưởng tượng bạn là người quản lý dự án chịu trách nhiệm lập kế hoạch cho một nhóm nhiệm vụ phải được thực hiện bởi một nhóm nhân viên. Mỗi nhiệm vụ đều có thời gian bắt đầu, thời gian kết thúc và danh sách nhân viên được ủy quyền thực hiện.
Dưới đây là bảng mô tả các nhiệm vụ và đặc điểm của chúng:
Nhiệm vụThời gian bắt đầuThời gian kết thúcCông nhân lành nghềT1911A, B, CT21012A, CT31113B, CT41214A, B
Phân công từng nhiệm vụ cho nhân viên để giảm thiểu tổng thời gian hoàn thành.
Vấn đề lập kế hoạch có thể gặp phải trong ngành sản xuất khi cố gắng tối ưu hóa việc phân bổ các nguồn lực như máy móc, vật liệu, công cụ và lao động.
Nó cũng có thể được tìm thấy trong chăm sóc sức khỏe, tối ưu hóa việc sử dụng giường bệnh, nhân viên và vật tư y tế. Các ngành khác có thể xảy ra vấn đề này bao gồm quản lý dự án, quản lý chuỗi cung ứng và giáo dục.
#3. Vấn đề nhân viên bán hàng du lịch
Nguồn: Wikipedia
Đây là một trong những vấn đề tối ưu hóa được nghiên cứu nhiều nhất và có thể giải quyết bằng quy hoạch động.
Bài toán người bán hàng du lịch chứa một danh sách các thành phố và khoảng cách giữa mỗi cặp thành phố. Bạn cần tìm con đường ngắn nhất có thể ghé thăm mỗi thành phố đúng một lần và quay trở lại thành phố xuất phát.
Một ví dụ về bài toán người bán hàng du lịch được đưa ra dưới đây:
Hãy tưởng tượng bạn là một nhân viên bán hàng cần đến thăm một số thành phố trong thời gian ngắn nhất. Bạn có một danh sách các thành phố bạn phải ghé thăm và khoảng cách giữa mỗi cặp thành phố như trong bảng dưới đây:
Thành phốABCDEA010152030B100352515C153503020D202530010E301520100
Vấn đề nhân viên bán hàng du lịch có thể gặp phải, trong số những vấn đề khác, trong ngành giải trí khi cố gắng lập kế hoạch các tuyến đường cho khách du lịch, hậu cần khi lập kế hoạch vận chuyển hàng hóa, vận chuyển khi lập kế hoạch các tuyến xe buýt và trong ngành bán hàng.
Tất nhiên, lập trình động có nhiều ứng dụng trong thế giới thực, giúp bạn tìm hiểu thêm về nó.
Sử dụng các tài nguyên sau để mở rộng kiến thức của bạn về lập trình động.
Tài nguyên
Lập trình động của Richard Bellman
Lập trình động là cuốn sách của Richard Bellman, người đã phát minh ra lập trình động và phát triển nó trong giai đoạn đầu.
Sách được viết dễ hiểu, chỉ cần kiến thức cơ bản về toán học và giải tích là có thể hiểu được văn bản. Trong cuốn sách, Bellman trình bày lý thuyết toán học về việc ra quyết định nhiều giai đoạn, là trọng tâm của lập trình động.
Sau đó, cuốn sách xem xét các điểm nghẽn trong quy trình sản xuất nhiều giai đoạn, các định lý tồn tại và duy nhất cũng như phương trình tồn kho tối ưu.
Điểm hay nhất của cuốn sách này là Bellman đưa ra ví dụ về nhiều vấn đề phức tạp trong các lĩnh vực như hậu cần, lý thuyết lập kế hoạch, lý thuyết truyền thông, toán kinh tế và quy trình điều khiển, đồng thời chỉ ra cách lập trình động có thể giải quyết những vấn đề này.
Cuốn sách có sẵn trong phiên bản Kindlebìa cứng và bìa mềm.
Khóa học thạc sĩ về thuật toán lập trình động
Lớp học nâng cao về thuật toán lập trình động của Udemy này được cung cấp bởi Apaar Kamal, kỹ sư phần mềm tại Google và Prateek Naranga, người cũng từng làm việc với Google.
Khóa học được tối ưu hóa để giúp học viên thành công trong cuộc thi lập trình có nhiều bài toán lập trình động.
Ngoài các thí sinh lập trình, khóa học này còn lý tưởng cho các lập trình viên muốn nâng cao hiểu biết về thuật toán và những người chuẩn bị cho các cuộc phỏng vấn lập trình và các vòng viết mã trực tuyến.
Khóa học kéo dài hơn 40 giờ, bao gồm lập trình động chuyên sâu. Khóa học đầu tiên cung cấp kiến thức cập nhật về các khái niệm như đệ quy và quay lui.
Sau đó, nó bao gồm lập trình động trong lý thuyết trò chơi, chuỗi, cây và đồ thị, lũy thừa ma trận, mặt nạ bit, tổ hợp và dãy con, các vấn đề phân vùng và lập trình động đa chiều, cùng nhiều khái niệm khác.
Nguyên tắc cơ bản của lập trình cạnh tranh, các thuật toán chính
Udemy cung cấp khóa học Nguyên tắc lập trình cạnh tranh do Prateek Narang và Amal Kamaar giảng dạy, bao gồm lập trình động, toán học, lý thuyết số cũng như các cấu trúc dữ liệu và thuật toán nâng cao theo cách hữu ích và phù hợp với các lập trình viên cạnh tranh.
Khóa học cung cấp kiến thức mới về cấu trúc dữ liệu và thuật toán trước khi đi sâu vào các thuật toán và kỹ thuật phức tạp hơn hữu ích trong lập trình cạnh tranh.
Khóa học bao gồm lập trình động, toán học, lý thuyết trò chơi, khớp mẫu, mặt nạ bit và rất nhiều thuật toán nâng cao được sử dụng và thử nghiệm trong các cuộc thi lập trình.
Khóa học Udemy được chia thành 10 học phần và 42 phần, với nhiều câu hỏi thực hành sau mỗi phần. Khóa học bán chạy nhất này là một khóa học phải đọc đối với bất kỳ ai quan tâm đến lập trình cạnh tranh.
những từ cuối
Lập trình động là một kỹ năng có lợi cho bất kỳ lập trình viên nào học cách cải thiện việc giải quyết các vấn đề trong thế giới thực. Do đó, các nhà phát triển nên cân nhắc xem xét các tài nguyên được đề xuất để thêm công cụ quan trọng này vào bộ công cụ của họ.
Sau đó, bạn có thể kiểm tra các ngôn ngữ lập trình để sử dụng trong khoa học dữ liệu.
