Lập trình năng động, các nguyên tắc cơ bản

Để chọn giải pháp tối ưu khi thực hiện nhiệm vụ lập trình đôi khi cần thiết để sắp xếp một lượng lớn kết hợp dữ liệu tải bộ nhớ của máy tính cá nhân. Những phương pháp này bao gồm, ví dụ, phương pháp của chương trình "chia để trị". Trong trường hợp này các thuật toán cung cấp vấn đề tách thành subtasks nhỏ riêng biệt. Phương pháp này chỉ áp dụng trong những trường hợp subtasks nhỏ là độc lập lẫn nhau. Để tránh thực hiện công việc không cần thiết nếu phụ thuộc lẫn nhau tiểu nhiệm vụ, sử dụng phương pháp quy hoạch động đề xuất Mỹ R.Bellmanom trong những năm 50.

phương pháp này

lập trình năng động là để xác định các giải pháp tối ưu vấn đề n chiều, chia sẻ n giai đoạn riêng biệt của mình. Mỗi trong số họ là một nhiệm vụ phụ liên quan đến một biến với.

Ưu điểm chính của phương pháp này có thể được coi là các nhà phát triển tham gia vào các vấn đề tối ưu hóa một chiều subtasks thay vì một vấn đề n chiều, và mục tiêu chính của chúng tôi là sẽ "từ dưới lên".

Đó là khuyến khích để áp dụng lập trình năng động trong những trường hợp tiểu nhiệm vụ quan hệ với nhau, ví dụ: chia sẻ module chung. Các thuật toán cung cấp các quyết định của mỗi người trong số các nhiệm vụ nhỏ một lần, và phản ứng tiết kiệm được thực hiện trong một bảng đặc biệt. Điều này làm cho nó có thể không tính toán một câu trả lời khi họ gặp nhau một lần nữa với cùng nhiệm vụ phụ.

Nhiệm vụ quy hoạch động giải quyết vấn đề tối ưu hóa. Tác giả của phương pháp này được xây dựng bởi R. Bellman nguyên tắc tối ưu: bất cứ điều gì là tình trạng ban đầu của mỗi bậc thang và giải pháp quy định tại bước này, tất cả những điều sau đây để lựa chọn tối ưu liên quan đến tình trạng, mà nhận được hệ thống vào cuối năm bước.

Phương pháp cải thiện hiệu suất trong những nhiệm vụ giải quyết bằng các phương tiện của các biến thể, hoặc đệ quy.

thuật toán nhiệm vụ xây dựng

thuật toán lập trình động liên quan đến việc xây dựng các nhiệm vụ như vậy mà nhiệm vụ nên được chia thành hai hoặc nhiều nhiệm vụ nhỏ để giải pháp của nó bao gồm một giải pháp tối ưu cho tất cả các nhiệm vụ nhỏ, nó bao gồm. Hơn nữa, nó là cần thiết để viết một mối quan hệ tái phát, và tính toán các giá trị tham số tối ưu cho công việc như một toàn thể.

Đôi khi, trên bước thứ 3 là để ghi nhớ một số thông tin cơ bản bổ sung về tiến độ thực hiện từng nhiệm vụ. Đây được gọi là đột quỵ trở lại.

phương pháp ứng dụng

lập trình động được áp dụng khi có hai tính năng đặc trưng:

• tối ưu cho subtasks;
• hiện diện trong vấn đề chồng chéo bài toán.

Giải quyết vấn đề tối ưu hóa bằng cách lập trình năng động, trước tiên bạn cần phải mô tả cấu trúc của giải pháp. Nhiệm vụ phải được tối ưu nếu các giải pháp bao gồm những quyết định tốt nhất của subtasks của nó. Trong trường hợp này, đó là khuyến khích sử dụng lập trình năng động.

Thuộc tính thứ hai của vấn đề, quan trọng trong phương pháp này, - một số ít tiểu nhiệm vụ. giải pháp đệ quy của vấn đề sử dụng cùng một phụ trùng lặp vấn đề, số lượng phụ thuộc vào kích thước của các thông tin ban đầu. Câu trả lời được lưu trữ trong một bảng đặc biệt, chương trình tiết kiệm thời gian bằng cách sử dụng dữ liệu này.

Đặc biệt hiệu quả là sử dụng các chương trình năng động khi nhiệm vụ được cơ bản cần thiết để đưa ra quyết định trong giai đoạn. Ví dụ, hãy xem xét một ví dụ đơn giản của vấn đề thay thế và sửa chữa thiết bị. Hãy nói rằng trên máy nhà máy đúc để sản xuất lốp xe đồng thời làm cho lốp xe trong hai hình thức khác nhau. Trong trường hợp một trong các hình thức thất bại, nó là cần thiết để tháo rời máy. Có thể hiểu rằng đôi khi có lợi nhuận nhiều hơn để thay thế và một hình thức thứ hai để tháo rời máy trong trường hợp và hình thức này sẽ không khả thi trong giai đoạn tiếp theo. Đặc biệt kể từ khi nó dễ dàng hơn để thay thế cả hình làm việc trước khi họ bắt đầu thất bại. Phương pháp quy hoạch động xác định chiến lược tốt nhất trong vấn đề của việc thay thế các hình thức, có tính đến tất cả các yếu tố: lợi ích của hình thức tiếp tục khai thác, mất thời gian chết máy, chi phí của lốp xe bỏ đi và nhiều hơn nữa.