Lập trình động là một thuật ngữ có thể đã được sử dụng cho đến bây giờ nếu bạn đã ở trong lĩnh vực này trong một khoảng thời gian dài. Chủ đề này thường xuyên xuất hiện trong các cuộc họp đánh giá thiết kế và trong các tương tác hàng ngày của các kỹ sư và nó cũng là tâm điểm trong các cuộc phỏng vấn kỹ thuật. Chiến lược chia để trị là một phương pháp hoàn hảo để đạt được bất kỳ mục tiêu nào. Trong lập trình máy tính, ý tưởng này cũng đúng. Nhiều khó khăn có các loại phụ có thể được phân lập và xử lý riêng, cho phép giải quyết vấn đề chính một cách triệt để. Trong bài viết này, chúng ta sẽ thảo luận về thuật toán lập trình động và Python.
Lập trình động là gì?
Lập trình động là một phương pháp để giải quyết các vấn đề phức tạp bằng cách đầu tiên giảm chúng thành những vấn đề đơn giản hơn, sau đó sử dụng các giải pháp cho các vấn đề đơn giản hơn đó làm khối xây dựng để giải quyết vấn đề ban đầu.
Chúng tôi phân chia vấn đề hiện tại thành các phần có thể quản lý được. Trong hầu hết các trường hợp, sự khác biệt thực sự duy nhất giữa vấn đề của cha mẹ và vấn đề của con cái là quy mô tương đối của chúng. Do đó, những vấn đề nhỏ này có thể được chia thành nhiều vấn đề nhỏ hơn nữa, v.v., vô thời hạn. Hãy tưởng tượng rằng một vấn đề và các vấn đề con khác nhau của nó tạo thành một cái cây. Các vấn đề về “chiếc lá” được giải quyết trước tiên, tiếp theo là các vấn đề về “cha mẹ” của chúng, và cứ tiếp tục như vậy trên cây vấn đề. Khi chúng tôi giải quyết những khó khăn nhỏ hơn, chúng tôi ghi lại tiến trình của mình để sử dụng sau này. Điều này cho phép chúng ta bỏ qua phần đó của vấn đề trong tương lai.
Phương pháp này tương tự như kỹ thuật chia để trị ở chỗ nó chia một vấn đề thành các vấn đề nhỏ hơn có thể được giải độc lập và sau đó kết hợp lại để có được giải pháp cuối cùng.
Lập trình động hoạt động như thế nào?
Lập trình động hiệu quả vì nó đơn giản hóa các vấn đề khó bằng cách phân tách chúng thành các phần cấu thành. Bước tiếp theo là xác định câu trả lời tốt nhất cho những thách thức tiếp theo này. Kết quả của các quy trình này có thể được ghi nhớ để có thể truy xuất các giải pháp tương ứng từ bộ lưu trữ và sử dụng mà không cần tính toán thêm. Ngoài ra, lời giải có thể được lưu lại để tránh tính toán lại các bài toán con đã giải trước đó.
Có hai phương pháp để thực hiện lập trình động:
#1. Cách tiếp cận từ trên xuống
Trong khoa học máy tính, các vấn đề thường được giải quyết bằng cách xây dựng các giải pháp theo cách đệ quy hoặc bằng cách sử dụng kết quả của các bước trước đó để giải quyết vấn đề hiện tại. Có thể ghi nhớ hoặc giữ một bảng lời giải cho các bài toán con nếu chúng tương tự nhau. Phương pháp từ trên xuống dựa trên việc học thuộc lòng. Ghi nhớ cũng giống như thực hiện đệ quy và lưu vào bộ nhớ đệm hai lần. Đệ quy liên quan đến việc thực hiện một cuộc gọi gián tiếp đến hàm, trong khi bộ nhớ đệm liên quan đến việc theo dõi các kết quả trung gian.
Trong số nhiều ưu điểm của cách tiếp cận từ trên xuống là:
- Phương pháp từ trên xuống rất đơn giản để nắm bắt và áp dụng. Để hiểu rõ hơn những gì cần phải làm, phương pháp này giải cấu trúc các vấn đề thành các yếu tố cấu thành của chúng. Mỗi bước phát triển mới đều mang theo nó sự giải tỏa một trở ngại không thể vượt qua trước đây. Một số phần thậm chí có thể được áp dụng cho các vấn đề khác.
- Nó cho phép giải các bài toán con theo yêu cầu. Phương pháp từ trên xuống sẽ cho phép phân tách các vấn đề thành các phần có thể quản lý được, với các giải pháp cho các phần đó được lưu trữ để sử dụng sau này. Sau đó, khách hàng có thể yêu cầu trợ giúp sửa từng bộ phận.
- Gỡ lỗi cũng được đơn giản hóa. Chia một vấn đề thành các phần nhỏ hơn giúp bạn dễ dàng theo dõi câu trả lời hơn và nhận ra những sai lầm tiềm ẩn.
Sau đây là một số nhược điểm của việc sử dụng cách tiếp cận từ trên xuống:
- Chiến lược từ trên xuống sử dụng phương thức đệ quy, chiếm nhiều bộ nhớ hơn trong ngăn xếp cuộc gọi so với các phương pháp khác. Điều này cuối cùng dẫn đến giảm hiệu suất. Ngoài ra, tràn ngăn xếp có thể xảy ra nếu đệ quy lùi quá xa về quá khứ.
#2. Cách tiếp cận từ dưới lên
Sau khi giải pháp của một vấn đề được thể hiện dưới dạng các bài toán con của nó theo kiểu tự lặp lại, người dùng có thể viết lại bài toán bằng cách sử dụng phương pháp tiếp cận từ dưới lên, trong đó họ giải quyết các bài toán con nhỏ hơn trước rồi áp dụng các giải pháp của họ cho các bài toán lớn hơn .
Trái ngược với phương pháp từ trên xuống, đệ quy bị loại bỏ khi sử dụng phương pháp từ dưới lên. Do đó, các hàm đệ quy không thêm chi phí không cần thiết hoặc khiến ngăn xếp bị tràn. Ngoài ra, nó cho phép nén dữ liệu. Độ phức tạp về thời gian của đệ quy được giảm bớt bằng cách loại bỏ nhu cầu tính toán lại các giá trị giống nhau.
Một số lợi ích của việc làm việc từ đầu như sau:
- Đầu tiên, nó xác định cách một bài toán lớn sẽ được xây dựng từ các bài toán con nhỏ hơn, có thể tái sử dụng.
- Bằng cách loại bỏ đệ quy, nó giúp tận dụng tốt hơn bộ nhớ khả dụng. Độ phức tạp về thời gian được giảm xuống như một tác dụng phụ.
Đặc điểm của lập trình động
Có hai đặc điểm phân biệt của lập trình động:
#1. Các bài toán con chồng lên nhau
Các sửa đổi của một vấn đề chính dễ quản lý hơn được gọi là "các vấn đề con". Dãy Fibonacci, trong đó mỗi số bằng tổng của hai số liền trước (0, 1, 1, 2, 3, 5, 8,…). Bạn có thể chia nhiệm vụ tìm giá trị thứ n trong dãy Fibonacci thành nhiều phần dễ quản lý hơn. Khi bạn tìm giải pháp bằng cách giải quyết lặp đi lặp lại cùng một vấn đề con, những khó khăn chồng chéo này ngày càng trở nên khó giải quyết.
Lập trình động có thể được sử dụng để phân vùng các công việc lập trình lớn thành các phần có thể quản lý được do sự xuất hiện phổ biến của các bài toán con chồng chéo.
#2. Cấu trúc con có tính chất tối ưu
Tính chất của cấu trúc con tối ưu thể hiện khi có thể tạo ra một giải pháp tối ưu từ các giải pháp cho tất cả các bài toán con. Để đệ quy hoạt động, bạn phải áp dụng câu trả lời mà bạn rút ra từ mỗi lần trùng lặp cho toàn bộ vấn đề. Thuộc tính cấu trúc con tối ưu được hiển thị bởi toàn bộ bài toán khi, như trong trường hợp của dãy Fibonacci, mỗi bài toán con có một giải pháp có thể được áp dụng cho bài toán con tiếp theo trong dãy để xác định giá trị của nó.
Sử dụng lập trình động trong thế giới thực
Dưới đây là những công dụng của lập trình động.
#1. vấn đề ba lô
Quy hoạch động đã được sử dụng rộng rãi để giải quyết vấn đề về chiếc ba lô. Đây là những vấn đề chúng tôi đang phải đối mặt:
Giá trị lý tưởng cho mỗi vấn đề phụ, được xác định bởi số lượng mục được đề cập và dung lượng còn lại trong ba lô, có thể được lưu trữ trong một mảng hai chiều, giúp giải quyết vấn đề này nhanh chóng. Chúng tôi có thể tối đa hóa giá trị bằng cách bao gồm hoặc loại trừ mặt hàng hiện tại ở mỗi giai đoạn. Câu trả lời có thể được tìm thấy ở góc dưới bên phải của mảng.
Vấn đề về chiếc ba lô có thể được sử dụng trong nhiều ngữ cảnh khác nhau, từ đóng gói hành lý đến đưa ra quyết định đầu tư đến phân bổ nguồn lực.
#2. Đường đi ngắn nhất của tất cả các cặp
Bài toán đường đi ngắn nhất trong đồ thị có trọng số là một cách sử dụng điển hình khác của quy hoạch động. Sử dụng các kỹ thuật như Floyd-Warshall hoặc Bellman-Ford, chúng ta có thể tìm ra đường đi ngắn nhất giữa hai cặp nút bất kỳ đã cho.
Để theo dõi đường đi ngắn nhất giữa hai nút bất kỳ, các thuật toán này sử dụng một mảng ba chiều. Ngoài ra, để theo dõi khoảng cách từ điểm bắt đầu, họ so sánh kết quả với khoảng cách giữa điểm bắt đầu và nút trung gian ở mỗi giai đoạn. Rốt cuộc, các bước lặp đã hoàn tất, giải pháp cuối cùng sẽ là ma trận khoảng cách.
Có một số cách sử dụng để giải quyết vấn đề đường đi ngắn nhất cho tất cả các cặp, chẳng hạn như trong phân tích mạng, định tuyến, điều hướng, phân tích mạng xã hội, v.v.
#3. đường may khắc
Trong lĩnh vực xử lý ảnh, khắc đường nối là một ứng dụng hấp dẫn của lập trình động. Nhiệm vụ hiện tại là giảm kích thước của hình ảnh mà không làm thay đổi bất kỳ đặc điểm cơ bản nào của nó. Các tuyến năng lượng thấp trong một hình ảnh, được gọi là đường nối, có thể được sử dụng để trừ hoặc thêm pixel để đạt được hiệu ứng này.
Sử dụng lập trình động, chúng ta có thể tính toán năng lượng tích lũy của từng pixel trong ảnh dựa trên độ dốc và các lân cận của nó, sau đó sử dụng thông tin đó để xác định nên loại bỏ hoặc thêm các đường nối nào. Sau đó, bằng cách đi lên từ dưới cùng của bức tranh, chúng ta có thể xác định vị trí đường may có ít thế năng nhất. Phương pháp này có thể được sử dụng lại cho đến khi đạt được kích thước yêu cầu.
Ngoài ra, hình ảnh có thể được thay đổi kích thước, cắt xén, nhắm mục tiêu lại và hơn thế nữa với sự trợ giúp của khắc đường may.
#4. Học máy và bộ gen
Các thách thức về máy học và bộ gen như căn chỉnh trình tự, mô hình Markov ẩn và cây phát sinh gen đều có thể tuân theo khả năng giải quyết vấn đề của lập trình động.
Căn chỉnh nhiều chuỗi ký hiệu (thường là DNA hoặc protein) để khám phá những điểm tương đồng được gọi là căn chỉnh trình tự. Điều này có thể làm sáng tỏ các mối liên kết tiến hóa, chức năng trong xã hội hoặc đặc điểm cấu trúc của chúng. Có thể tìm thấy sự sắp xếp tối ưu thông qua lập trình động bằng cách chỉ định điểm số cho các điểm trùng khớp và không khớp giữa các chuỗi.
Các mô hình xác suất được gọi là mô hình Markov ẩn được sử dụng để mô tả dữ liệu chuỗi thời gian có điều kiện ở các trạng thái chưa biết. Chúng rất hữu ích để lập mô hình các hiện tượng khó như nhận dạng giọng nói, NLP, tin sinh học, v.v. Khi được cung cấp một tập hợp các quan sát, các kỹ thuật lập trình động như Viterbi và Forward-Backward có thể xác định chuỗi trạng thái ẩn có khả năng nhất.
Cây phát sinh gen cho thấy mối liên hệ giữa các loài hoặc gen theo thời gian. Có thể suy ra tổ tiên chung, ngày phân kỳ và các sự kiện tiến hóa từ những điểm tương đồng này. Ngoài ra, một thuật toán lập trình động như Fitch và Sankoff có thể được sử dụng để tạo ra các cây phát sinh gen tối ưu bằng cách sử dụng dữ liệu giải trình tự.
# 5. Mật mã học
Mật mã học, nghiên cứu về giao tiếp bí mật, cũng được hưởng lợi từ khả năng giải quyết vấn đề của lập trình động. Mã hóa, giải mã, chữ ký số, xác thực và các quy trình tương tự khác đều là một phần của mật mã.
Mã hóa chuyển đổi thông tin từ con người có thể đọc được thành khóa bí mật có thể đọc được. Giải mã là quá trình chuyển đổi dữ liệu được mã hóa trở lại thành văn bản gốc bằng khóa gốc hoặc khóa mới. Chữ ký số cho phép xác minh tính xác thực và tính toàn vẹn của tin nhắn hoặc tài liệu. Kiểm tra thông tin đăng nhập của người gửi hoặc người nhận có thể xác minh danh tính của người gửi hoặc người nhận.
Các loại mật mã khác nhau, bao gồm mật mã khóa động, mật mã dựa trên mã và mật mã dựa trên lập trình động, đều có thể được triển khai bằng lập trình động.
Mật mã khóa động là một cơ chế mã hóa và giải mã thông điệp bằng các khóa thay đổi liên tục. Các khóa "động" là những khóa phát triển theo thời gian hoặc phản ứng với các yếu tố khác. Điều này làm cho chúng an toàn hơn so với các khóa tĩnh, dễ bị tấn công. Có thể sử dụng lập trình động để tạo và cập nhật các khóa khi triển khai mật mã khóa động.
Sử dụng một kỹ thuật được gọi là mật mã dựa trên mã, có thể mã hóa và giải mã thông báo bằng cách sử dụng mã sửa lỗi trong quá trình thực hiện. Có thể sửa lỗi đường truyền bằng mã sửa lỗi. Việc sử dụng mật mã dựa trên mã được nhiều người coi là kháng lượng tử vì nó an toàn trước các cuộc tấn công từ máy tính lượng tử. Lập trình động có thể được sử dụng để mã hóa và giải mã thông tin liên lạc bằng hệ thống mật mã dựa trên mã.
Là một phương pháp mã hóa và giải mã dữ liệu, mã hóa dựa trên lập trình động dựa trên thuật toán lập trình động. Để giải quyết các thách thức tối ưu hóa, các kỹ thuật lập trình động thường phân chia vấn đề thành một tập hợp các bài toán con đơn giản hơn. Mật mã lập trình động sử dụng ba lô, đường đi ngắn nhất và khắc đường may.
Một ví dụ trong thế giới thực của lập trình động là gì?
Nhiều trường hợp ứng dụng phần mềm trong thế giới thực sử dụng lập trình động để duy trì sự linh hoạt và hiệu quả trong khi giảm dấu vết tài nguyên của chúng trên hệ thống máy chủ. Một số trường hợp như sau:
- Bản đồ Google. Google Maps sử dụng lập trình động để tìm tuyến đường nhanh nhất từ một điểm gốc nhất định đến một số điểm đến khác nhau.
- Kết nối mạng. Truyền dữ liệu tuần tự từ một người gửi đến nhiều người nhận.
- Người kiểm tra đánh vần. Thuật toán chỉnh sửa khoảng cách xác định số bước cần thiết để chuyển đổi một từ thành một từ khác và cung cấp thước đo định lượng về mức độ khác nhau giữa hai từ.
- Phần mềm đạo văn. Phương pháp khoảng cách tài liệu giúp xác định độ tương tự của tài liệu văn bản.
- Các công cụ tìm kiếm. Để xác định hai phần nội dung internet thực sự giống nhau như thế nào.
Làm thế nào để giải quyết các vấn đề lập trình động?
Học công thức để giải các bài toán quy hoạch động là bước tiếp theo sau khi hiểu khái niệm về quy hoạch động. Dưới đây là một số gợi ý về cách áp dụng quy hoạch động cho vấn đề hiện tại và đưa ra giải pháp khả thi:
#1. Thừa nhận vấn đề lập trình động
Phần quan trọng nhất là nhận ra rằng một thuật toán lập trình động có thể giải quyết vấn đề đã chỉ định. Giải quyết vấn đề này trước tiên cần xác định xem mỗi câu lệnh của vấn đề có thể được chia thành các phần nhỏ hơn dưới dạng một chức năng hay không.
#2. Xác định nguyên nhân của vấn đề
Nếu bạn đã kết luận rằng lập trình động là công cụ thích hợp cho công việc, thì bước tiếp theo là xác định cấu trúc đệ quy của vấn đề trong số các vấn đề con cấu thành của nó. Trong trường hợp này, bạn phải tính đến bản chất linh hoạt của các điều kiện của vấn đề. Biến này có thể là một vị trí mảng hoặc tốc độ giải quyết vấn đề.
Ngoài ra, việc đếm các bộ phận cấu thành của vấn đề là rất quan trọng.
#3. Chọn giữa phương pháp lặp và phương pháp đệ quy
Để khắc phục các sự cố lập trình động, bạn có thể sử dụng các phương pháp lặp hoặc đệ quy. Từ những gì đã nói cho đến nay, có thể nói rằng phương pháp đệ quy là thích hợp hơn. Tuy nhiên, tất cả những cân nhắc nói trên đều đứng độc lập, bất kể phương pháp được chọn để giải quyết vấn đề là gì.
Cả hai cách tiếp cận đệ quy và lặp lại đều cần bạn chỉ định mối quan hệ lặp lại và trường hợp cơ bản của vấn đề.
#4. Kết hợp một hệ thống ghi nhớ
Khi giải quyết một vấn đề có cấu trúc tương tự, có thể hữu ích khi nhớ lại kinh nghiệm xử lý các vấn đề con tương tự trong quá khứ. Do đó, độ phức tạp về thời gian của vấn đề sẽ giảm đi. Độ phức tạp về thời gian của một nhiệm vụ có thể tăng theo cấp số nhân nếu chúng ta tiếp tục giải đi giải lại các bài toán con giống nhau mà không sử dụng phương pháp ghi nhớ.
#5. Đặt mối quan hệ lặp lại thành từ
Khi giải quyết một vấn đề, nhiều lập trình viên bỏ qua việc xác định mối quan hệ truy hồi và chuyển thẳng sang viết mã. Bạn sẽ hiểu vấn đề tốt hơn và có thể viết mã nhanh hơn nếu bạn có thể diễn đạt quan hệ truy hồi một cách rõ ràng trước khi bắt đầu.
Thuật toán Lập trình động
Hầu hết các ứng dụng của quy hoạch động bao gồm thuật toán đệ quy. Việc sử dụng lập trình động để tối ưu hóa ngụ ý rằng đệ quy là bản chất của phần lớn các vấn đề tối ưu hóa.
Tuy nhiên, không thể giải các bài toán đệ quy toàn phần bằng quy hoạch động. Một phép đệ quy chỉ có thể tìm ra lời giải bằng chiến lược chia để trị trừ khi có sự hiện diện của các bài toán con trùng nhau, như trong bài toán dãy Fibonacci.
Điều này là do các bài toán con cơ bản trong thuật toán đệ quy như Hợp nhất Sắp xếp không trùng lặp, loại trừ việc sử dụng Lập trình động.
Các loại thuật toán lập trình động khác nhau
Dưới đây là các loại thuật toán lập trình động khác nhau.
#1. Dãy con chung dài nhất
Các phần tử của dãy con chung dài nhất (LCS) có thể xuất hiện theo bất kỳ thứ tự nào trong các dãy ban đầu; LCS được định nghĩa là chuỗi con dài nhất chung cho tất cả các chuỗi đã chỉ định.
Nếu có hai dãy S1 và S2 thì dãy Z là dãy con của cả S1 và S2 được gọi là dãy con chung của chúng. Là một yêu cầu bổ sung, Z phải bao gồm một chuỗi tăng dần nghiêm ngặt của các chỉ số của bộ S1 và S2.
Chỉ số của các phần tử được chọn trong Z phải tăng nghiêm ngặt để tạo thành một chuỗi tăng.
#2. Thuật toán Floyd-Warshall
Tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong đồ thị có trọng số là mục tiêu của Thuật toán Floyd-Warshall. Phương pháp này xử lý các biểu đồ có trọng số theo cả hai hướng. Mặt khác, nó không thành công đối với các chu kỳ trong đó tổng các cạnh của chúng là âm.
Thuật toán Floyd, thuật toán Roy-Floyd, thuật toán Roy-Warhshall và thuật toán WFI đều là tên của thuật toán Floyd-Warhshall.
Thuật toán này sử dụng kỹ thuật lập trình động để xác định vị trí các phím tắt tối ưu.
Làm thế nào để một thuật toán lập trình động giải quyết các vấn đề Lcs nhanh hơn một kỹ thuật đệ quy?
Lập trình động giúp giảm chi phí gọi hàm. Nó ghi nhớ kết quả của mỗi lần gọi hàm để các lần gọi tiếp theo có thể sử dụng dữ liệu được lưu trữ mà không lặp lại cùng một công việc.
Mỗi khi một phần tử của X được so sánh với một phần tử của Y, các kết quả được ghi vào một bảng để chúng có thể được sử dụng trong các tính toán tiếp theo trong quy trình động đã nói ở trên.
Do đó, thời gian chạy của một phương thức động giống như thời gian cần thiết để điền vào bảng (O(mn)). Ngược lại, độ phức tạp của thuật toán đệ quy là 2max(m, n). Ngoài ra, đọc Cách chọn loại thuật toán mã hóa phù hợp với nhu cầu kinh doanh của bạn
Các vấn đề lập trình động trong Python là gì
Sử dụng lập trình động, người ta có thể xác định giải pháp thích hợp nhất cho bất kỳ số lượng báo cáo vấn đề khác nhau nào. Trong phần sau đây, chúng tôi sẽ xem xét một số câu lệnh vấn đề nổi tiếng được yêu cầu thường xuyên nhất và đưa ra lời giải thích ngắn gọn cùng với mã Python thích hợp.
#1. Ba lô (0-1) Giới hạn
Trong tình huống này, bạn được cung cấp giá và trọng lượng của N hàng hóa và được giao nhiệm vụ xếp chúng vào một chiếc ba lô có sức chứa W; mục tiêu là giảm thiểu số lượng vật phẩm được chọn trong khi vẫn nhét mọi thứ vào ba lô.
Hầu hết các cuộc phỏng vấn kỹ thuật cho các tổ chức hàng hóa sẽ yêu cầu ứng viên giải quyết vấn đề về chiếc ba lô, đây là một ví dụ cổ điển về kỹ thuật lập trình động.
Tuyên bố của vấn đề Giả sử rằng bạn có một chiếc túi có sức chứa W và một danh sách các thứ, mỗi thứ có trọng lượng và lợi nhuận tương ứng. Mục tiêu là để tối đa hóa thu nhập bằng cách lấp đầy hiệu quả xấu.
Câu trả lời là tạo một bảng có các cột cho mỗi trọng số có thể hiểu được từ 1 đến W và các hàng cho các trọng số mà bạn thực sự chọn. Bảng này sẽ được gọi là dp[][]. Nếu 'j' là sức chứa của chiếc ba lô và các phần tử 'i' đầu tiên trong mảng trọng lượng/mặt hàng được bao gồm, thì trạng thái /ô dp[i][j] trong bảng cho biết lợi nhuận cao nhất có thể.
Do đó, giá trị trong ô cuối cùng sẽ biểu thị giải pháp. Điều quan trọng là chỉ đóng gói những gì không vượt quá giới hạn trọng lượng của ba lô. Có hai lựa chọn thay thế cho tiêu chí “trọng lượng>wt[i-1]”, trong đó tất cả các cột đều có thể được điền.
#2. 0/1 Knapsack Bounded Ghi nhớ
Đổ đầy một túi các mặt hàng có trọng lượng và lợi nhuận đã biết, cỡ K. Mục tiêu của bạn là tối đa hóa thu nhập của mình. Ở đây, chúng ta sẽ sử dụng phương pháp ghi nhớ thay vì lập bảng để xem liệu chúng ta có thể giải quyết vấn đề hay không.
Vấn đề về chiếc ba lô 0/1 ở trên sử dụng chiến lược từ dưới lên để tìm ra giải pháp, trong khi vấn đề này sử dụng cách tiếp cận từ trên xuống dựa trên sự ghi nhớ để tìm ra giải pháp.
Lập trình động sử dụng ghi nhớ để giảm nhu cầu giải quyết nhiều lần cùng một phần của vấn đề. Điều này giúp loại bỏ sự cần thiết phải liên tục giải quyết vấn đề phụ và hợp lý hóa quá trình tạo đầu ra.
Tuyên bố của vấn đề Giả sử rằng bạn có một chiếc túi có sức chứa W và một danh sách các thứ, mỗi thứ có trọng lượng và lợi nhuận tương ứng. Nếu túi đầy với hiệu quả càng nhiều càng tốt, người ta có thể nhận được mức lợi nhuận tiềm năng cao nhất.
Giải pháp đầu tiên là xây dựng một mảng hai chiều để chứa các câu trả lời cuối cùng cho các bài toán con riêng lẻ. Các cột của bảng sẽ liệt kê tất cả các trọng số tiềm năng từ 1 đến W, phân chia nó thành nhiều phần và các hàng sẽ hiển thị các trọng số bạn chọn tại mỗi thời điểm nhất định.
Chúng tôi sử dụng một mảng dp để theo dõi từng bài toán con đã giải quyết. Thay vì giải quyết một vấn đề con đã được giải quyết trước đó, chúng tôi chỉ trả lời câu trả lời của nó.
#3. Bài toán tập hợp con bằng nhau
Tìm một phân vùng của tập hợp đã cho sao cho tổng số phần tử trong cả hai tập hợp con bằng nhau bằng cách sử dụng quy hoạch động để giải quyết vấn đề tập hợp con bằng nhau. Ngoài các tên gọi khác, bài toán tập con bằng nhau (hay bài toán phân vùng) là một minh họa điển hình về sức mạnh của quy hoạch động.
Nhiệm vụ hiện tại yêu cầu chúng ta chia mảng arr thành hai nửa để mỗi tập hợp con tiếp theo có cùng kích thước tổng thể.
Như một giải pháp, chúng ta cần xây dựng một mảng hai chiều với các kích thước là (tổng/2+1)*(mục tiêu+1). Tại đây, kết quả của việc chia tách mảng ban đầu có thể được lưu trữ cho từng tập hợp con và từng tổng và sau đó được truy xuất. Chiều thứ nhất của mảng sẽ biểu thị các tập hợp con khác nhau có thể được tạo, trong khi chiều thứ hai của mảng sẽ biểu thị các tổng khác nhau có thể được tính bằng cách kết hợp các tập hợp con.
Ưu điểm của lập trình động
Dưới đây là một số ưu điểm của lập trình động.
#1. Biện pháp khắc phục hiệu quả
Quy hoạch động là một công cụ mạnh mẽ để tìm giải pháp tối ưu cho các vấn đề với cấu trúc con tối ưu và các vấn đề con chồng chéo. Bằng cách phân tách chúng thành các phần có thể quản lý được, những thách thức này sẽ dễ dàng giải quyết hơn bằng phương pháp này. Lập trình động có thể tạo ra một giải pháp tối ưu bằng cách tránh các tính toán lặp đi lặp lại và sử dụng lại các câu trả lời cho các vấn đề phụ.
#2. Tạo điều kiện dễ dàng tìm kiếm vấn đề
Giải quyết một vấn đề khó khăn có thể dễ dàng hơn bằng cách phân tách nó thành các phần đơn giản hơn. Nó làm cho các vấn đề phức tạp trở nên dễ giải quyết hơn bằng cách phân chia chúng thành các phần dễ quản lý hơn. Phương pháp này đơn giản hóa giải pháp và làm cho vấn đề dễ tiếp cận hơn.
# 3. Có hiệu quả
Bằng cách loại bỏ các tính toán không cần thiết và tái chế các bài toán con đã giải quyết trước đó, Lập trình động có thể cắt giảm đáng kể thời gian cần thiết để giải một bài toán. Khi các vấn đề phụ trùng lặp, phương pháp này có thể trợ giúp bằng cách giảm tổng số biện pháp cần thiết để giải quyết vấn đề.
#4. Hiệu quả khi một vấn đề có nhiều giải pháp
Lập trình động có thể giúp xác định cách giải thích nào có nhiều khả năng xảy ra hơn. Khi có một số tùy chọn khả thi để khắc phục sự cố, phương pháp này có thể giúp chúng tôi tập trung vào giải pháp tốt nhất.
Hạn chế của lập trình động là gì?
Dưới đây là một số nhược điểm của lập trình động.
#1. Các vấn đề phụ liên tục lặp lại
Lập trình động hoạt động tốt nhất khi vấn đề có các vấn đề phụ chồng chéo, điều này có thể không phải lúc nào cũng đúng. Nó sẽ không hoạt động và có thể sẽ không cung cấp cho bạn giải pháp tốt nhất nếu các vấn đề riêng lẻ không giao nhau.
#2. Sự phức tạp trong thời gian và không gian
Nếu vấn đề lớn, Lập trình động có thể yêu cầu nhiều bộ nhớ và dung lượng lưu trữ, điều này làm tăng độ phức tạp về thời gian và không gian của giải pháp. Sử dụng bộ nhớ, cách tiếp cận này lưu trữ các kết quả tạm thời trong một bảng hoặc một bảng ghi nhớ.
#3. Khung cho vấn đề
Mặc dù hiệu quả đối với một số cấu trúc bài toán nhất định, Lập trình động không phải lúc nào cũng là lựa chọn tốt nhất. Phương pháp này hoạt động tốt nhất khi bài toán có các bài toán con chồng lên nhau, do đó nó có thể không áp dụng được cho các tình huống khác.
#4. Khó đưa vào thực tế
Lập trình động cần có kiến thức chuyên sâu về thuật toán và cấu trúc dữ liệu, khiến việc triển khai trở nên khó khăn đối với người mới bắt đầu. Phương pháp này đòi hỏi phải suy nghĩ trước và làm quen sâu sắc với vấn đề hiện tại.
bottom Line
Tóm lại, Lập trình động là một phương pháp hiệu quả để tìm câu trả lời, mặc dù các phương pháp khác được ưa chuộng hơn. Điều quan trọng là phải biết những ưu và nhược điểm và chọn phương pháp phù hợp tùy theo vấn đề hiện tại. Đối với các bài toán có cấu trúc con tối ưu và các bài toán con chồng lấp, Quy hoạch động có thể đưa ra lời giải tối ưu; tuy nhiên, phương pháp này có thể không phải lúc nào cũng được áp dụng.
Mặc dù khó phát triển và sử dụng nhiều bộ nhớ, nhưng khả năng hợp lý hóa quá trình giải quyết vấn đề và rút ngắn thời gian tính toán khiến nó trở thành một nguồn tài nguyên quan trọng cho các nhà khoa học máy tính và nhà toán học.
Câu hỏi thường gặp về lập trình động
Sự khác biệt giữa Lập trình tuyến tính và Lập trình động là gì?
Đối với các bài toán tối ưu tuyến tính, chúng ta có thuật toán quy hoạch tuyến tính (LP) và đối với các bài toán tối ưu phi tuyến chung với các ràng buộc không lồi, chúng ta có quy hoạch động (DP), đảm bảo tính tối ưu toàn cục của một giải pháp.
Học lập trình động khó đến mức nào?
Mọi người đều biết rằng lập trình động là một chủ đề phức tạp, đặc biệt đối với những người mới tham gia lĩnh vực khoa học máy tính. Tuy nhiên, người ta có thể học lập trình động một cách dễ dàng nếu nắm vững các nguyên tắc cơ bản và thực hành phong phú.
Lập trình động có khó không?
Chúng thật khó! Để bắt đầu, ý tưởng về các phương pháp lập trình động có thể khó nắm bắt. Bất kỳ lập trình viên chuyên nghiệp nào cũng sẽ chứng thực rằng việc thành thạo DP đòi hỏi một cam kết về thời gian đáng kể. Kỹ năng phân tách một vấn đề thành các bộ phận cấu thành của nó và tập hợp lại thành một tổng thể khả thi cũng rất cần thiết.
Bài viết tương tự
- QUẢN LÝ THỜI GIAN DỰ ÁN: Quy trình, Công cụ & Phần mềm để Quản lý Hiệu quả
- AMAZON SEO: Cách tối ưu hóa sản phẩm của bạn để xếp hạng tốt hơn
- NGÔN NGỮ LẬP TRÌNH PHỔ BIẾN NHẤT: Hướng dẫn năm 2023
- LẬP TRÌNH MÁY TÍNH LÀ GÌ: Ví dụ, Loại, Khóa học & Phần mềm
- Di chúc trực tuyến: Người lập di chúc trực tuyến tốt nhất.
Tài liệu tham khảo
