Thực đơn
trang chủSự liên quan

Lý thuyết quy hoạch động. Khái niệm quy hoạch động. Ở phía trên nó cũng viết về một dạng động lực học hai chiều nào đó.

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

2. Bản chất của phương pháp quy hoạch động……………..4

3. Ví dụ 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


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

Lập trình động (DP) về mặt 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ụ nhỏ hơn. Nó á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 cấu trúc 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. quyết định chung. 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 công cụ 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 phân tách chúng thành các phần nhỏ hơn và nhỏ hơn. nhiệm vụ phức tạp. trong đó tính năng đặc biệt là lời giải của các bài toán theo từng giai đoạn, ở những khoảng thời gian cố định, xác đị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ể nhận đượ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.

Vì vậy, lập trình động trong theo nghĩa rộngđại diện kiểm soát tối ưu quá trình, thông qua sự thay đổi thông số được kiểm soátở 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 chủ đề 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 hóa biến thể với tiêu chí nhất định tối ưu với kết nối nhất định giữa các biến và hàm mục tiêu, được biểu thị bằng hệ phương trình hoặc bất đẳng thức. Đồng thời, cũng như trong các bài toán giải bằng phương pháp lập trình tuyến tính, các ràng buộc 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 tính năng động của một quá trình hoặc hệ thống và cho các vấn đề tĩnh liên quan đến việc 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 phổ quát các giải pháp. 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; phát triển 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 về sản phẩm luôn biến động; lập kế hoạch lịch cho hiện tại và sửa chữa chính thiết bị và sự thay thế của nó; tìm kiếm khoảng cách ngắn nhất 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.


Bản chất của phương pháp quy hoạch động.

Phương pháp quy hoạch động dựa trên nguyên lý tối ưu, được nhà toán học người Mỹ Richard Bellman đưa ra vào năm 1957: “Hành vi tối ưu có đặc tính là bất kể trạng thái và quyết định ban đầu ở thời điểm ban đầu như thế nào, các quyết định tiếp theo phải tạo thành hành vi tối ưu so với trạng thái xuất phát từ quyết định đầu tiên”.

Bản chất vật lý của nguyên lý tối ưu là sai sót trong việc lựa chọn giải pháp khoảnh khắc này không thể sửa chữa trong tương lai.

Những điều sau đây đang được xem xét nhiệm vụ chung. Có một số hệ thống vật lý, trong đó một số quá trình xảy ra, bao gồm N các bước. Hiệu quả của quá trình được đặc trưng bởi một số chỉ số Wđược gọi là thắng. Hãy để tổng lợi ích W cho tất cả N các bước của quy trình bao gồm lợi ích ở các bước riêng lẻ

Ở đâu Wi- tiền thắng trên Tôi-bước thứ. Nếu như W có tính chất này, nó được gọi là tiêu chí phụ gia.

Quá trình về cái nào Chúng ta đang nói về, đại diện quá trình kiểm soát, I E. có thể chọn một số tham số ảnh hưởng đến tiến trình và kết quả của nó, và ở mỗi bước, một số quyết định được chọn mà tiền thắng phụ thuộc vào bước này. Giải pháp này được gọi là điều khiển bước. Tập hợp tất cả các bước điều khiển thể hiện sự kiểm soát của toàn bộ quá trình. Hãy biểu thị nó bằng chữ cái bạn và điều khiển bước - bằng các chữ cái. Sau đó

Kiểm soát bước trong trường hợp chung không phải số, mà, như một quy luật, vectơ, hàm, v.v.

Trong mô hình quy hoạch động, quy trình ở mỗi bước ở một trong các trạng thái S tập hợp các trạng thái S. Người ta tin rằng mỗi trạng thái được liên kết với một số điều khiển bước. Các điều khiển này sao cho điều khiển được chọn trong trạng thái nàyđối với bất kỳ lịch sử nào trước đó của quy trình, sẽ xác định hoàn toàn trạng thái tiếp theo của quy trình. Thông thường có hai điều kiện đặc biệt: S 0 - ban đầu và s w- cuối cùng.

Vì vậy, hãy để mỗi trạng thái được cung cấp một tập hợp các điều khiển bước có thể chấp nhận được và mỗi điều khiển bước tương ứng - trạng thái mà quá trình đi vào tôi là kết quả của việc sử dụng điều khiển bước bạn. Hãy để quá trình ở trạng thái ban đầu S 0 . Sự lựa chọn đặt quá trình vào trạng thái S 1 = σ( S 0 ,bạn 1), sự lựa chọn - để nêu S 2 = σ( S 1 ,bạn 2) v.v. Kết quả là một quỹ đạo quá trình bao gồm một chuỗi các cặp

và kết thúc ở trạng thái cuối cùng. Để nhất quán, chúng ta có thể giả sử rằng chỉ có một trạng thái được đưa vào, để quá trình ở cùng trạng thái cuối cùng. Cần lưu ý rằng tập hợp các trạng thái và biện pháp kiểm soát được chấp nhận

hữu hạn và Chúng ta cho nhiều S không giao nhau.

TRONG nhìn chung Bài toán quy hoạch động được phát biểu như sau: tìm quỹ đạo quá trình tại đó độ lợi (2.1) sẽ đạt cực đại.

Điều khiển đạt được độ lợi cực đại được gọi là kiểm soát tối ưu. Nó bao gồm một bộ điều khiển bước

Mức tăng tối đa đạt được với điều khiển này sẽ được biểu thị bằng Wmax:

Wmax= tối đa bạn{W(bạn)}. (2.5)

Sử dụng ví dụ về bài toán chiếc ba lô, chúng ta hãy xem xét ý nghĩa của từng bước, trạng thái, sự kiểm soát và mức chi trả.

Việc chất đồ lên ba lô có thể được coi là một quá trình bao gồm N các bước. Ở mỗi bước bạn cần trả lời câu hỏi: lấy vật phẩm này trong ba lô hay không? Vì vậy, bước quy trình là gán cho một biến x tôi giá trị 1 hoặc 0.

Bây giờ hãy xác định các trạng thái. Rõ ràng, trạng thái hiện tại của quy trình được đặc trưng bởi khả năng chuyên chở còn lại của ba lô - trọng lượng mà chúng ta vẫn có thể tùy ý sử dụng cho đến cuối cùng (cho đến khi ba lô được xếp gọn hoàn toàn). Vì vậy, dưới tình trạng trước đây Tôi

(2.10)

Cần phải tìm điều khiển tối ưu tại đó giá trị khuếch đại (2.10) trở thành tối đa.

Giả sử có một vấn đề mà chúng ta đã giải quyết được lập trình năng động, ví dụ: 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
Chúng ta hãy biểu thị một dãy răng cưa có độ dài N là một dãy trong đó với mỗi phần tử không cực trị thì thỏa mãn điều kiện sau: nó nhỏ hơn cả hai phần tử lân cận hoặc lớn hơn. Bạn cần đếm số dãy răng cưa gồm các chữ số có độ dài N . Nó trông giống như thế này:

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

Đây là một lớp động lực trong đó trạng thái là ranh giới của một phân đoạn của một số mảng. Vấn đề là tính toán câu trả lời cho các bài toán con dựa trên tất cả các phân đoạn có thể có trong mảng của chúng ta. Thông thường chúng được sắp xếp theo thứ tự độ dài tăng dần và việc tính toán lại dựa trên các đoạn ngắn hơn.
Ví dụ #4: Đóng gói một chuỗi
Đây là Điều kiện mở rộng. Tôi sẽ tóm tắt ngắn gọn:

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: Cây sồi

Động lực theo cây con

Tham số trạng thái của động lực dọc theo các cây con thường là một đỉnh, biểu thị cây con trong đó đỉnh này là gốc. Để có được giá trị của trạng thái hiện tại, bạn thường cần biết kết quả của tất cả các phần tử con của mình. Thông thường, họ thực hiện nó một cách lười biếng - họ chỉ đơn giản viết tìm kiếm theo chiều sâu từ gốc của cây.
Ví dụ #6: Cây logic
Cho một cây treo, các lá của cây chứa các số một bit - 0 hoặc 1. Tất cả các đỉnh bên trong cũng chứa các số, nhưng theo quy tắc sau: đối với mỗi đỉnh, một trong các phép toán logic được chọn: “AND” hoặc “OR”. Nếu là "VÀ", thì giá trị của đỉnh là "VÀ" logic từ giá trị của tất cả các con của nó. Nếu “HOẶC”, thì giá trị của đỉnh là “HOẶC” logic từ giá trị của tất cả các con của nó.

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 muốn nhận “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

Trong động lực tập hợp con, trạng thái thường bao gồm mặt nạ của một tập hợp nhất định. Chúng thường được sắp xếp theo thứ tự tăng số lượng đơn vị trong mặt nạ này và được tính toán lại, theo đó, từ các trạng thái bao gồm nhỏ hơn. Động lực học lười biếng thường được sử dụng để không suy nghĩ cụ thể về thứ tự truyền tải, điều này đôi khi không hoàn toàn tầm thường.
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
Cho một đồ thị có trọng số (trọng số các cạnh không âm) G có kích thước N . Tìm một chu trình Hamilton (một chu trình đi qua tất cả các đỉnh không tự giao nhau) có trọng số nhỏ nhất.

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 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ơ

Các bài toán cổ điển được giải bằng mô hình động học là các bài toán xếp một trường với một số số liệu. Hơn nữa, có thể yêu cầu những thứ khác nhau, chẳng hạn như số lượng phương pháp ốp lát hoặc ốp lát với số lượng hình tối thiểu.

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 mặt cắt 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
Tìm số cách xếp một bảng N x M bằng cách sử dụng các quân domino 1 x 2 và 2 x 1.

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 xếp chồng 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 bạn 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ứ trong mảng can - 1 nếu bạn có thể đi, 0 nếu bạn 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 - đường viền bên trái của trường - bức 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.
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

Đây là một sự tối ưu hóa rất mạnh mẽ về tính năng động của hồ sơ. Ở đây hồ sơ không chỉ là một mặt nạ mà còn là một điểm dừng. Nó trông như thế này:

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

Đôi khi xảy ra trường hợp chỉ biết một số đặc điểm của câu trả lời tốt nhất là không đủ. Ví dụ: trong nhiệm vụ "Đóng gói chuỗi" (ví dụ số 4), cuối cùng chúng ta chỉ nhận được độ dài của chuỗi nén ngắn nhất, nhưng rất có thể, chúng ta không cần độ dài của nó mà là chính chuỗi đó. Trong trường hợp này, bạn cần khôi phục câu trả lời.

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 một 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 trên đường đi.

Tối ưu hóa nhỏ

Ký ức
Thông thường trong động lực học người ta có thể gặp phải một vấn đề trong đó một trạng thái đòi hỏi phải đếm một số lượng không lớn các trạng thái khác. Ví dụ: khi tính các số Fibonacci, chúng ta chỉ sử dụng hai số cuối và không bao giờ quay lại các số trước đó. Điều này có nghĩa là bạn có thể quên chúng, tức là không lưu trữ chúng trong bộ nhớ. Đôi khi điều này cải thiện ước tính tiệm cận từ bộ nhớ. Kỹ thuật này có thể được sử dụng trong các ví dụ số 1, số 2, số 3 (trong giải pháp không có ma trận chuyển tiếp), số 7 và số 8. Đúng, điều này không thể được sử dụng theo bất kỳ cách nào nếu thứ tự truyền tải là động lực lười biếng.
Thời gian
Đôi khi bạn có thể cải thiện thời gian tiệm cận bằng cách sử dụng một số loại cấu trúc dữ liệu. Ví dụ: trong thuật toán Dijkstra, bạn có thể sử dụng hàng đợi ưu tiên để thay đổi thời gian tiệm cận.

Thay thế trạng thái

Trong các giải pháp theo động lực học, một trạng thái nhất thiết phải xuất hiện - các tham số xác định duy nhất nhiệm vụ con, nhưng trạng thái này không nhất thiết phải là trạng thái duy nhất. Đôi khi bạn có thể đưa ra các tham số khác và hưởng lợi từ điều này dưới dạng giảm thời gian hoặc bộ nhớ tiệm cận.
Ví dụ #9: Mở rộng số
Bạn cần tìm số cách phân rã của số N thành các số hạng khác nhau. Ví dụ: nếu N = 7 thì có 5 cách khai triển như vậy:
  • 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 có 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 này 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. Các vấn đề tìm ra con đường ngắn nhất cho logistics vận tải là 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 để 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 tại bất kỳ thời điểm 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 của các 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à

) trông giống như một tập hợp các bài toán con chồng lên nhau có độ phức tạp nhỏ hơn một chút so với bài toán gốc. 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.

Phương pháp lập trình động từ trên cao- đây là cách ghi nhớ đơn giản về kết quả của việc giải quyết những nhiệm vụ phụ có thể gặp lại trong tương lai. Lập trình động từ bên dưới liên quan đến việc chuyển đổi một bài toán phức tạp thành một chuỗi đệ quy gồm các bài toán con đơn giản hơn.

YouTube bách khoa toàn thư

  • 1 / 5

    Cụm từ “lập trình động” được R. Bellman sử dụng lần đầu tiên vào những năm 1990 để mô tả quá trình tìm giải pháp cho một vấn đề trong đó câu trả lời cho một vấn đề chỉ có thể có được sau khi giải quyết vấn đề “trước” nó. Ở thành phố, ông đã làm rõ định nghĩa này theo định nghĩa hiện đại. Lĩnh vực này ban đầu được thành lập với lĩnh vực phân tích và kỹ thuật hệ thống, được IEEE công nhận. Những đóng góp của Bellman cho quy hoạch động đã được ghi nhớ dưới cái tên phương trình Bellman, một kết quả trung tâm của lý thuyết quy hoạch động, trình bày lại một vấn đề tối ưu hóa ở dạng đệ quy.

    Từ “lập trình” trong cụm từ “lập trình động” thực ra gần như không liên quan gì đến lập trình “truyền thống” (viết code) và có ý nghĩa tương tự như trong cụm từ “lập trình toán học”, đồng nghĩa với từ “tối ưu hóa” . Do đó, từ “chương trình” trong ngữ cảnh này đúng hơn có nghĩa là chuỗi hành động tối ưu để đạt được giải pháp cho vấn đề. Ví dụ: lịch trình cụ thể của các sự kiện tại một cuộc triển lãm đôi khi được gọi là chương trình. Chương trình trong trường hợp này được hiểu là một chuỗi sự kiện hợp lệ.

    Ý tưởng lập trình động

    Cấu trúc nền tảng tối ưu trong quy hoạch động có nghĩa là lời giải tối ưu cho các bài toán con nhỏ hơn có thể được sử dụng để giải bài toán ban đầu. Ví dụ, đường đi ngắn nhất trong đồ thị từ một đỉnh (ký hiệu là s) đến một đỉnh khác (ký hiệu là t) có thể được tìm thấy như sau: đầu tiên, chúng ta tính đường đi ngắn nhất từ ​​tất cả các đỉnh liền kề với s đến t, sau đó lấy tính đến trọng số của các cạnh nối s với các đỉnh liền kề, chọn đường đi tốt nhất đến t (đỉnh nào là tốt nhất để đi qua). Nói chung, chúng ta có thể giải bài toán có cấu trúc con tối ưu bằng cách thực hiện ba bước sau.

    1. Chia nhỏ một nhiệm vụ thành các nhiệm vụ nhỏ hơn.
    2. Tìm giải pháp tối ưu cho các bài toán con theo cách đệ quy bằng cách thực hiện thuật toán ba bước tương tự.
    3. Sử dụng lời giải thu được cho các bài toán con để xây dựng lời giải cho bài toán ban đầu.

    Các nhiệm vụ con được giải bằng cách chia chúng thành các nhiệm vụ con có kích thước nhỏ hơn, v.v., cho đến khi người ta đi đến trường hợp tầm thường của một vấn đề có thể giải được trong thời gian không đổi (có thể nói ra câu trả lời ngay lập tức). Ví dụ: nếu chúng ta cần tìm n!, thì nhiệm vụ tầm thường sẽ là 1! = 1 (hoặc 0! = 1).

    Nhiệm vụ phụ chồng chéo trong lập trình động, chúng có nghĩa là các nhiệm vụ con được sử dụng để giải quyết một số vấn đề (không chỉ một) có quy mô lớn hơn (nghĩa là chúng ta thực hiện cùng một việc nhiều lần). Một ví dụ nổi bật là phép tính dãy Fibonacci, F 3 = F 2 + F 1 (\displaystyle F_(3)=F_(2)+F_(1)) Và F 4 = F 3 + F 2 (\displaystyle F_(4)=F_(3)+F_(2))- ngay cả trong trường hợp tầm thường như vậy, chúng ta cũng chỉ tính được hai số Fibonacci hai lần. Nếu chúng ta tiếp tục đi xa hơn và đếm, thì F 2 (\displaystyle F_(2)) sẽ được tính thêm hai lần nữa, vì để tính F 5 (\displaystyle F_(5)) sẽ lại cần thiết F 3 (\displaystyle F_(3)) Và F 4 (\displaystyle F_(4)). Điều xảy ra là một cách tiếp cận đệ quy đơn giản sẽ lãng phí thời gian tính toán giải pháp cho các vấn đề mà nó đã giải quyết được.

    Để tránh diễn biến của các sự kiện như vậy, chúng ta sẽ lưu lời giải của các bài toán con mà chúng ta đã giải và khi chúng ta cần lại lời giải của bài toán con đó, thay vì tính toán lại, chúng ta sẽ chỉ lấy nó từ bộ nhớ. Cách tiếp cận này được gọi là ghi nhớ. Chúng tôi cũng có thể thực hiện các tối ưu hóa hơn nữa - ví dụ: nếu chúng tôi hoàn toàn chắc chắn rằng chúng tôi sẽ không cần giải pháp cho một nhiệm vụ phụ nữa, chúng tôi có thể loại bỏ nó khỏi bộ nhớ, giải phóng nó cho các nhu cầu khác hoặc nếu bộ xử lý không hoạt động và chúng tôi biết rằng việc giải một số nhiệm vụ con chưa tính toán sẽ cần sau này, chúng ta có thể giải trước.

    Tóm tắt những điều trên, chúng ta có thể nói rằng quy hoạch động sử dụng các tính chất sau của bài toán:

    • nhiệm vụ chồng chéo;
    • kết cấu nền tối ưu;
    • khả năng ghi nhớ lời giải cho các bài toán con thường gặp.

    Lập trình động thường tuân theo hai cách tiếp cận để giải quyết vấn đề:

    • Lập trình động từ trên xuống: một bài toán được chia thành các bài toán con nhỏ hơn, các bài toán này được giải và sau đó được kết hợp để giải bài toán ban đầu. Ghi nhớ được sử dụng để giải quyết các vấn đề con thường gặp.
    • Lập trình động từ dưới lên: tất cả các nhiệm vụ con cần thiết sau đó để giải quyết vấn đề ban đầu đều được tính toán trước và sau đó được sử dụng để xây dựng giải pháp cho vấn đề ban đầu. Phương pháp này tốt hơn lập trình từ trên xuống về kích thước của ngăn xếp cần thiết và số lượng lệnh gọi hàm, nhưng đôi khi không dễ để biết trước những bài toán con nào chúng ta sẽ cần giải quyết sau này.

    Các ngôn ngữ lập trình có thể ghi nhớ kết quả của lệnh gọi hàm với một bộ đối số (memoization) cụ thể để tăng tốc độ "đánh giá theo tên". Một số ngôn ngữ có tích hợp sẵn tính năng này (ví dụ: Schema, Common Lisp, Clojure, Perl) và một số ngôn ngữ yêu cầu các phần mở rộng bổ sung (C++).

    Có quy hoạch động nối tiếp, được bao gồm trong tất cả các sách giáo khoa về nghiên cứu hoạt động, và lập trình động không nối tiếp (NSDP), hiện chưa được biết đến nhiều, mặc dù nó đã được phát hiện vào những năm 1960.

    Lập trình động thông thường là trường hợp đặc biệt của lập trình động không nối tiếp, khi đồ thị của các mối quan hệ biến chỉ đơn giản là một đường dẫn. NSDP, là một phương pháp tự nhiên và tổng quát để tính đến cấu trúc của một bài toán tối ưu hóa, coi một tập hợp các ràng buộc và/hoặc hàm mục tiêu là một hàm có thể tính toán đệ quy. Điều này cho phép bạn tìm giải pháp theo từng giai đoạn, ở mỗi giai đoạn bằng cách sử dụng thông tin thu được ở các giai đoạn trước và hiệu quả của thuật toán này trực tiếp phụ thuộc vào cấu trúc của biểu đồ mối quan hệ giữa các biến. Nếu biểu đồ này đủ thưa thớt thì lượng tính toán ở mỗi giai đoạn có thể được giữ trong giới hạn hợp lý.

    Một trong những đặc tính chính của các bài toán được giải bằng quy hoạch động là tính cộng. Các bài toán không cộng được giải bằng các phương pháp khác. Ví dụ, nhiều vấn đề về tối ưu hóa khoản đầu tư của một công ty không mang tính chất cộng thêm và được giải quyết bằng cách so sánh giá trị của công ty khi có và không có khoản đầu tư.

    Các bài toán lập trình động cổ điển

    • Bài toán về dãy con chung dài nhất: Cho 2 dãy con cần tìm dãy con chung dài nhất.
    • Bài toán tìm dãy con tăng dài nhất: Cho một dãy con cần tìm dãy con tăng dài nhất.
    • Bài toán khoảng cách biên tập (khoảng cách Levenshtein): cho hai chuỗi, bạn cần tìm số lần xóa, thay thế và thêm ký tự tối thiểu để biến chuỗi này thành chuỗi khác.
    • Bài toán về thứ tự nhân ma trận: ma trận đã cho A 1 (\displaystyle A_(1)), …, Một n (\displaystyle A_(n)), cần phải giảm thiểu số lượng các phép toán vô hướng để nhân chúng.
    • Vấn đề lựa chọn quỹ đạo
    • Vấn đề ra quyết định tuần tự
    • Vấn đề sử dụng lao động
    • Vấn đề quản lý hàng tồn kho