Nó là gì, nó hoạt động như thế nào và tài nguyên học tập
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 các bài toán tối ưu hóa phức tạp. Các vấn đề về tối ưu hóa yêu cầu bạn 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 để cho phép người bán hàng ghé thăm mỗi thành phố đúng một lần và quay trở lại thành phố bắt đầu.
Cách tiếp cận của Bellman đối với các bài toá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 đó, anh ta lưu trữ 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 đằng sau 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 nhỏ chúng thành các vấn đề con nhỏ hơn, giải quyết từng vấn đề con một lần và lưu trữ các giải pháp của chúng để có thể được sử dụng lại và kết hợp để giải quyết vấ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 các giải pháp được sử dụng lại.
Lập trình động hoạt động như thế nào?
Giải một bài toán bằng quy hoạch động bao gồm các bước sau:
Để thấy điều này trong thực tế, chúng tôi tính toán số Fibonacci thứ 6, F(6), sử dụng quy trình này.
Đầu tiên, xác định các vấn đề phụ cần được giải quyết.
F(n) = F(n-1) + F(n-2) với n > 1
Do đó: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Bước thứ hai liên quan đến việc giải quyết từng vấ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ả từ các bài toán con nhỏ hơn. Điều này mang lại cho chúng ta những điều sau đây:
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 chúng tôi giải quyết từng vấn đề phụ, chúng tôi lưu trữ các giải pháp trong một mảng hoặc bảng để chúng có thể được sử dụng lại trong việc giải quyết các vấn đề phụ lớn hơn như sau:
Khi tất cả các bài toán phụ đã được giải, 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, giải pháp cho vấn đề ban đầu là số Fibonacci thứ 6, được tìm thấy bằng cách tính tổng 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 ta 8.
Lập trình động được sử dụng ở đâu và tại sao?
Quy hoạch động được sử dụng trong các lĩnh vực mà chúng ta có các vấn đề có thể được chia thành các vấn đề con nhỏ hơn và các 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 quyết các vấn đề liên quan đến trình tự, đồ thị và giá trị 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 trong 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 đề trong phân bổ tài nguyên, lập kế hoạch, sản xuất, truyền thông và hệ thống điều khiển.
Có một số lợi thế khi sử dụng lập trình động để giải quyết các vấn đề tối ưu hóa:
Khi giải quyết các vấ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ả trong các giải pháp.
Các phương pháp được sử dụng trong lập trình động
Trong lập trình động, hai cách tiếp cận được sử dụng để giải các bài toán tối ưu. Đó 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 để làm cho các chương trình máy tính nhanh hơn bằng cách lưu trữ kết quả của các lệnh gọi hàm trong bộ nhớ đệm và trả lại kết quả đã lưu trong bộ đệm ẩn vào lần tiếp theo khi cần 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ố của nó. Đệ quy được sử dụng để chia bài toán thành các bài toán con nhỏ hơn và giải các bài toán con đó.
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ớ cache và được sử dụng lại bất cứ khi nào một vấn đề tương tự xảy ra. Phương pháp từ trên xuống dễ hiểu và dễ thực hiện và chỉ giải quyết một vấn đề phụ một lần. Tuy nhiên, nhược điểm của nó là nó chiếm rất nhiều bộ nhớ do đệ 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à lập bảng, loại bỏ đệ quy, thay thế nó bằng phép lặp, do đó tránh được lỗi tràn ngăn xếp.
Trong cách tiếp cận này, một vấn đề lớn được chia thành các vấn đề nhỏ hơn và các giải pháp cho các vấn đề phụ được sử dụng để giải quyết vấn đề lớn hơn.
Các bài toán con nhỏ hơn trước tiên được giải từ bài toán lớn nhất đến bài toá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.
Các kết quả được lưu trữ giải quyết các vấn đề lớn hơn phụ thuộc vào các vấn đề phụ. Kết quả của bài toán ban đầu sau đó đượ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ị đã tính toán trước đó.
Cách tiếp cận này có ưu điểm là bộ nhớ và thời gian hiệu quả bằng cách loại bỏ đệ quy.
Ví dụ về các vấn đề có thể được giải quyết bằng Quy hoạch động
Sau đâ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 đề ba lô
Nguồn: Wikipedia
Ba lô là một chiếc túi làm bằng vải bạt, nylon hoặc da thường được buộc sau lưng và được binh lính và người đi bộ đường dài sử dụng để mang theo đồ tiếp tế.
Trong bài toán về chiếc ba lô, bạn được đưa cho một chiếc ba lô và với khả năng mang theo của nó, bạn được yêu cầu chọn các món đồ, mỗi món đồ đều có giá trị của nó. 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 vật phẩm đã chọn và trọng lượng của các vật phẩm đó nhỏ hơn hoặc bằng sức chứa của ba lô.
Một ví dụ về vấn đề ba lô được đưa ra dưới đây:
Hãy tưởng tượng rằng bạn đang thực hiện một chuyến đi bộ đường dài và có một chiếc ba lô nặng 15 kg. Bạn có một danh sách các mặt hàng mà bạn có thể mang theo bên mình, cùng với giá trị và trọng lượng của chúng, như trong bảng bên dưới:
Hạng mụcGiá trịTrọng lượngLều2003Túi ngủ1502Bếp501Thức ăn1002Chai nước100.5Bộ sơ cứu251
Chọn một nhóm nhỏ các mặt hàng cần mang theo sao cho tổng giá trị của các mặt hàng là lớn nhất trong khi tổng trọng lượng nhỏ hơn hoặc bằng sức chứa của ba lô, tức là 15 kg.
Các ứng dụng trong thế giới thực của bài toán chiếc 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 cũng như tìm ra những cách ít lãng phí nhất để cắt giảm nguyên liệu thô.
#2. vấn đề lập kế hoạch
Bài toán lập lịch trình là một bài toán tối ưu hóa trong đó mục tiêu là phân công nhiệm vụ một cách tối ưu cho một tập hợp các nguồn lực. Tài nguyên có thể là máy móc, nhân sự hoặc các tài nguyên khác được sử dụng để hoàn thành nhiệm vụ.
Một ví dụ về vấn đề lập lịch trình được đưa ra dưới đây:
Hãy tưởng tượng rằ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ụ cần được hoàn thành 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ững nhân viên đủ điều kiện để hoàn thành 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úcNhân viên có năng lựcT1911A,B,CT21012A,CT31113B,CT41214A,B
Giao từng nhiệm vụ cho một nhân viên để giảm thiểu tổng thời gian hoàn thành.
Vấn đề lập lịch trình 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ể gặp phải trong chăm sóc sức khỏe khi tối ưu hóa việc sử dụng giường bệnh, nhân sự và vật tư y tế. Các ngành khác mà vấn đề này có thể xảy ra là quản lý dự án, quản lý chuỗi cung ứng và giáo dục.
#3. Vấn đề người bán hàng du lịch
Nguồn: Wikipedia
Đây là một trong những bài toán tối ưu được nghiên cứu nhiều nhất có thể giải bằng quy hoạch động.
Bài toán người bán hàng lưu động cung cấp 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 yêu cầu tìm con đường ngắn nhất có thể đến mỗi thành phố đúng một lần và quay trở lại thành phố ban đầu.
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 rằ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 có thể. Bạn có một danh sách các thành phố mà bạn cần đến 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
Bài toán nhân viên bán hàng du lịch có thể gặp phải trong ngành giải trí khi cố gắng lập kế hoạch 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 tải khi lập kế hoạch tuyến xe buýt và trong ngành bán hàng, v.v.
Rõ ràng, lập trình động có nhiều ứng dụng trong thế giới thực, giúp tìm hiểu thêm về nó.
Xem xét các tài nguyên sau đây để giải thích 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à một cuốn sách của Richard Bellman, người đã nghĩ ra lập trình động và phát triển nó trong giai đoạn đầu.
Cuốn sách được viết một cách dễ hiểu, chỉ cần kiến thức cơ bản về toán học và giải tích để hiểu văn bản. Trong cuốn sách, Bellman giới thiệu lý thuyết toán học về quy trình quyết định nhiều giai đoạn, vốn là chìa khóa trong quy hoạch động.
Sau đó, cuốn sách xem xét các vấn đề thắt cổ chai trong quy trình sản xuất nhiều giai đoạn, các định lý về sự tồn tại và tính duy nhất cũng như phương trình hàng tồn kho tối ưu.
Điểm hay nhất của cuốn sách là Bellman đưa ra các 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 lịch trình, lý thuyết truyền thông, kinh tế toán học và các 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 các vấn đề đó.
Cuốn sách có sẵn trong các phiên bản Kindle, bìa cứng và bìa mềm.
Khóa học thạc sĩ giải thuật lập trình động
Khóa học tổng thể về thuật toán lập trình động này của Udemy được cung cấp bởi Apaar Kamal, một kỹ sư phần mềm tại Google và Prateek Narang, người cũng đã làm việc với Google.
Khóa học được tối ưu hóa nhằm giúp người học vượt trội trong cuộc thi lập trình vốn có rất nhiều bài toán yêu cầu lập trình động.
Bên cạnh các đối thủ cạnh tranh về lập trình, khóa học 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 một cách chuyên sâu. Đầu tiên, khóa học cung cấp nội dung ôn lại 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 & đồ thị, phép lũy thừa ma trận, mặt nạ bit, tổ hợp & chuỗi con, bài toán phân vùng và lập trình động đa chiều, cùng nhiều khái niệm khác.
Yếu tố cần thiết về lập trình cạnh tranh, thuật toán chính
Udemy cung cấp Khóa học cơ bản về lập trình cạnh tranh của Prateek Narang và Amal Kamaar bao gồm lập trình động, toán học, lý thuyết số và cấu trúc dữ liệu nâng cao & thuật toán 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 ôn tập 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 có í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, Bitmasking và vô số 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 mô-đun và 42 phần và cung cấp rất 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à khóa học bắt buộc đối với bất kỳ ai quan tâm đến lập trình cạnh tranh.
Từ cuối cùng
Lập trình động là một kỹ năng hữu ích cho bất kỳ lập trình viên nào để học cách cải thiện khả năng giải quyết vấn đề của họ đối với các vấn đề trong thế giới thực. Do đó, các lập trình viên nên cân nhắc xem qua các tài nguyên được đề xuất để thêm công cụ quan trọng này vào hộp công cụ của họ.
Tiếp theo, 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.
