Tại sao mergesort không phải là động lập trình

Question

Tôi đã đọc những lời này:

Có hai thuộc tính quan trọng mà một vấn đề phải có để cho quy hoạch động để được áp dụng: Hạ tầng cơ sở tối ưu và bài toán chồng chéo. Nếu một vấn đề có thể được giải quyết bằng cách kết hợp các giải pháp tối ưu cho các vấn đề con không chồng chéo, chiến lược được gọi là "phân chia và chinh phục". Đây là lý do tại sao mergesort và quicksort không được phân loại là các vấn đề lập trình động.

Tôi có 3 câu hỏi sau:?

1. Tại sao mergesort và quicksort không phải là lập trình động Tôi nghĩ rằng mergesort cũng có thể được chia nhỏ vấn đề và các vấn đề nhỏ sau đó làm điều tương tự và như vậy.
2. Thuật toán Dijkstra có sử dụng thuật toán động không?
3. Có các ví dụ áp dụng nào về việc sử dụng Lập trình động không?

Answer 1

1. Từ khóa ở đây là "các khái niệm phụ chồng chéo" và "cấu trúc con tối ưu". Khi bạn thực hiện quicksort hoặc mergesort, bạn đệ quy phá vỡ mảng của bạn thành các phần nhỏ hơn mà không chồng chéo lên nhau. Bạn không bao giờ hoạt động trên cùng một phần tử của mảng ban đầu hai lần trong bất kỳ mức độ đệ quy nào của đệ quy. Điều này có nghĩa là không có cơ hội để tái sử dụng các phép tính trước đó. Mặt khác, nhiều vấn đề DO liên quan đến việc thực hiện các phép tính tương tự trên các tập con chồng chéo, và có đặc tính hữu ích là giải pháp tối ưu cho một bài toán con có thể được sử dụng lại khi tính toán giải pháp tối ưu cho một vấn đề lớn hơn.

2. Thuật toán Dijkstra là một ví dụ điển hình về lập trình động, vì nó sử dụng lại các tính toán trước để khám phá đường đi ngắn nhất giữa hai nút A và Z. Giả sử hàng xóm ngay lập tức của A là B và C. Chúng tôi có thể tìm đường đi ngắn nhất từ A đến Z bằng cách cộng tổng khoảng cách giữa A và B với đường đi ngắn nhất được tính toán của chúng tôi từ B đến Z; và làm tương tự để tìm đường đi ngắn nhất từ ​​C đến Z. Sau đó, đường đi ngắn nhất từ ​​A đến Z sẽ là ngắn hơn của hai đường dẫn này. Thông tin chi tiết quan trọng ở đây là chúng ta có thể tái sử dụng các phép tính đường dẫn ngắn nhất cho các đường dẫn có độ dài 2 khi tính toán các đường đi ngắn nhất có độ dài 3, v.v. Làm như vậy dẫn đến một thuật toán hiệu quả hơn nhiều.

3. Lập trình động có thể được sử dụng để giải quyết nhiều loại sự cố - xem http://en.wikipedia.org/wiki/Dynamic_programming#Examples:_Computer_algorithms để biết một số ví dụ.

Answer 2

1. Đối với quy hoạch động để áp dụng đối với một vấn đề, cần có

   i. Cấu trúc tối ưu trong các biểu mẫu con:

Điều này có nghĩa là khi bạn chia nhỏ vấn đề thành các đơn vị nhỏ hơn, các đơn vị nhỏ hơn cũng cần được chia thành các đơn vị nhỏ hơn để có giải pháp tối ưu. Ví dụ, trong sắp xếp hợp nhất, một mảng các số có thể được sắp xếp nếu chúng ta chia nó thành hai mảng con, làm cho chúng được sắp xếp và kết hợp chúng. Trong khi phân loại hai subarrays này, lặp lại cùng một quá trình bạn đã làm theo trong câu trước. Vì vậy, một giải pháp tối ưu (một mảng được sắp xếp) là có khi chúng tôi tìm thấy một giải pháp tối ưu cho các vấn đề con của nó (chúng tôi sắp xếp các subarrays và kết hợp chúng). Yêu cầu này được đáp ứng cho sắp xếp hợp nhất. Ngoài ra, các bài toán con phải độc lập để chúng tuân theo một cấu trúc tối ưu.Điều này cũng được thực hiện bằng cách sắp xếp hợp nhất vì các giải pháp của các giải pháp con không bị ảnh hưởng bởi các giải pháp của nhau. Ví dụ, các giải pháp cho hai phần của một mảng không bị ảnh hưởng bởi sự sắp xếp của nhau.

ii. Overlapping subproblems:

Điều này có nghĩa là trong khi giải quyết giải pháp, các vấn đề con bạn xây dựng được lặp lại và do đó chỉ cần được giải quyết một lần. Trong trường hợp sắp xếp hợp nhất, yêu cầu này sẽ chỉ được đáp ứng hiếm khi trong trường hợp bình thường. Một loạt các số như 2 1 3 4 9 4 2 1 3 1 9 4 có thể là một ứng cử viên tốt cho các vấn đề con chồng chéo cho sắp xếp hợp nhất. Trong trường hợp này, giải pháp cho loại phân loại con (2 1 3) có thể được lưu trữ trong một bảng để được tái sử dụng, bởi vì nó sẽ được gọi hai lần trong quá trình tính toán. Nhưng như bạn có thể thấy, có một cơ hội rất mỏng mà một mảng ngẫu nhiên các số sẽ có loại này của một contrivance lặp đi lặp lại. Vì vậy, nó sẽ chỉ không hiệu quả nếu chúng ta sử dụng một kỹ thuật lập trình động như ghi nhớ cho một thuật toán như sắp xếp hợp nhất.

2. Không. Thuật toán của Dijkstra sử dụng chiến lược tham lam.

3. Có. Nếu tôi có thể trích dẫn Wikipedia ở đây, "Lập trình động được sử dụng rộng rãi trong tin sinh học cho các nhiệm vụ như sắp xếp chuỗi, gấp protein, dự đoán cấu trúc RNA và liên kết protein-DNA." ^[1]

[1] https://en.wikipedia.org/wiki/Dynamic_programming