Các mô hình ra quyết định của Markov được khái quát hóa theo các hướng khác nhau, cụ thể cho từng trường hợp Vấn đề tái thiết Markov. Sự khái quát hóa hữu ích nhất thu được khi xem xét thời gian chuyển tiếp không bằng nhau hoặc thay đổi. Trong các mô hình đơn giản, người ta giả định rằng quá trình chuyển đổi từ trạng thái này sang trạng thái khác và việc quan sát trạng thái này là tức thời và khoảng thời gian giữa các lần chuyển đổi từ trạng thái này sang trạng thái khác có thể có độ dài thay đổi hoặc ngẫu nhiên.

Bất cứ khi nào một trạng thái được quan sát, một giải pháp sẽ được chọn và không thể thay đổi cho đến khi quá trình chuyển sang trạng thái mới, nơi giải pháp mới được chọn, v.v. Mô hình này là sự kết hợp giữa lý thuyết chuỗi Markov và lý thuyết phục hồi; thường được gọi là Vấn đề tái thiết Markov.

Câu hỏi kiểm tra Chương 6.

1. Mạng định hướng bao gồm những thành phần nào?

1. Ma trận dung lượng mạng được xây dựng như thế nào?

1. Ma trận luồng mạng được hình thành như thế nào?

1. Tại sao lại trừ ma trận công suất và lưu lượng?

1. Sơ đồ mạng là gì và dùng để làm gì?

1. Thời gian bắt đầu sớm và kết thúc sớm của công việc được xác định như thế nào?

1. Tổng số float cho một số sự kiện trên sơ đồ mạng là bao nhiêu?

1. Đường tới hạn được xác định như thế nào?

1. Vector trạng thái của một hệ thống nào đó được gọi là gì?

1. Quỹ đạo của hệ trong không gian trạng thái là gì?

1. Vấn đề điều khiển tối ưu là gì?

1. Tiêu chí tối ưu được xây dựng như thế nào?

1. Lập trình động là gì?

1. Xây dựng nguyên lý tối ưu Bellman.

1. Bản chất của thuật toán quét tiến và quét lùi khi tìm đường đi ngắn nhất là gì?

Các lựa chọn cho bài tập cho Chương 6.

Đối với các mạng trong mỗi tùy chọn:

1) Tìm luồng tối đa từ nguồn (1) đến nút cuối cùng của mạng - phần đích, giả sử rằng một trong các số trong ngoặc cho mỗi cung (i, j) xác định dung lượng của cung;

1) Giả sử rằng các cung (1)®(2), (1)®(3), v.v. xác định một số công việc, thời gian tối thiểu và tối đa của chúng được cho bởi các số được chỉ ra dưới các cung tương ứng, hãy tìm đường tới hạn từ sự kiện đầu tiên (1) đến khi kết thúc;

1) Tìm kiếm đường đi ngắn nhất từ ​​nút đầu đến nút cuối của mạng. Xét khoảng cách giữa các nút i, j được cho bởi một trong các số trong ngoặc.

Giả sử có một vấn đề mà chúng ta đã giải quyết bằng lập trình động, chẳng hạn như các số Fibonacci vĩnh cửu.
Chúng ta hãy định dạng lại nó một chút. Chúng ta hãy có một vectơ mà từ đó chúng ta muốn thu được một vectơ. Hãy mở rộng các công thức một chút: . Bạn có thể thấy rằng từ một vectơ bạn có thể nhận được một vectơ bằng cách nhân với một số ma trận, vì chỉ các biến được thêm vào từ vectơ đầu tiên mới xuất hiện trong vectơ cuối cùng. Ma trận này rất dễ suy ra, đây là: . Hãy gọi nó là ma trận chuyển tiếp.

Điều này có nghĩa là nếu chúng ta lấy vector và nhân nó với ma trận chuyển tiếp n - 1 lần, ta được một vectơ chứa fib[n] - đáp án của bài toán.

Bây giờ, tại sao tất cả những điều này lại cần thiết? Phép nhân ma trận có tính chất kết hợp, tức là (nhưng đồng thời nó không có tính giao hoán, điều này theo tôi là đáng ngạc nhiên). Thuộc tính này cho chúng ta quyền thực hiện điều này: .

Điều này tốt vì bây giờ bạn có thể sử dụng phương pháp lũy thừa nhanh, hoạt động trong . Tổng cộng, chúng tôi có thể tính số Fibonacci thứ N dưới dạng logarit của các phép tính số học.

Và bây giờ là một ví dụ nghiêm túc hơn:

Ví dụ #3: Trình tự đoạn đường nối

Giải pháp

Đầu tiên, một giải pháp không có ma trận chuyển tiếp:

1) Trạng thái động lực: dp[n] - số chuỗi răng cưa có độ dài n kết thúc bằng số cuối cùng. Hơn nữa, nếu nhỏ hơn == 0 thì chữ số cuối cùng nhỏ hơn chữ số áp chót, còn nếu nhỏ hơn == 1 thì nhiều hơn.
2) Giá trị ban đầu:
cho lần cuối cùng trong phạm vi (10): dp = 9 - dp cuối cùng = 3 cuối cùng) Tính toán lại động lực học:
cho phần trước trong phạm vi (10): if trước > cuối: dp[n] += dp nếu trước< last: dp[n] += dp 4) Порядок пересчёта: мы всегда обращаемся к предыдущей длине, так что просто пара вложенных for "ов.
5) Câu trả lời là tổng dp[N] .

Bây giờ chúng ta cần đưa ra một vectơ ban đầu và ma trận chuyển tiếp sang nó. Vectơ dường như xuất hiện nhanh chóng: tất cả các trạng thái biểu thị độ dài của chuỗi N . Chà, ma trận chuyển đổi được suy ra bằng cách xem xét các công thức chuyển đổi.

Vectơ chuyển tiếp và ma trận

Động lực theo phân đoạn

Ví dụ #4: Đóng gói một chuỗi

Hãy xác định một chuỗi nén:
1) Một chuỗi chỉ gồm các chữ cái là một chuỗi nén. Cô ấy hòa mình vào chính mình.
2) Một chuỗi là sự nối của hai chuỗi nén A và B. Nó được giải nén thành một chuỗi gồm các chuỗi A và B đã giải nén.
3) Chuỗi D(X) , trong đó D là số nguyên lớn hơn 1 và X là chuỗi nén. Nó được giải nén thành một chuỗi D được giải nén từ X .
Ví dụ: “3(2(A)2(B))C” mở rộng thành “AABBAABBAABBC” .

Cần phải tìm ra từ chuỗi s độ dài của chuỗi nén ngắn nhất giải nén vào nó.

Giải pháp

Vấn đề này được giải quyết, như bạn có thể đã đoán, bằng động lực trong các phân đoạn.

1) Trạng thái động: d[l][r] - chuỗi nén có độ dài tối thiểu, được giải nén thành chuỗi s
2) Trạng thái ban đầu: tất cả các chuỗi con có độ dài bằng một chỉ có thể được nén vào chính chúng.
3) Tính toán lại động lực học:
Câu trả lời hay nhất có một số hoạt động cuối cùng nén: hoặc đó chỉ là một chuỗi từ chữ in hoa, hoặc đó là sự nối của hai chuỗi hoặc chính sự nén. Vì vậy, chúng ta hãy xem xét tất cả các tùy chọn và chọn cái tốt nhất.

Dp_len = r - l dp[l][r] = dp_len # Tùy chọn nén đầu tiên chỉ là một chuỗi. for i in range(l + 1, r): dp[l][r] = min(dp[l][r], dp[l][i] + dp[i][r]) # Thử chia cho hai chuỗi con được nén cho cnt trong range(2, dp_len): if (dp_len % cnt == 0): # Nếu nó không chia hết thì chẳng ích gì khi cố gắng chia good = True cho j trong range(1, ( dp_len / cnt) + 1 ): # Kiểm tra xem tất cả các chuỗi con cnt có tốt như nhau không &= s == s nếu tốt: # Cố gắng chia thành các chuỗi con giống hệt cnt và nén dp[l][r] = min(dp[l ][r], len (str(cnt)) + 1 + dp[l] + 1) 4) Thứ tự tính toán lại: độ dài chuỗi con tăng dần trực tiếp hoặc động học lười.
5) Câu trả lời nằm ở d.

Ví dụ #5:

Động lực theo cây con

Ví dụ #6: Cây logic

Cần phải tìm số lượng thay đổi tối thiểu trong các phép toán logic ở các đỉnh bên trong sao cho giá trị tại gốc thay đổi hoặc báo cáo rằng điều này là không thể.

Giải pháp

1) Trạng thái động lực học: d[v][x] - số thao tác cần thiết để đạt được giá trị x tại đỉnh v. Nếu điều này là không thể thì giá trị trạng thái là +inf.
2) Giá trị ban đầu: đối với các lá, rõ ràng là giá trị của bạn có thể nhận được khi không thay đổi, nhưng không thể thay đổi giá trị, nghĩa là có thể, nhưng chỉ có thể trong các phép toán +inf.
3) Công thức quy đổi:
Nếu đỉnh này đã có giá trị x thì bằng 0. Nếu không thì có hai lựa chọn: thay đổi thao tác ở đỉnh hiện tại hoặc không. Đối với cả hai bạn cần tìm lựa chọn tốt nhất và chọn cái tốt nhất.

Nếu thao tác là “VÀ” và bạn cần nhận được “0”, thì câu trả lời là giá trị nhỏ nhất của d[i] , trong đó i là con của v .
Nếu phép toán là “AND” và bạn muốn nhận “1”, thì câu trả lời là tổng của tất cả các giá trị d[i] , trong đó i là con của v .
Nếu phép toán là “HOẶC” và bạn muốn nhận “0”, thì câu trả lời là tổng của tất cả các giá trị d[i] , trong đó i là con của v .
Nếu thao tác là “HOẶC” và bạn cần nhận “1”, thì câu trả lời là giá trị nhỏ nhất của d[i] , trong đó i là con của v .

4) Thứ tự tính toán lại: cách dễ nhất để thực hiện nó là một cách lười biếng - dưới dạng tìm kiếm theo chiều sâu từ gốc.
5) Đáp án là d xor 1].

Động lực theo tập hợp con

Ví dụ #7: Chu trình Hamilton của trọng lượng tối thiểu hoặc bài toán người bán hàng du lịch

Giải pháp

Vì chúng ta đang tìm một chu trình đi qua tất cả các đỉnh nên chúng ta có thể chọn bất kỳ đỉnh nào làm đỉnh “ban đầu”. Gọi đây là đỉnh số 0.

1) Trạng thái động học: dp[v] - đường có trọng số tối thiểu từ đỉnh 0 đến đỉnh v, đi qua tất cả các đỉnh nằm trong mặt nạ và chỉ đi qua chúng.
2) Giá trị ban đầu: dp = 0, tất cả các trạng thái khác ban đầu là +inf.
3) Công thức chuyển đổi: Nếu bit thứ i trong mặt nạ là 1 và có cạnh từ i đến v thì:
dp[v] = min(dp[v], dp[i] + w[i][v]) Trong đó w[i][v] là trọng số của cạnh từ i đến v .
4) Quy trình tính toán lại: đơn giản nhất và Một cách thuận tiện- đây là để viết động lực học lười biếng, nhưng bạn có thể sáng tạo và viết một bảng liệt kê các mặt nạ để tăng số lượng bit đơn vị trong đó.
5) Đáp án nằm ở d[(1<< N) - 1] .

Động lực theo hồ sơ

Những vấn đề này có thể được giải quyết bằng cách tìm kiếm toàn diện trong , trong đó a là số tùy chọn xếp kề cho một ô. Động lực học theo cấu hình tối ưu hóa thời gian dọc theo một trong các chiều thành tuyến tính, chỉ để lại hệ số theo cấp số nhân. Bạn sẽ nhận được một cái gì đó như thế này: .

Một tiết diện có k (thường là một) cột, là ranh giới giữa phần đã được lát và phần chưa được lát. Đường viền này chỉ được lấp đầy một phần. Rất thường xuyên nó là một phần của trạng thái động.

Hầu như luôn luôn trạng thái là một hồ sơ và hồ sơ đó ở đâu. Và quá trình chuyển đổi làm tăng vị trí này lên một. Bạn có thể tìm hiểu xem có thể chuyển từ cấu hình này sang cấu hình khác theo thời gian tuyến tính với kích thước cấu hình hay không. Điều này có thể được kiểm tra mỗi lần trong quá trình tính toán lại, nhưng nó cũng có thể được tính toán trước. Chúng tôi sẽ tính toán trước một mảng hai chiều - liệu có thể di chuyển từ mặt nạ này sang mặt nạ khác bằng cách đặt một số hình, tăng vị trí của cấu hình lên một. Nếu tính toán trước sẽ mất ít thời gian hơn để hoàn thành và nhiều bộ nhớ hơn.

Ví dụ #8: Xếp gạch Domino

Giải pháp

Ở đây hồ sơ là một cột. Thật thuận tiện khi lưu trữ nó dưới dạng mặt nạ nhị phân: 0 - một ô chưa có cột của cột, 1 - một ô xếp kề nhau. Đó là, tổng số hồ sơ.

0) Tính toán trước (tùy chọn): xem qua tất cả các cặp hồ sơ và kiểm tra xem có thể đi từ hồ sơ này sang hồ sơ khác hay không. Trong vấn đề này, điều này được kiểm tra như thế này:

Nếu trong cấu hình đầu tiên có số 1 ở vị trí tiếp theo, thì ở cấu hình thứ hai phải có số 0, vì chúng ta sẽ không thể bao phủ ô này bằng bất kỳ con số nào.

Nếu trong hồ sơ đầu tiên có số 0 ở vị trí tiếp theo, thì có hai tùy chọn - ở hồ sơ thứ hai là 0 hoặc 1.
Nếu là 0, điều này có nghĩa là chúng ta phải đặt một quân domino dọc, nghĩa là ô tiếp theo có thể được coi là 1. Nếu là 1 thì chúng ta đặt quân domino dọc và chuyển sang ô tiếp theo.

Ví dụ về chuyển đổi (từ cấu hình trên cùng, bạn có thể chuyển sang cấu hình dưới cùng và chỉ ở đó):

Sau đó, lưu mọi thứ vào một mảng có thể - 1 nếu bạn có thể đi, 0 nếu không thể.
1) Trạng thái động: dp - số ô xếp hoàn chỉnh của vị trí đầu tiên - 1 cột có cấu hình mặt nạ.
2) Trạng thái ban đầu: dp = 1 - viền trái của trường - tường thẳng.
3) Công thức quy đổi:
dp += dp * có thể
4) Thứ tự duyệt theo thứ tự tăng dần của vị trí.
5) Câu trả lời nằm ở dp.

Kết quả tiệm cận là .

Động lực dọc theo một hồ sơ bị hỏng

Bây giờ, sau khi thêm dấu ngắt vào cấu hình, bạn có thể chuyển sang trạng thái tiếp theo, chỉ thêm một hình bao phủ ô bên trái của dấu ngắt. Nghĩa là, bằng cách tăng số lượng trạng thái lên N lần (chúng ta phải nhớ điểm dừng ở đâu), chúng ta đã giảm số lần chuyển đổi từ trạng thái này sang trạng thái khác từ xuống còn . tiệm cận được cải thiện từ đến .

Sự chuyển đổi động lực dọc theo một mặt cắt bị hỏng bằng cách sử dụng ví dụ về bài toán xếp gạch bằng quân domino (ví dụ số 8):

Trả lời khôi phục

Mỗi bài toán đều có cách tìm đáp án riêng nhưng phổ biến nhất là:

• Lưu trữ câu trả lời đầy đủ cho nhiệm vụ con bên cạnh giá trị trạng thái động. Nếu câu trả lời là một cái gì đó lớn, nó có thể cần quá nhiều bộ nhớ, vì vậy nếu có thể sử dụng một phương pháp khác thì thường là nó được thực hiện.
• Xây dựng lại câu trả lời, biết (các) tổ tiên của trạng thái đã cho. Thông thường có thể xây dựng lại phản hồi bằng cách chỉ biết nó được nhận như thế nào. Trong cùng một “Đóng gói chuỗi”, để khôi phục phản hồi, bạn chỉ có thể lưu trữ loại hành động cuối cùng và trạng thái mà hành động đó được nhận.
• Có một cách hoàn toàn không sử dụng bộ nhớ bổ sung - sau khi tính toán lại động lực, hãy đi từ cuối dọc theo con đường tốt nhất và soạn câu trả lời trong suốt quá trình đó.

Tối ưu hóa nhỏ

Ký ức

Thời gian

Thay thế trạng thái

Ví dụ #9: Mở rộng số

• 3 + 4
• 2 + 5
• 1 + 7
• 1 + 2 + 4

Trong số các vấn đề được giải quyết bằng lập trình toán học, người ta có thể phân biệt một loại vấn đề riêng biệt yêu cầu tối ưu hóa các quy trình nhiều bước (nhiều giai đoạn). Những vấn đề như vậy được phân biệt bằng khả năng chia giải pháp thành nhiều giai đoạn liên kết với nhau. Để giải quyết những vấn đề như vậy, lập trình động hay còn được gọi là lập trình nhiều giai đoạn được sử dụng. Các phương pháp của nó được tối ưu hóa để tìm ra giải pháp tối ưu cho các vấn đề nhiều bước có thể được chia thành nhiều giai đoạn, bước, v.v.

Nguồn gốc của thuật ngữ

Việc sử dụng từ “động” trong tên ban đầu ngụ ý rằng việc phân chia thành các nhiệm vụ phụ sẽ diễn ra chủ yếu theo thời gian. Khi sử dụng các phương pháp động để giải quyết các vấn đề sản xuất, kinh tế và các vấn đề khác có xuất hiện yếu tố thời gian, việc chia nó thành các giai đoạn riêng biệt không khó. Nhưng cũng có thể sử dụng các kỹ thuật lập trình động trong các nhiệm vụ mà các giai đoạn riêng lẻ không liên quan về mặt thời gian. Trong bài toán có nhiều bước, bạn luôn có thể chọn một tham số hoặc thuộc tính có thể được sử dụng để chia nó thành các bước riêng biệt.

Thuật toán (phương pháp) giải bài toán nhiều giai đoạn

Thuật toán hoặc phương pháp lập trình động dựa trên nguyên tắc tối ưu hóa tuần tự của một bài toán, khi lời giải của một bài toán tổng quát được chia thành nhiều lời giải cho các bài toán con riêng lẻ rồi kết hợp lại thành một lời giải duy nhất. Rất thường xuyên, các bài toán con riêng lẻ hóa ra giống nhau và một giải pháp chung giúp giảm đáng kể thời gian tính toán.

Một đặc điểm của phương pháp là tính tự chủ trong việc giải quyết vấn đề ở từng giai đoạn riêng lẻ, tức là, bất kể quy trình được tối ưu hóa và giải quyết ở giai đoạn trước như thế nào, chỉ các tham số quy trình đặc trưng cho nó tại thời điểm đó mới được sử dụng trong tính toán hiện tại. Ví dụ, một người lái xe đang di chuyển trên đường sẽ đưa ra quyết định về lối rẽ hiện tại bất kể trước đó anh ta đã lái xe bao lâu và như thế nào.

Phương pháp từ trên và phương pháp từ dưới

Mặc dù thực tế là khi tính toán ở một giai đoạn riêng biệt để giải quyết vấn đề, các tham số của quy trình tại thời điểm hiện tại được sử dụng, kết quả tối ưu hóa ở giai đoạn trước ảnh hưởng đến tính toán của các giai đoạn tiếp theo để đạt được kết quả tốt nhất nói chung. Lập trình động gọi nguyên tắc giải pháp này là phương pháp tối ưu, xác định rằng chiến lược tối ưu để giải quyết vấn đề, bất kể các quyết định và điều kiện ban đầu, phải được tuân theo các quyết định tiếp theo ở tất cả các giai đoạn để tạo ra chiến lược tối ưu so với trạng thái ban đầu. Như chúng ta có thể thấy, quá trình giải quyết vấn đề là sự tối ưu hóa liên tục kết quả ở từng giai đoạn riêng lẻ từ giai đoạn đầu đến giai đoạn cuối. Phương pháp này được gọi là phương pháp lập trình từ trên xuống. Hình vẽ sơ đồ thể hiện thuật toán giải từ trên xuống. Nhưng có một loại bài toán gồm nhiều bước trong đó hiệu ứng tối đa ở giai đoạn cuối đã được biết trước, chẳng hạn như chúng ta đã đi từ điểm A đến điểm B và bây giờ chúng ta muốn tìm hiểu xem liệu chúng ta có lái xe đúng ở mỗi giai đoạn trước hay không. giai đoạn hoặc liệu điều gì đó có thể được thực hiện một cách tối ưu hơn. Một chuỗi các giai đoạn đệ quy xuất hiện, tức là chúng ta đi, như vốn có, “từ hướng ngược lại”. Phương pháp giải này được gọi là “phương pháp lập trình từ dưới lên”.

Công dụng thực tế

Lập trình động có thể được sử dụng trong bất kỳ lĩnh vực hoạt động nào có các quy trình có thể được chia thành một số giai đoạn nhỏ giống hệt nhau theo một số tham số (thời gian, số lượng, nhiệt độ, v.v.). Phương pháp giải động được sử dụng rộng rãi nhất trong lý thuyết điều khiển và phát triển hệ thống máy tính.

Tìm đường đi tối ưu

Sử dụng tối ưu hóa động, có thể giải quyết một loạt các vấn đề tìm kiếm hoặc tối ưu hóa đường đi ngắn nhất và các vấn đề khác trong đó phương pháp liệt kê các phương án giải pháp có thể “cổ điển” dẫn đến tăng thời gian tính toán và đôi khi hoàn toàn không thể chấp nhận được. Bài toán quy hoạch động cổ điển là bài toán về chiếc ba lô: cho một số lượng vật thể nhất định có khối lượng và giá thành nhất định, cần chọn một tập hợp vật thể có giá và khối lượng tối đa không vượt quá thể tích của chiếc ba lô. Việc tìm kiếm cổ điển tất cả các tùy chọn để tìm kiếm giải pháp tối ưu sẽ mất nhiều thời gian, nhưng với sự trợ giúp của các phương pháp động, vấn đề sẽ được giải quyết trong khung thời gian có thể chấp nhận được. Bài toán tìm ra con đường ngắn nhất cho logistics vận tải là vấn đề cơ bản và các phương pháp giải pháp động là phù hợp nhất để giải quyết chúng. Ví dụ đơn giản nhất của nhiệm vụ như vậy là xây dựng tuyến đường ngắn nhất bằng thiết bị định vị GPS trên ô tô.

Sản xuất

Lập trình động được sử dụng rộng rãi trong việc giải quyết nhiều vấn đề sản xuất, chẳng hạn như quản lý hàng tồn kho để duy trì số lượng linh kiện cần thiết bất cứ lúc nào, lập kế hoạch cho quy trình sản xuất, định kỳ và đại tu thiết bị, khối lượng công việc thống nhất của nhân sự, phân phối hiệu quả nhất quỹ đầu tư, v.v. Để giải quyết các vấn đề sản xuất bằng phương pháp lập trình động, các gói phần mềm đặc biệt đã được phát triển để tích hợp vào các hệ thống quản lý doanh nghiệp phổ biến, chẳng hạn như SAP.

Lĩnh vực khoa học

Phương pháp quy hoạch động được sử dụng rộng rãi trong nhiều nghiên cứu khoa học khác nhau. Ví dụ, chúng được sử dụng thành công trong các thuật toán nhận dạng giọng nói và hình ảnh khi xử lý lượng lớn dữ liệu trong xã hội học và

Xin chào, Habrakhabr. Tôi hiện đang viết một cuốn sách giáo khoa về lập trình Olympic, một trong những đoạn trong đó dành cho lập trình động. Dưới đây là một đoạn trích từ đoạn này. Cố gắng giải thích chủ đề này một cách đơn giản nhất có thể, tôi cố gắng kèm theo những khoảnh khắc phức tạp bằng hình ảnh minh họa. Tôi quan tâm đến ý kiến ​​​​của bạn về mức độ rõ ràng của tài liệu này. Tôi cũng rất vui khi nhận được lời khuyên về những nhiệm vụ khác nên được đưa vào phần này.

Trong nhiều bài toán lập trình Olympic, việc giải bằng cách sử dụng đệ quy hoặc tìm kiếm toàn diện đòi hỏi phải thực hiện một số lượng rất lớn các phép toán. Việc cố gắng giải quyết những vấn đề như vậy, ví dụ, bằng cách tìm kiếm toàn diện, sẽ dẫn đến việc vượt quá thời gian thực hiện.

Tuy nhiên, trong số các bài toán tìm kiếm toàn diện và một số bài toán khác, chúng ta có thể phân biệt một lớp bài toán có một đặc tính tốt: có lời giải cho một số bài toán con (ví dụ, với số nhỏ hơn N), bạn có thể tìm ra giải pháp cho vấn đề ban đầu mà hầu như không cần tìm kiếm.

Những vấn đề như vậy được giải quyết bằng cách sử dụng phương pháp quy hoạch động và bằng chính lập trình động, chúng tôi muốn nói đến việc giảm vấn đề thành các nhiệm vụ con.

trình tự

Dãy số Fibonacci F Nđược cho bởi các công thức: F 1 = 1, F 2 = 1,
Fn = F N - 1 + F N- 2 lúc N> 1. Cần tìm F N theo số N.

Một giải pháp có vẻ hợp lý và hiệu quả là giải quyết bằng đệ quy:

Int F(int n) ( if (n< 2) return 1; else return F(n - 1) + F(n - 2); }
Sử dụng chức năng như vậy, chúng tôi sẽ giải quyết vấn đề “từ cuối” - chúng tôi sẽ giảm dần từng bước N cho đến khi chúng ta đạt được các giá trị đã biết.

Nhưng như bạn có thể thấy, dường như chương trình đơn giảnđã ở N= 40 hoạt động đáng chú ý trong một thời gian dài. Điều này là do thực tế là cùng một dữ liệu trung gian được tính toán nhiều lần - số lượng phép toán tăng với tốc độ tương tự như các số Fibonacci tăng - theo cấp số nhân.

Một cách thoát khỏi tình huống này là lưu đã được tìm thấy kết quả trung gian nhằm mục đích tái sử dụng:

Int F(int n) ( if (A[n] != -1) return A[n]; if (n< 2) return 1; else { A[n] = F(n - 1) + F(n - 2); return A[n]; } }
Giải pháp đưa ra là chính xác và hiệu quả. Nhưng đối với vấn đề này, một giải pháp đơn giản hơn cũng có thể áp dụng được:

F = 1; F = 1; với (i = 2; tôi< n; i++) F[i] = F + F;
Giải pháp này có thể được gọi là giải pháp “từ đầu” - trước tiên chúng tôi điền vào các giá trị đã biết, sau đó chúng tôi tìm giá trị chưa biết đầu tiên ( F 3), rồi đến cái tiếp theo, v.v., cho đến khi chúng ta đạt được cái mong muốn.

Đây chính xác là giải pháp cổ điển cho lập trình động: trước tiên chúng tôi giải quyết tất cả các bài toán con (chúng tôi đã tìm thấy tất cả F Tôi Vì Tôi < N), sau đó, khi biết lời giải của các bài toán con, chúng ta đã tìm ra câu trả lời ( F N = F N - 1 + F N - 2 , F N- 1 và F N- 2 đã được tìm thấy).

Lập trình động một chiều

Giả sử vấn đề ban đầu là tìm một số nhất định T với dữ liệu ban đầu N 1 , N 2 , ..., N k. Tức là chúng ta có thể nói về hàm T(N 1 , N 2 , ..., N k), giá trị của nó chính là câu trả lời chúng ta cần. Sau đó chúng ta sẽ coi các nhiệm vụ là nhiệm vụ phụ
T(Tôi 1 , Tôi 2 , ..., Tôi k) Tại Tôi 1 < N 1 , Tôi 2 < N 2 , ..., Tôi k < N k .

Bài toán quy hoạch động một chiều sau đây có nhiều biến thể khác nhau.

Tại N < 32 полный перебор потребует нескольких секунд, а при N= 64 về nguyên tắc, tìm kiếm toàn diện là không khả thi. Để giải bài toán bằng phương pháp quy hoạch động, ta rút gọn vấn đề ban đầuđến các nhiệm vụ phụ.

Tại N = 1, N= 2 câu trả lời là hiển nhiên. Giả sử rằng chúng ta đã tìm thấy K N - 1 , K N- 2 - số lượng các chuỗi có độ dài như vậy N- 1 và N - 2.

Hãy xem độ dài của chuỗi có thể là bao nhiêu N. Nếu ký tự cuối cùng của nó là 0 thì ký tự đầu tiên N- 1 — bất kỳ chuỗi độ dài chính xác nào
N- 1 (không quan trọng nó kết thúc bằng 0 hay một - 0 tiếp theo). Chỉ có những chuỗi như vậy K N- 1 . Nếu ký tự cuối cùng bằng 1 thì ký tự áp chót phải bằng 0 (nếu không sẽ có hai ký tự liên tiếp) và ký tự đầu tiên
N- 2 ký tự - bất kỳ chuỗi độ dài hợp lệ nào N- 2 thì số dãy như vậy bằng nhau K N - 2 .

Như vậy, K 1 = 2, K 2 = 3, K N = K N - 1 + K N- 2 lúc N> 2. Đó là nhiệm vụ này thực sự bắt nguồn từ việc tìm các số Fibonacci.

Lập trình động 2D

Dưới đây là một số công thức của các nhiệm vụ như vậy:

Nhiệm vụ 2. N*tôi tế bào. Bạn có thể thực hiện các bước một ô ở bên phải hoặc xuống dưới. Đếm xem bạn có thể đi từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Nhiệm vụ 3. Cho một trường hình chữ nhật có kích thước N*tôi tế bào. Bạn có thể thực hiện các bước một ô sang phải, xuống hoặc theo đường chéo sang phải và xuống. Mỗi ô chứa một số số tự nhiên. Bạn cần đi từ ô trên cùng bên trái đến ô dưới cùng bên phải. Trọng số của tuyến đường được tính bằng tổng các số từ tất cả các ô đã truy cập. Cần phải tìm một tuyến đường có trọng lượng tối thiểu.

Một đặc điểm đặc trưng của tất cả các vấn đề như vậy là mỗi tuyến đường riêng lẻ không thể đi qua cùng một ô hai lần trở lên.

Hãy xem xét nhiệm vụ 2 chi tiết hơn Đối với một số ô có tọa độ ( Tôi,j) chỉ có thể đến từ phía trên hoặc từ bên trái, nghĩa là từ các ô có tọa độ ( Tôi - 1, j) Và ( Tôi, j - 1):

Vì vậy, đối với một ô ( Tôi, j) số lượng tuyến đường A[i][j] sẽ bằng
A[j] + A[i], nghĩa là bài toán được rút gọn thành hai nhiệm vụ con. Việc triển khai này sử dụng hai tham số - Tôi Và j- do đó, liên quan đến vấn đề này, chúng ta đang nói về quy hoạch động hai chiều.

Bây giờ chúng ta có thể tuần tự đi qua các hàng (hoặc cột) của mảng A, tìm số tuyến đường cho ô hiện tại bằng công thức trên. Trước tiên bạn phải đặt số 1 vào A.

Trong bài toán 3, trong một ô có tọa độ ( Tôi, j) chúng ta có thể lấy từ các ô có tọa độ
(Tôi- 1, j), ( Tôi, j- 1) và ( Tôi - 1, j- 1). Giả sử rằng đối với mỗi ô trong số ba ô này, chúng ta đã tìm ra lộ trình của trọng số tối thiểu và đặt các trọng số vào W[j], W[i],
W. Để tìm trọng lượng tối thiểu cho ( Tôi, j), bạn cần chọn trọng số tối thiểu W[j], W[i], W và thêm vào đó số được ghi trong ô hiện tại:

W[i][j] = min(W[j], W[i], W) + A[i][j];

Nhiệm vụ này phức tạp bởi thực tế là không chỉ cần tìm trọng lượng tối thiểu mà còn cả chính tuyến đường. Do đó, trong một mảng khác, chúng tôi sẽ ghi thêm cho từng ô mà chúng tôi cần nhập từ phía nào.

Hình dưới đây cho thấy một ví dụ về dữ liệu ban đầu và một trong các bước của thuật toán.

Chính xác một mũi tên dẫn đến từng ô đã được chuyển qua. Mũi tên này cho biết bạn cần đến ô này từ phía nào để có được trọng lượng tối thiểu được ghi trong ô.

Sau khi truyền toàn bộ mảng, bạn sẽ cần theo dõi lộ trình từ ô cuối cùng, theo các mũi tên theo hướng ngược lại.

Các vấn đề tiếp theo

Nhiệm vụ 4. Cho một dãy số nguyên. Cần phải tìm dãy con tăng nghiêm ngặt dài nhất của nó.

Hãy bắt đầu giải bài toán ngay từ đầu - chúng ta sẽ tìm kiếm câu trả lời, bắt đầu từ những số hạng đầu tiên của dãy này. Đối với mỗi số Tôi chúng ta sẽ tìm dãy con tăng lớn nhất kết thúc bằng một phần tử ở vị trí Tôi. Hãy để chuỗi ban đầu được lưu trữ trong mảng A. Trong mảng L, chúng ta sẽ ghi lại độ dài của các chuỗi con tối đa kết thúc bằng phần tử hiện tại. Chúng ta hãy tìm tất cả L[i] cho 1<= Tôi <= k- 1. Bây giờ bạn có thể tìm L[k] như sau. Chúng tôi xem xét tất cả các phần tử của A[i] cho 1<= Tôi < k- 1. Nếu
Một [tôi]< A[k], то k Phần tử th có thể trở thành phần tiếp theo của dãy con kết thúc bằng phần tử A[i]. Độ dài của dãy con thu được sẽ lớn hơn L[i] 1 đơn vị. Để tìm L[k], bạn cần phải trải qua tất cả Tôi từ 1 đến k - 1:
L[k] = max(L[i]) + 1, trong đó mức tối đa được lấy trên tất cả Tôi sao cho A[i]< A[k] и
1 <= Tôi < k.

Ở đây, mức tối đa của tập trống sẽ được coi là bằng 0. Trong trường hợp này, phần tử hiện tại sẽ trở thành phần tử duy nhất trong chuỗi đã chọn và sẽ không phải là phần tiếp theo của một trong những phần trước đó. Sau khi điền mảng L, độ dài của dãy con tăng lớn nhất sẽ bằng phần tử lớn nhất của L.

Để khôi phục lại dãy con, bạn cũng có thể lưu trữ số phần tử đã chọn trước đó cho mỗi phần tử, ví dụ: trong mảng N.

Chúng ta hãy xem xét giải pháp cho vấn đề này bằng cách sử dụng ví dụ về dãy 2, 8, 5, 9, 12, 6. Vì không có phần tử nào trước 2 nên dãy con tối đa chỉ chứa một phần tử - L = 1 và không có phần tử nào trước đó nó - N = 0. Hơn nữa,
2 < 8, поэтому 8 может стать продолжением последовательности с предыдущим элементом. Тогда L = 2, N = 1.

Phần tử duy nhất nhỏ hơn A = 5 là A = 2, vì vậy 5 có thể trở thành phần tiếp theo của duy nhất một dãy con - dãy chứa 2. Khi đó
L = L + 1 = 2, N = 1, vì 2 ở vị trí số 1. Tương tự, chúng ta thực hiện thêm ba bước của thuật toán và nhận được kết quả cuối cùng.

Bây giờ chúng ta chọn phần tử lớn nhất trong mảng L và từ mảng N chúng ta xây dựng lại dãy con 2, 5, 9, 12.

Một bài toán lập trình động cổ điển khác là bài toán palindrome.

Nhiệm vụ 5. Cho một chuỗi các chữ cái viết hoa của bảng chữ cái Latinh. Bạn cần tìm độ dài của bảng màu lớn nhất có thể đạt được bằng cách gạch bỏ một số chữ cái trong một chuỗi cho trước.

Chúng ta hãy biểu thị chuỗi này bằng S và ký hiệu của nó là S[i], 1<= Tôi <= N. Chúng ta sẽ xem xét các chuỗi con có thể có của chuỗi này với Tôi quần què j biểu tượng thứ, chúng tôi biểu thị chúng bằng S(Tôi, j). Chúng ta sẽ viết độ dài của palindrome tối đa cho các chuỗi con trong một mảng vuông L: L[i][j] là độ dài của palindrome tối đa có thể lấy được từ chuỗi con S(Tôi, j).

Hãy bắt đầu giải bài toán bằng các chuỗi con đơn giản nhất. Đối với một chuỗi ký tự đơn (nghĩa là một chuỗi con có dạng S(Tôi, Tôi)) câu trả lời là hiển nhiên - không cần phải gạch bỏ bất cứ thứ gì, chuỗi như vậy sẽ là một chuỗi palindrome. Đối với chuỗi hai ký tự S(Tôi, Tôi+ 1) Có hai lựa chọn: nếu các ký tự bằng nhau thì ta có bảng màu, không cần gạch bỏ gì cả. Nếu các ký tự không bằng nhau thì gạch bỏ bất kỳ ký tự nào.

Bây giờ chúng ta được cung cấp một chuỗi con S(Tôi, j). Nếu ký tự đầu tiên (S[i]) và cuối cùng (S[j]) của chuỗi con không khớp nhau thì một trong số chúng phải bị xóa. Sau đó chúng ta còn lại chuỗi con S(Tôi, j- 1) hoặc S(Tôi + 1, j) — nghĩa là chúng ta rút gọn bài toán thành một nhiệm vụ con: L[i][j] = max(L[i], L[j]). Nếu ký tự đầu và ký tự cuối bằng nhau thì chúng ta có thể bỏ cả hai nhưng cần biết cách giải quyết vấn đề S(Tôi + 1, j - 1):
L[i][j] = L + 2.

Hãy xem giải pháp sử dụng chuỗi ABACCBA làm ví dụ. Trước hết, chúng ta điền đơn vị vào đường chéo của mảng, chúng sẽ tương ứng với các chuỗi con S(Tôi, Tôi) từ một ký tự. Sau đó chúng ta bắt đầu xem xét các chuỗi con có độ dài bằng hai. Trong tất cả các chuỗi con ngoại trừ S(4, 5), các ký hiệu khác nhau nên ta viết 1 vào các ô tương ứng, và 2 vào L.

Hóa ra chúng ta sẽ điền mảng theo đường chéo, bắt đầu từ đường chéo chính dẫn từ góc trên bên trái đến góc dưới bên phải. Đối với chuỗi con có độ dài 3, thu được các giá trị sau: trong chuỗi con ABA, chữ cái đầu và chữ cái cuối bằng nhau, do đó
L = L + 2. Ở các chuỗi con còn lại, chữ cái đầu và chữ cái cuối khác nhau.

BAC: L = max(L, L) = 1.
ACC: L = max(L, L) = 2.
CCB: L = max(L, L) = 2.
CBA: L = max(L, L) = 1.

Nếu trong nhiệm vụ cần xuất ra không phải độ dài mà là chính bảng màu, thì ngoài mảng độ dài, chúng ta phải xây dựng một mảng chuyển tiếp - đối với mỗi ô, hãy nhớ trường hợp nào đã được triển khai (để rõ ràng, trong hình, thay vì chuyển tiếp mã hóa các giá trị số, các mũi tên tương ứng được vẽ).

Một ví dụ về giải bài toán bằng phương pháp quy hoạch động………………………..7

Danh sách các nguồn được sử dụng………………………..11

1. Lập trình năng động. Các khái niệm cơ bản.

Lập trình động (DP) trong lý thuyết hệ thống máy tính, một cách giải quyết các vấn đề phức tạp bằng cách chia chúng thành các nhiệm vụ đơn giản hơn. Nó có thể áp dụng cho các bài toán có cấu trúc con tối ưu, trông giống như một tập hợp các bài toán con chồng chéo có độ phức tạp nhỏ hơn một chút so với bài toán ban đầu. Trong trường hợp này, thời gian tính toán có thể giảm đáng kể so với các phương pháp “ngây thơ”.

Ý tưởng chính trong lập trình động khá đơn giản. Theo nguyên tắc, để giải một bài toán nhất định phải giải từng phần riêng lẻ của bài toán (nhiệm vụ con), sau đó kết hợp lời giải của các nhiệm vụ con thành một lời giải tổng quát. Thường thì nhiều nhiệm vụ phụ này giống nhau. Phương pháp quy hoạch động là giải mỗi bài toán con chỉ một lần, do đó giảm số lượng phép tính. Điều này đặc biệt hữu ích trong trường hợp số lượng nhiệm vụ con lặp lại lớn theo cấp số nhân.

Lập trình động là một kỹ thuật toán học tiếp cận giải pháp của một loại vấn đề nhất định bằng cách chia chúng thành các phần, các vấn đề nhỏ hơn và ít phức tạp hơn. Đồng thời, đặc điểm nổi bật là việc giải quyết các vấn đề theo từng giai đoạn, theo những khoảng thời gian, khoảng thời gian cố định đã quyết định sự xuất hiện của thuật ngữ quy hoạch động. Cần lưu ý rằng phương pháp quy hoạch động cũng được sử dụng thành công khi giải các bài toán không tính đến yếu tố thời gian. Nói chung, bộ máy toán học có thể được biểu diễn dưới dạng lập trình từng bước hoặc từng bước. Việc giải các bài toán bằng phương pháp quy hoạch động được thực hiện trên cơ sở nguyên lý tối ưu do R. E. Bellman xây dựng: hành vi tối ưu có tính chất là bất kể trạng thái ban đầu của hệ thống và lời giải ban đầu thì lời giải tiếp theo phải xác định hành vi tối ưu. so với trạng thái thu được khi thực hiện nghiệm ban đầu. Từ đó, việc lập kế hoạch cho từng bước phải được thực hiện có tính đến lợi ích tổng thể thu được khi hoàn thành toàn bộ quá trình, điều này cho phép tối ưu hóa kết quả cuối cùng theo tiêu chí đã chọn.

Như vậy, quy hoạch động theo nghĩa rộng là sự điều khiển tối ưu một quá trình bằng cách thay đổi các tham số được điều khiển ở mỗi bước và do đó ảnh hưởng đến tiến trình của quá trình, làm thay đổi trạng thái của hệ thống ở mỗi bước. Nhìn chung, quy hoạch động là một lý thuyết hài hòa dễ hiểu và đơn giản để sử dụng trong hoạt động thương mại khi giải các bài toán tuyến tính và phi tuyến.

Lập trình động là một trong những nhánh của lập trình tối ưu. Nó được đặc trưng bởi các phương pháp và kỹ thuật cụ thể được áp dụng cho các hoạt động trong đó quá trình ra quyết định được chia thành các giai đoạn (bước). Phương pháp quy hoạch động được sử dụng để giải các bài toán tối ưu biến thể với tiêu chí tối ưu cho trước, có mối liên hệ nhất định giữa các biến và hàm mục tiêu, được biểu diễn bằng hệ phương trình hoặc bất đẳng thức. Trong trường hợp này, như trong các bài toán được giải bằng phương pháp quy hoạch tuyến tính, các hạn chế có thể được đưa ra dưới dạng đẳng thức hoặc bất đẳng thức. Tuy nhiên, nếu trong các bài toán quy hoạch tuyến tính, sự phụ thuộc giữa hàm tiêu chí và các biến nhất thiết phải là tuyến tính, thì trong các bài toán quy hoạch động, các sự phụ thuộc này cũng có thể là phi tuyến. Lập trình động có thể được sử dụng để giải quyết các vấn đề liên quan đến động lực của một quá trình hoặc hệ thống và cho các vấn đề tĩnh liên quan, chẳng hạn như phân bổ nguồn lực. Điều này mở rộng đáng kể phạm vi lập trình động để giải các bài toán điều khiển. Và khả năng đơn giản hóa quy trình giải pháp, đạt được bằng cách giới hạn diện tích và số lượng được kiểm tra khi chuyển sang giai đoạn lựa chọn tiếp theo, làm tăng lợi thế của bộ phương pháp này.

Tuy nhiên, lập trình động cũng có nhược điểm. Trước hết, không có một phương pháp giải phổ quát duy nhất. Hầu hết mọi vấn đề được giải quyết bằng phương pháp này đều có đặc điểm riêng và đòi hỏi phải tìm kiếm bộ phương pháp thích hợp nhất để giải quyết nó. Ngoài ra, khối lượng lớn và độ phức tạp của việc giải các bài toán nhiều bước với nhiều trạng thái dẫn đến nhu cầu lựa chọn các bài toán ít chiều hoặc sử dụng thông tin nén. Điều thứ hai đạt được bằng cách sử dụng các phương pháp phân tích các tùy chọn và xử lý danh sách các trạng thái.

Đối với các quy trình có thời gian liên tục, quy hoạch động được coi là phiên bản giới hạn của sơ đồ giải pháp rời rạc. Kết quả thu được trong trường hợp này thực tế trùng khớp với kết quả thu được bằng phương pháp tối đa của L. S. Pontryagin hoặc Hamilton-Jacobi-Bellman.

Lập trình động được sử dụng để giải quyết các vấn đề trong đó có thể tìm kiếm phương án tối ưu bằng cách tiếp cận từng bước, ví dụ: phân bổ các khoản đầu tư vốn khan hiếm giữa các lĩnh vực sử dụng mới; xây dựng các quy tắc quản lý nhu cầu hoặc hàng tồn kho nhằm thiết lập thời điểm bổ sung và quy mô của đơn hàng bổ sung; xây dựng các nguyên tắc lập kế hoạch sản xuất và cân bằng việc làm trong điều kiện nhu cầu sản phẩm luôn biến động; lập kế hoạch lịch trình cho việc sửa chữa thiết bị hiện tại và lớn và thay thế thiết bị đó; tìm kiếm khoảng cách ngắn nhất trên mạng lưới giao thông; hình thành trình tự phát triển của hoạt động thương mại, v.v.