Ví dụ về điều khiển tối ưu lập trình động. Có phải nó được viết ở trên cùng về một dạng động lực học hai chiều nào đó không? Bài toán quy hoạch động ứng dụng
Xin chào, Habrakhabr. TRONG Hiện nay tôi đang làm việc dụng cụ trợ giảng về lập trình Olympic, một trong những đoạn 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 những khoảnh khắc khó khăn kèm theo 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 vấn đề Olympic trong lập trình, việc giải quyết bằng cách sử dụng đệ quy hoặc bạo lực đòi hỏi rất nhiều số lượng lớn hoạt động. 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 và một số bài toán khác, chúng ta có thể phân biệt một loại bài toán có một tài sản 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 phương pháp lập trình năng động và bằng cách lập trình động, chúng tôi muốn nói đến việc giảm bớt một nhiệm vụ thành các nhiệm vụ con.
trình tự
Bài toán trình tự cổ điển như sau.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ể được áp dụng:
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
Để hiểu rõ hơn bản chất của lập trình động, trước tiên chúng ta định nghĩa chính thức hơn các khái niệm về nhiệm vụ và nhiệm vụ con.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 xảy ra với 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 việc 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
Một bài toán kinh điển trong quy hoạch động hai chiều là bài toán tìm đường đi trên một trường hình chữ nhật.Trong các công thức khác nhau, bạn cần đếm số lượng tuyến đường hoặc tìm tuyến đường tốt nhất theo một nghĩa nào đó.
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
Xét bài toán dãy con tăng dần.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 tử 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ột 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 th 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ẽ).
Phần Lập trình động được biểu thị bằng các máy tính sau:
- Vấn đề phân bổ đầu tư. Để tái thiết và hiện đại hóa sản xuất tại bốn doanh nghiệp, kinh phí đã được phân bổ C = 80 den. các đơn vị Đối với mỗi doanh nghiệp, khả năng tăng fi (x) (i = 1, 4) của sản lượng đều được biết trước, tùy thuộc vào số tiền được phân bổ.
Trong các bài toán quy hoạch động, quy trình kinh tế phụ thuộc vào thời gian (hoặc vào một số khoảng thời gian), do đó, một số giải pháp tối ưu được tìm thấy (tuần tự cho từng giai đoạn) đảm bảo sự phát triển tối ưu của toàn bộ quy trình. Lập trình động là một công cụ toán học cho phép lập kế hoạch tối ưu các quy trình được kiểm soát và các quy trình phụ thuộc vào thời gian. Việc thực hiện tối ưu hóa từng bước được gọi là quy trình ra quyết định gồm nhiều bước. Một quá trình kinh tế được gọi là được kiểm soát nếu nó có thể tác động đến quá trình phát triển của nó.
Phương pháp quy hoạch động (DP) dựa trên nguyên tắc tối ưu hóa tuần tự: giải pháp cho bài toán tối ưu hóa nhiều chiều ban đầu được thay thế bằng giải pháp cho một chuỗi các vấn đề tối ưu hóa thứ nguyên nhỏ. Điều kiện chính để áp dụng phương pháp DP là khả năng chia quá trình ra quyết định thành một số bước hoặc giai đoạn tương tự nhau, mỗi bước được lên kế hoạch riêng biệt nhưng có tính đến kết quả thu được ở các bước khác. Ví dụ: hoạt động của một ngành trong một số năm kinh doanh hoặc chuỗi thử nghiệm được sử dụng trong việc kiểm soát thiết bị, v.v. Một số quy trình (hoạt động) được chia thành các bước một cách tự nhiên, nhưng có những hoạt động phải được chia thành các giai đoạn một cách nhân tạo, chẳng hạn như quá trình dẫn đường cho tên lửa vào mục tiêu.
Nguyên tắc này đảm bảo rằng điều khiển được chọn ở bất kỳ bước nào không phải là điều khiển tốt nhất cục bộ mà là điều tốt nhất theo quan điểm của toàn bộ quá trình, vì điều khiển này được chọn có tính đến hậu quả trong các bước sắp tới.
Hãy xem xét Mô tả chung về bài toán quy hoạch động.
Hãy chia quá trình ra quyết định gồm nhiều bước thành N các bước. Hãy ký hiệu ε 0 là trạng thái ban đầu của hệ thống, bằng ε 1, ε 2, … ε N– trạng thái của hệ thống sau lần thứ nhất, thứ hai, N-bước thứ. Nhìn chung, nhà nước
ε k– vectơ (ε k 1 , …, ε k s).
Sự quản lý trong một quy trình gồm nhiều bước, một tập hợp các giải pháp (các biến điều khiển) được gọi là bạn k = (bạn k 1 , ..., bạn biết đấy) được thực hiện ở mỗi bước k và chuyển hệ thống từ trạng thái ε k-1 = (ε k- 1 1 , …, ε k -1 S) để phát biểu ε k = (ε k 1 , …, ε k s).
Trong các quá trình kinh tế, quản lý bao gồm việc phân phối và tái phân phối vốn ở từng giai đoạn. Ví dụ, việc sản xuất sản phẩm của bất kỳ doanh nghiệp nào cũng là một quy trình được kiểm soát, vì nó được xác định bởi những thay đổi về thành phần thiết bị, khối lượng cung cấp nguyên liệu thô, lượng tài chính, v.v. trong năm, kỳ lập kế hoạch, việc cung cấp cho doanh nghiệp nguyên liệu thô, thay thế thiết bị, số tiền tài trợ, v.v. là quản lý. Có vẻ như để đạt được khối lượng đầu ra tối đa, cách dễ nhất là đầu tư số tiền tối đa có thể và sử dụng hết công suất thiết bị. Nhưng điều này sẽ dẫn đến sự hao mòn nhanh chóng của thiết bị và hậu quả là làm giảm sản lượng. Vì vậy, việc phát hành sản phẩm phải được lên kế hoạch sao cho tránh được những tác động không mong muốn. Cần phải thực hiện các biện pháp để đảm bảo rằng thiết bị được bổ sung khi nó bị hao mòn, tức là theo thời gian. Điều thứ hai, mặc dù dẫn đến giảm khối lượng đầu ra ban đầu, nhưng mang lại khả năng mở rộng sản xuất trong tương lai. Như vậy, quá trình sản xuất kinh tế có thể được coi là bao gồm nhiều giai đoạn (bước), mỗi giai đoạn đều ảnh hưởng đến sự phát triển của nó.
Sự bắt đầu của một giai đoạn (bước) của một quy trình được kiểm soát được coi là thời điểm đưa ra quyết định (về số vốn đầu tư, về việc thay thế một loại thiết bị nhất định, v.v.). Một giai đoạn thường được hiểu là một năm kinh doanh.
Thường kiểm soát ở mọi bước bạn k một số hạn chế được áp dụng. Các điều khiển thỏa mãn những hạn chế này được gọi là chấp nhận được.
Giả sử rằng chỉ số hiệu suất k Bước thứ của quy trình phụ thuộc vào trạng thái ban đầu ở bước này k-1 và từ điều khiển ở bước này bạn k, chúng ta thu được hàm mục tiêu của toàn bộ quy trình gồm nhiều bước dưới dạng: 
.
Bây giờ chúng ta xây dựng bài toán quy hoạch động: “Xác định tập hợp các biện pháp kiểm soát được chấp nhận ( bạn 1 , …, bạn n), chuyển hệ từ trạng thái ban đầu ε 0 sang trạng thái cuối cùng ε N và tối đa hóa hoặc giảm thiểu chỉ số hiệu quả F».
Kiểm soát đạt được mức tối đa (tối thiểu) của chức năng F gọi điện kiểm soát tối ưu bạn * = (bạn 1* ,…, bạn n *).
Nếu biến điều khiển bạn k lấy các giá trị rời rạc thì mô hình DP được gọi là rời rạc. Nếu các biến bạn k thay đổi liên tục thì mô hình DP được gọi là tiếp diễn.
Tùy thuộc vào số lượng tham số trạng thái S và số lượng biến kiểm soát r phân biệt một chiều Và đa chiều Nhiệm vụ DP.
Số bước trong một tác vụ có thể là cuối cùng hoặc bất tận.
Bài toán quy hoạch động ứng dụng
- vấn đề quy hoạch xây dựng cơ sở vật chất.
Lập trình năng động.
Khi mô hình hóa cấu trúc mạng, ngoài các vấn đề liên quan đến sự tồn tại của các luồng trong giao thông, điện, điện thoại, máy tính và các loại mạng khác, còn có một loạt các vấn đề phát sinh có thể được rút gọn thành bài toán đường đi ngắn nhất. Ví dụ: vấn đề về đường đi ngắn nhất luôn được giải quyết bằng chương trình bộ định tuyến khi một trang web được tìm thấy theo tên của nó trên Internet.
Bài toán đường đi ngắn nhất trong mạng có hướng là một bài toán quy hoạch động điển hình, do đó, mặc dù lập trình động, giống như quy hoạch mạng, có liên quan đến sự phát triển của các quy trình theo thời gian, việc mô hình hóa chúng sẽ được thảo luận chi tiết hơn trong phần tiếp theo, chúng tôi sẽ xem xét trong phần này phương pháp quy hoạch động trên ví dụ tìm đường đi ngắn nhất.
Khái niệm quy hoạch động có liên quan chặt chẽ với quy trình nhiều bước quyết định. Quy trình ra quyết định gồm nhiều bước có thể được định nghĩa là quá trình đưa ra các quyết định tuần tự nhằm đạt được một mục tiêu nhất định. Quá trình ra quyết định gồm nhiều bước liên tục gặp phải trong nhiều tình huống khác nhau, từ sửa chữa ô tô trong tiệm sửa chữa ô tô đến điều khiển tàu vũ trụ.
Lập trình động có thể được định nghĩa một cách lỏng lẻo là một tập hợp các thủ tục toán học được sử dụng trong phân tích các quy trình ra quyết định gồm nhiều bước. Mỗi quy trình quyết định gồm nhiều bước là một sự phát triển của vấn đề sau: tìm đường đi ngắn nhất trong mạng không tuần hoàn, có định hướng.
Quy hoạch động có thể được coi là một lý thuyết thống nhất do một tập hợp các ý tưởng và kỹ thuật được sử dụng trong phân tích toán học của nhiều vấn đề khác nhau. Những ý tưởng và kỹ thuật này là bản chất của lập trình động. Bellman là một trong những người đầu tiên hiểu được bản chất của nguyên lý tối ưu và bắt đầu áp dụng nó vào nhiều vấn đề tối ưu hóa phát sinh trong toán học, kỹ thuật, nghiên cứu hoạt động và các lĩnh vực khác.
Do đó, khái niệm quy hoạch động gắn liền với quá trình ra quyết định gồm nhiều bước để đạt được một mục tiêu cụ thể. Ví dụ, việc chuyển một chiếc máy bay từ quỹ đạo này sang quỹ đạo khác là một bài toán lập trình động điển hình, với điều kiện là việc điều chỉnh quỹ đạo được thực hiện bằng cách áp dụng một xung lực vào những thời điểm riêng biệt và mục tiêu là tiết kiệm nhiên liệu.
Mô tả quy hoạch động như một tập hợp các thủ tục toán học để điều khiển tối ưu một hệ thống rời rạc, nói chung bài toán điều khiển tối ưu có thể được phát biểu như sau. Tại những thời điểm riêng biệt t= 1, 2,..., N hệ thống nằm trong một trong các tập s i trạng thái được đặc trưng bởi vectơ trạng thái x (t). Việc chuyển đổi giữa các trạng thái liên tiếp được thực hiện bằng vectơ điều khiển u (t) theo định luật:
x (t) = g (t) (x (t) , bạn (t)) ; t= 1, 2,..., N
Các điều khiển u (t) được chọn từ tập hợp các điều khiển được chấp nhận và tạo thành một chuỗi các điều khiển được chấp nhận u (0) ,u (1) ,…,u (N). Trình tự các điều khiển được chấp nhận đối với trạng thái ban đầu x (0) nhất định xác định quỹ đạo của hệ thống x (0), x (1), x (2),…, x (N).
Mỗi quỹ đạo tương ứng với giá trị riêng của tiêu chí tối ưu F hoặc hàm điều khiển mục tiêu, bao gồm các đóng góp riêng lẻ ở mỗi giai đoạn điều khiển:
Bài toán điều khiển tối ưu là tìm trong một tập hợp các trình tự điều khiển một trình tự đạt được giá trị F nhỏ nhất. Trình tự như vậy được gọi là trình tự điều khiển tối ưu và xác định quỹ đạo tối ưu.
Lập trình động dựa trên nguyên tắc tối ưu Bellman, có thể được xây dựng như sau. Một chiến lược tối ưu có đặc tính là bất kể trạng thái ban đầu và quyết định tại thời điểm ban đầu, các quyết định tiếp theo phải hình thành một chiến lược tối ưu đối với trạng thái phát sinh sau quyết định ban đầu.
Ý nghĩa của nguyên lý tối ưu trở nên rõ ràng hơn nếu chúng ta xét rằng đối với một quỹ đạo tối ưu thì mỗi đoạn giữa điểm cuối và bất kỳ điểm trung gian nào cũng là một quỹ đạo tối ưu. Nguyên tắc tối ưu, hay nói cách khác là phương pháp lập trình động, cho phép bạn tìm ra chiến lược nhiều bước tối ưu bằng cách giải quyết một tập hợp các vấn đề tối ưu hóa một bước đơn giản hơn.
Phương pháp quy hoạch động được minh họa rõ ràng bằng ví dụ về tìm đường đi ngắn nhất giữa các nút cực trị của mạng định hướng. Hãy xem xét một số mạng được định hướng có 12 nút, mạng này cần được truyền từ nút bắt đầu (1) đến nút kết thúc (12) theo bốn bước, di chuyển từ nút này sang nút khác theo từng bước.
Cơm. 6.4.1. Đi qua một mạng có hướng dọc theo con đường ngắn nhất.
Các số chỉ ở cung ( tôi, j) bằng độ dài các cung tôi ij giữa các nút Tôi Và j(theo đơn vị thông thường). Các trạng thái có thể có của hệ thống s i trong trường hợp này có liên quan đến việc ở trong Tôi nút thứ, điều khiển u(t) được liên kết với việc lựa chọn hướng đường dẫn ở mỗi bước điều khiển. Bốn bước điều khiển u(1),...,u(4) lần lượt chuyển hệ từ trạng thái ban đầu s 1 sang trạng thái cuối cùng s 12 và do đó tạo thành một quỹ đạo nhất định cần tìm. Tiêu chí tối ưu F trong trường hợp này là độ dài quỹ đạo L, bao gồm độ dài của các cung riêng lẻ:
Nếu việc tìm kiếm đường đi ngắn nhất, tức là quỹ đạo tối ưu, không bắt đầu từ đầu mà từ cuối mạng và di chuyển theo hướng ngược lại với điểm đầu, thì trong trường hợp này chúng ta có thuật toán "quét ngược". Trong trường hợp này, khi thực hiện thuật toán quét lùi, việc di chuyển được thực hiện từ trạng thái cuối cùng s 12 đến trạng thái ban đầu s 1.
Khi bắt đầu tìm kiếm đường đi ngắn nhất, một bảng chuyển tiếp sẽ được biên soạn. Số hàng của bảng bằng số bước điều khiển, số cột bằng số trạng thái trừ đi một. Bảng này sẽ lưu trữ các bước điều khiển và các giá trị tương ứng của tiêu chí tối ưu Lt cho tất cả các trạng thái có thể có của hệ thống sau mỗi bước.
Bảng 6.4.1
| Nó | s 1 | s 2 | s 3 | s 4 | s 5 | S6 | s 7 | s 8 | s 9 | s 10 | s 11 |
| 12 | 12 6 | ||||||||||
| 10 | 11 10 | ||||||||||
| 5 | |||||||||||
| 1 |
Các ô đã điền của bảng được chia làm đôi. Điều khiển u(t) được nhập vào phần trên của ô đã điền, tức là trong trường hợp này là số nút mà quá trình chuyển đổi được thực hiện. Giá trị đóng góp Lt vào tổng giá trị của tiêu chí tối ưu L, thu được trong quá trình chuyển đổi từ nút tương ứng với ô này sang nút cuối cùng, được nhập vào phần dưới của ô đã điền.
Việc điền vào bảng bắt đầu bằng dòng đầu tiên, nơi lưu trữ thông tin về bước cuối cùng của đường dẫn. Trong trường hợp này, bước cuối cùng của đường dẫn được xác định duy nhất trong quá trình chuyển đổi từ bất kỳ trạng thái áp chót nào, có thể là một trong ba trạng thái có thể: s 9, s 10, s 11. Vì vậy, việc điều khiển tối ưu ở bước cuối cùng là hiển nhiên. Tùy theo trạng thái áp chót mà phần đóng góp cho tiêu chí tối ưu là L 4(9) = 12, L 4(10) = 6, hoặc L 4(11) = 7. Các giá trị đóng góp cho L này được viết ở phía dưới của các ô ở hàng đầu tiên của bảng. 6.4.1.
Trước bước áp chót - trong trường hợp này là bước thứ ba, tập hợp các trạng thái có thể có của hệ thống là (s 5, s 6, s 7, s 8). Bây giờ chúng ta hãy áp dụng nguyên lý Bellman để xác định quỹ đạo ở bước thứ ba và thứ tư. Nó nằm ở chỗ, bất kể hai bước điều khiển đầu tiên, đoạn quỹ đạo ở hai bước cuối cùng tự nó là một quỹ đạo tối ưu, tức là. đưa ra mức đóng góp tối thiểu của L 3 cho tiêu chí tối ưu.
Nếu trạng thái của hệ thống trước bước áp chót là trạng thái s 8 thì ở bước cuối cùng sự đóng góp cho L được xác định bởi quan hệ
L 3 (giây 5)=phút( 
}.
Vì có thể chuyển từ s 5 sang s 9 và s 11, tức là:
g(s 5,9) = s 9; ; L 4 (s 9) = 12,
g(s 5,11) = s 11; ; L 4 (s 11) = 7,
L 3 (s 5) = min(6+12, 4+7) = 11 và u(3) = 11.
Điều này có nghĩa là nếu hệ thống ở trạng thái s 5 thì điều khiển tối ưu trước tiên bao gồm việc chuyển sang trạng thái s 11, sau đó sang trạng thái s 12. Độ dài của cung từ s 5 đến s 12 bằng 11 đơn vị.
Tính toán đóng góp cho L tương tự cho các chuyển đổi từ trạng thái s 6, s 7, s 8, ta thu được các đóng góp sau:
L 3 (s 6)=min(7+12, 6+6)=12, u (3) =10;
L 3 (s 7)=min(5+6, 3+7)=10, u (3) =11;
L 3 (s 8)=min(10+6, 12+7)=16, u (3) =10;
Bốn cặp số thu được được viết ở dòng thứ hai của Bảng. 6.4.1.
Ở bước điều khiển thứ hai, đóng góp vào tiêu chí tối ưu phụ thuộc vào trạng thái ban đầu là
L 2 (s 2) = min( ) = min(11+11, 14+10) = 22, u(2) = 5;
L 2 (s 3) = min( ) = min(7+11, 9+12) = 18, u(2) = 5;
L 2(s 4) = min( ) = min(2+16, 3+12, 6+10) = 15, u(2) = 6;
Ba cặp số thu được được viết ở dòng thứ ba của Bảng 6.4.1.
Trạng thái ban đầu s 1 được xác định duy nhất, do đó, ở hàng cuối cùng của bảng, ô duy nhất được điền vào, trong đó các giá trị 3 và 24 được viết vì:
L 1 (s 1) = phút( 
) = min(5+22, 6+18, 11+15) = 24, u(1) = 3.
Bây giờ cuối cùng chúng ta có thể xác định trình tự điều khiển nhiều bước tối ưu. Ở bước đầu tiên u (1) = 3, tức là từ nút 1 chúng ta đến nút 3, ở bước thứ hai u (2) = 5, tức là chúng ta đi đến nút 5, sau đó sau khi điều khiển u (3) = 11 - đến nút 11 và cuối cùng là đến nút 12. Cuối cùng, chúng ta có được đường đi ngắn nhất qua mạng như trong Hình. 6.4.1, đi qua chuỗi trạng thái s 1 →s 2 →s 5 →s 11 →s 12 và độ dài của nó là 24 đơn vị quy ước.
Việc tìm kiếm đường đi ngắn nhất cũng có thể được thực hiện từ đầu mạng, trong khi thực hiện thuật toán quét chuyển tiếp, về cơ bản thực hiện các hoạt động cộng và so sánh tương tự, nhưng theo một trình tự hơi khác.
Các thuật toán quét tiến và lùi, mặc dù về cơ bản là khác nhau, cung cấp một phép cộng và một phép so sánh trên mỗi cung. Do đó, cả hai thuật toán đều có hiệu suất như nhau. Tuy nhiên, có một sự khác biệt quan trọng. Thuật toán quét tiến xét các cung hướng ngoại trong số các nút đó, đường đi ngắn nhất tôi tôi những gì đã được biết đến.
Thuật toán quét lùi xét các cung hộp thư đếnđến các nút đó, các đường dẫn ngắn nhất tôi j mà vẫn chưa được biết đến. Do trường hợp sau, thuật toán quét trực tiếp thường được ưu tiên hơn. Thuật toán này có thể được áp dụng cho bất kỳ cấu trúc nào của tập hợp đường dẫn ngắn nhất.
Việc giải bài toán đường đi ngắn nhất đơn giản minh họa một số tính năng đặc trưng sau đây vốn có trong các quy trình ra quyết định gồm nhiều bước phức tạp hơn nhiều:
1. Bài toán ban đầu chứa đựng nhiều bài toán tối ưu hóa; trong trường hợp này, mỗi nút sẽ giải quyết vấn đề riêng của mình.
2. Tập nghiệm của bài toán tối ưu được mô tả bằng phương trình hàm, là hệ phương trình kết nối một số bài toán tối ưu. Trong hệ thống như vậy, mỗi phương trình tương ứng với một nút và thường chứa các toán tử như min, max hoặc minimax ở bên phải dấu bằng và các biến như g i và g j ở cả hai vế của nó.
3. Có thể tìm ra giải pháp cho nhiều vấn đề tối ưu hóa bằng cách sử dụng thuật toán quét ngược, tương đương với quy trình có thứ tự để giải một chuỗi các phương trình hàm.
Lập trình động rất phù hợp để giải quyết các vấn đề liên quan đến mô hình hóa các hệ thống mạng không có cấu trúc đặc biệt. Do đó, các thuật toán quét tiến và lùi phù hợp để thực hiện các phép tính trong mạng không tuần hoàn. Thuật toán quét ngược có thể được khái quát hóa và sử dụng để giải các bài toán có yếu tố ngẫu nhiên. Điều này không thể thực hiện được đối với thuật toán quét tiến.
Khái niệm "trạng thái" đóng vai trò trung tâm trong lập trình động và các trạng thái có ý nghĩa như sau. Quá trình chuyển đổi được thực hiện từ trạng thái sang trạng thái chứa toàn bộ lịch sử của quá trình, tức là trạng thái được mô tả với mức độ chi tiết cho phép tính toán (đánh giá) các giải pháp thay thế hiện tại.
Đối với mô hình mạng, các trạng thái là các nút và các cung xuất phát từ một nút nhất định thể hiện các quyết định khác nhau có thể được đưa ra tại nút (trạng thái) đó. Với cách giải thích này, chúng ta có thể nói rằng quá trình chuyển đổi xảy ra từ trạng thái này sang trạng thái khác và trạng thái đại diện cho các điểm mà tại đó các quyết định được đưa ra. Câu lệnh trên có nghĩa là các cung rời khỏi một nút không liên quan đến đường đi mà nút này hoặc nút kia đã đến, tức là chúng không phụ thuộc vào các cung đến.
Các phần tử trạng thái thường được gọi là các biến trạng thái. Trong các mô hình lập trình động, các trạng thái đôi khi được nhóm thành các giai đoạn và quá trình chuyển đổi được thực hiện từ giai đoạn này sang giai đoạn khác. Ví dụ, trong bài toán đường đi ngắn nhất có các trạng thái, nhưng không có giai đoạn nào, vì không thể nhóm các trạng thái thành các tập hợp theo cách có sự chuyển đổi từ tập hợp này sang tập hợp khác.
Đi sâu vào nhiều vấn đề tối ưu hóa khác nhau cũng tương đương với việc giới thiệu khái niệm không gian trạng tháiđại diện cho một tập hợp các trạng thái. Trong phương trình hàm, đáp ứng tối ưu được coi là hàm của trạng thái bắt đầu và nguyên tắc tối ưu thiết lập mối quan hệ giữa các đáp ứng tối ưu cho các trạng thái bắt đầu khác nhau.
Một loạt S các trạng thái có thể (hoặc có thể quan sát được) được gọi là không gian trạng thái, và phần tử S từ S xác định một cách cụ thể tình trạng. Với mọi điều kiện S nhiều kết nối D(S) . Yếu tố d từ nhiều D(S) được gọi là phán quyết. Quy tắc theo đó một giải pháp khả thi được xác định cho mỗi trạng thái được gọi là chiến lược d.
Thực ra chiến lược d phù hợp với từng trạng thái S một số phần tử d( S) từ nhiều D(S). Tập hợp tất cả các dạng d như vậy không gian chiến lược D. Điều sau có nghĩa là việc lựa chọn một giải pháp ở một trạng thái nào đó không hạn chế sự lựa chọn ở tất cả các trạng thái khác. Về cơ bản, D là tích Descartes của các tập hợp D(S) Qua S.
Một trong những ý tưởng của lập trình động là mỗi chiến lược d phải có cái gọi là hàm lợi nhuận. Vd(S), có thể thu được dựa trên trạng thái S và sử dụng chiến lược d. Khái niệm hàm lợi nhuận (hoặc thu nhập) khái quát hóa khái niệm đóng góp L t vào giá trị tổng thể của tiêu chí tối ưu L được xem xét khi giải bài toán đường đi ngắn nhất.
Cụm từ “sử dụng chiến lược d” có nghĩa là bạn có thể S giải pháp d( S); quá trình sau đó được coi là đã vào trạng thái S", tức là trạng thái được thực hiện S", trong đó nghiệm d( S"), v.v. Hàm lợi nhuận có cấu trúc khá phức tạp, vì nó phụ thuộc vào trình tự các trạng thái và quyết định, vào phần thưởng liên quan đến các trạng thái và quyết định này, cũng như cách tổng hợp phần thưởng.
Trạng thái là sự mô tả lịch sử của một quy trình với mức độ chi tiết cho phép đánh giá các giải pháp thay thế hiện tại. Đặc tính chính của trạng thái là trạng thái là một bản ghi ngắn gọn về lịch sử của quá trình, và mức độ chi tiết cho phép chúng ta xác định hàm thu nhập địa phương. Nói cách khác, hàm thu nhập địa phương chỉ có thể phụ thuộc vào. S, d Và v.
Chương tiếp theo sẽ xem xét chi tiết hơn về chuỗi Markov, chuỗi có tầm quan trọng lớn trong việc mô hình hóa sự tiến triển theo thời gian của các hệ thống sản xuất và kỹ thuật. Ngoài ra còn có các mô hình ra quyết định Markov trong đó nhà nước Sđược xác định bởi một số cặp số (n, tôi) , nghiệm là hàm phụ thuộc vào chúng k và hàm thu nhập địa phương được xác định bởi biểu thức như h[(N, TÔI) , k, v] = R K tôi(N) + å j P k ij(N)v(n+ 1,j) (N
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 đó 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.
X 4
Lập trình động là một chủ đề được dành khá nhiều bài viết trên RuNet, vì vậy chúng tôi quyết định giải quyết nó. Bài viết này sẽ phân tích các vấn đề cổ điển thành các chuỗi, động học một chiều và hai chiều, biện minh cho các giải pháp và mô tả các cách tiếp cận khác nhau để thực hiện chúng. Tất cả mã đưa ra trong bài viết đều được viết bằng Java.
Chúng ta đang nói về cái gì vậy? Lập trình động là gì?
Một phương pháp giải quyết một vấn đề bằng cách chia nó thành nhiều nhiệm vụ con giống hệt nhau và được kết nối với nhau thường xuyên. Ví dụ đơn giản nhất là các số Fibonacci - để tính một số nhất định trong dãy này, trước tiên chúng ta cần tính số thứ ba bằng cách cộng hai số đầu tiên, sau đó là số thứ tư. theo cách tương tự dựa trên thứ hai và thứ ba, v.v. (vâng, chúng tôi đã nghe nói về công thức đóng).
Được rồi, làm thế nào để sử dụng cái này?
Giải pháp cho một vấn đề bằng quy hoạch động phải có những nội dung sau:
Vậy tôi có cần viết phương pháp đệ quy để giải quyết vấn đề này không? Tôi nghe nói họ chậm.
Tất nhiên, điều đó là không cần thiết, vẫn có những cách tiếp cận khác để thực hiện động lực học. Hãy xem xét chúng bằng cách sử dụng bài toán sau làm ví dụ:
Tính số hạng thứ n của dãy đã cho theo công thức:
a 2n = a n + a n-1 ,
a 2n+1 = a n - a n-1 ,
a 0 = a 1 = 1.
Ý tưởng giải pháp
Ở đây chúng ta có cả hai trạng thái ban đầu (a 0 = a 1 = 1) và các phụ thuộc. Khó khăn duy nhất có thể nảy sinh là việc hiểu rằng 2n là điều kiện cho số chẵn và 2n+1 là điều kiện cho số lẻ. Nói cách khác, chúng ta cần kiểm tra xem một số có phải là số chẵn hay không và đếm số đó bằng các công thức khác nhau.
Giải pháp đệ quy
Việc thực hiện rõ ràng là viết phương pháp sau:
Private static int f(int n)( if(n==0 || n==1) return 1; // Kiểm tra giá trị ban đầu if(n%2==0)( //Kiểm tra trả về chẵn lẻ f(n /2)+f(n/2-1); // Tính toán bằng công thức cho các chỉ số chẵn, // tham khảo các giá trị trước đó )else( return f((n-1)/2)-f((n -1) /2-1); // Tính toán bằng công thức cho // chỉ số lẻ, tham khảo các giá trị trước đó) )
Và nó hoạt động rất tốt, nhưng có một số sắc thái. Nếu chúng ta muốn tính f(12) , thì phương thức sẽ tính tổng f(6)+f(5) . Đồng thời, f(6)=f(3)+f(2) và f(5)=f(2)-f(1), tức là chúng ta sẽ tính giá trị của f(2) hai lần. Có một giải pháp cho vấn đề này - ghi nhớ (giá trị bộ nhớ đệm).
Giải pháp đệ quy với bộ nhớ đệm giá trị
Ý tưởng ghi nhớ rất đơn giản - khi chúng tôi tính toán một giá trị, chúng tôi sẽ nhập giá trị đó vào một loại cấu trúc dữ liệu nào đó. Trước mỗi phép tính, chúng tôi kiểm tra xem giá trị được tính có nằm trong cấu trúc này hay không và nếu có thì chúng tôi sẽ sử dụng nó. Một mảng chứa đầy các giá trị cờ có thể được sử dụng làm cấu trúc dữ liệu. Nếu giá trị của phần tử tại chỉ số N bằng giá trị của cờ thì chúng ta chưa tính được. Điều này gây ra những khó khăn nhất định, bởi vì giá trị của cờ không nên thuộc về tập hợp các giá trị hàm, điều này không phải lúc nào cũng rõ ràng. Cá nhân tôi thích sử dụng bảng băm hơn - tất cả các thao tác trong đó được thực hiện trong O(1), rất thuận tiện. Tuy nhiên, với số lượng giá trị lớn, hai số có thể có cùng hàm băm, điều này đương nhiên gây ra vấn đề. Trong trường hợp này, bạn nên sử dụng gỗ đỏ đen chẳng hạn.
Đối với hàm f(int) đã được viết sẵn, các giá trị bộ đệm sẽ trông như thế này:
HashMap tĩnh riêng tư
Không quá khó, bạn có đồng ý không? Nhưng điều này giúp loại bỏ một số lượng lớn các hoạt động. Bạn trả tiền cho việc này bằng cách tiêu thụ thêm bộ nhớ.
Tính tuần tự
Bây giờ chúng ta hãy quay lại nơi chúng ta bắt đầu - đệ quy chậm. Không chậm đến mức gây ra rắc rối thực sự trong đời thực, nhưng trong một cuộc thi lập trình thể thao, mỗi mili giây đều có giá trị.
Phương pháp tính toán tuần tự chỉ phù hợp nếu hàm chỉ đề cập riêng đến các phần tử trước nó - đây là nhược điểm chính nhưng không phải là nhược điểm duy nhất của nó. Bài toán của chúng ta thỏa mãn điều kiện này.
Bản chất của phương pháp này như sau: chúng ta tạo một mảng gồm N phần tử và điền các giá trị vào đó một cách tuần tự. Có thể bạn đã đoán rằng bằng cách này, chúng ta cũng có thể tính toán những giá trị không cần thiết cho câu trả lời. Trong một phần quan trọng của các bài toán động học, thực tế này có thể được bỏ qua, vì tất cả các giá trị thường cần thiết cho câu trả lời. Ví dụ, khi tìm kiếm đường đi ngắn nhất, chúng ta không thể không tính toán đường đi đến một điểm nào đó; chúng ta cần xem xét lại tất cả các phương án. Nhưng trong bài toán của chúng ta, chúng ta cần tính xấp xỉ giá trị log 2 (N) (trong thực tế nhiều hơn), đối với phần tử thứ 922337203685477580 (MaxLong/10), chúng ta sẽ cần 172 phép tính.
Private static int f(int n)( if(n<2) return 1; //Может, нам и вычислять ничего не нужно?
int fs = int[n]; //Создаём массив для значений
fs=fs=1; //Задаём начальные состояния
for(int i=2; i Một nhược điểm khác của phương pháp này là mức tiêu thụ bộ nhớ tương đối lớn. Bây giờ về cơ bản chúng ta phải viết đệ quy của riêng mình. Ý tưởng như sau - đầu tiên chúng ta “đi xuống” từ N về trạng thái ban đầu, ghi nhớ các đối số mà chúng ta sẽ cần để tính hàm. Sau đó, chúng ta quay lại "lên", tính toán tuần tự các giá trị từ các đối số này, theo thứ tự mà chúng ta đã viết ra. Sự phụ thuộc được tính như sau: Danh sách liên kết Kích thước ngăn xếp kết quả là số lượng phép tính chúng ta cần thực hiện. Đây là cách tôi có được số 172 được đề cập ở trên. Bây giờ chúng tôi trích xuất từng chỉ số một và tính toán các giá trị cho chúng bằng các công thức - đảm bảo rằng tất cả các giá trị cần thiết sẽ được tính toán. Chúng tôi sẽ lưu trữ nó như trước - trong bảng băm. Bản đồ băm Tất cả các giá trị cần thiết đã được tính toán, tất cả những gì còn lại là viết Trả về giá trị.get(n); Tất nhiên, giải pháp này tốn nhiều thời gian hơn, nhưng nó đáng giá. Để rõ ràng hơn, chúng ta hãy phân tích bài toán sau đây đối với động lực học một chiều: Ở đầu một cái thang có N bậc thang có một quả bóng bắt đầu nhảy từ dưới lên. Bóng có thể nhảy sang bước tiếp theo, muộn hơn một bước hoặc muộn hơn hai bước (Tức là nếu bóng ở bước thứ 8 thì có thể chuyển sang bước thứ 5, 6 hoặc 7.) Xác định số lượng có thể “. đường đi của quả bóng từ trên xuống mặt đất. Bạn có thể đến bước đầu tiên chỉ bằng một cách - bằng cách thực hiện một bước nhảy có độ dài bằng một. Bạn có thể đến bước thứ hai bằng cách thực hiện bước nhảy có độ dài 2 hoặc từ bước đầu tiên - chỉ có 2 tùy chọn. Bạn có thể đến bước thứ ba bằng cách thực hiện bước nhảy dài ba bước, từ bước đầu tiên hoặc ba bước. Những thứ kia. chỉ có 4 lựa chọn (0->3; 0->1->3; 0->2->3; 0->1->2->3). Bây giờ chúng ta hãy xem bước thứ tư. Bạn có thể đến đó từ bước đầu tiên - một tuyến đường cho mỗi tuyến đường trước nó, từ bước thứ hai hoặc từ bước thứ ba - tương tự. Nói cách khác, số đường đi đến bước thứ 4 bằng tổng số đường đi đến bước 1, 2 và 3. Về mặt toán học, F(N) = F(N-1)+F(N-2)+F(N-3) . Chúng ta sẽ coi ba bước đầu tiên là các trạng thái ban đầu. Không có gì phức tạp ở đây. Dựa trên thực tế là, nhìn chung, một giải pháp đơn giản trên một mảng gồm N phần tử là hiển nhiên, tôi sẽ trình bày ở đây một giải pháp trên một mảng chỉ có ba phần tử. Int vars = int mới; vars=1;vars=2;vars=4; for(int i=3; i Vì mỗi giá trị tiếp theo chỉ phụ thuộc vào ba giá trị trước đó nên không có giá trị nào dưới chỉ số nhỏ hơn i-3 sẽ hữu ích cho chúng ta. Trong đoạn mã trên, chúng ta viết một giá trị mới thay cho giá trị cũ nhất, giá trị này không còn cần thiết nữa. Luân chuyển phần còn lại của phép chia cho 3 giúp chúng ta tránh được một loạt các câu lệnh có điều kiện. Đơn giản, nhỏ gọn, sang trọng. Không có tính năng đặc biệt nào liên quan đến động lực học hai chiều, nhưng để đề phòng, tôi sẽ xem xét ở đây một vấn đề cho nó. Trong bảng NxM hình chữ nhật, lúc đầu người chơi ở ô phía trên bên trái. Trong một nước đi, anh ta được phép di chuyển sang ô liền kề sang phải hoặc xuống (cấm di chuyển sang trái và lên). Đếm xem người chơi có bao nhiêu cách để vào ô dưới cùng bên phải. Logic của lời giải hoàn toàn giống với logic trong bài toán về quả bóng và cái thang - chỉ bây giờ bạn mới có thể đến ô (x,y) từ các ô (x-1,y) hoặc (x, y-1). Tổng F(x,y) = F(x-1, y)+F(x,y-1) . Ngoài ra, bạn có thể hiểu rằng tất cả các ô có dạng (1,y) và (x,1) chỉ có một tuyến đường - thẳng xuống hoặc thẳng sang phải. Vì Chúa, đừng thực hiện động lực 2D thông qua đệ quy. Người ta đã đề cập rằng đệ quy kém hiệu quả hơn vòng lặp về mặt hiệu suất, vì vậy đệ quy hai chiều cũng rất tệ khi đọc. Chỉ trong một ví dụ đơn giản như vậy, nó mới có vẻ dễ dàng và vô hại. Private static int f(int i, int j) ( if(i==1 || j==1) return 1; return f(i-1, j)+f(i, j-1); ) Để kết luận, tôi sẽ đưa ra một số bài toán điển hình cho động học một chiều và động học hai chiều kèm theo; Khi xử lý vật liệu phóng xạ, hai loại chất thải được tạo ra - cực kỳ nguy hiểm (loại A) và không nguy hiểm (loại B). Các thùng chứa tương tự được sử dụng để lưu trữ chúng. Chất thải sau khi được cho vào thùng chứa sẽ được xếp chồng lên nhau theo chiều dọc. Một chồng được coi là dễ nổ nếu nó chứa nhiều hơn một thùng chứa Loại A liên tiếp. Một chồng được coi là an toàn nếu nó không nổ. Với số lượng thùng chứa N cho trước, hãy xác định số loại ngăn xếp an toàn có thể có. Câu trả lời là số Fibonacci thứ (N+1). Có thể đoán bằng cách tính 2-3 giá trị đầu tiên. Có thể chứng minh điều đó một cách chặt chẽ bằng cách xây dựng một cây các công trình có thể. Mỗi phần tử chính được chia thành hai - chính (kết thúc bằng B) và phụ (kết thúc bằng A). Các phần tử phụ biến thành phần tử chính trong một lần lặp (chỉ có thể thêm B vào chuỗi kết thúc bằng A). Đây là điển hình cho số Fibonacci. Ví dụ như thế này: //Nhập số N từ bàn phím N+=2; BigInteger fib = BigInteger mới; fib=fib=BigInteger.ONE; for(int i=2; i Cậu bé đến gần cầu thang thu phí. Để bước lên bất kỳ bước nào, bạn cần phải trả số tiền ghi trên đó. Cậu bé biết cách bước sang bước tiếp theo hoặc nhảy qua một bước. Bạn cần tìm ra số tiền nhỏ nhất mà cậu bé sẽ cần để đạt được bước trên cùng. Rõ ràng số tiền cậu bé sẽ đưa ở bước thứ N chính là số tiền cậu đã đưa trước đó cộng với chi phí của chính bước đó. “Số tiền anh ấy đưa trước” phụ thuộc vào việc cậu bé bước đến bước thứ N - từ bước (N-1) hay từ bước (N-2). Bạn cần chọn cái nhỏ nhất. Ví dụ như thế này: Int Imax; //*nhập số bước từ bàn phím* DP = new int; for(int i=0; i Có một máy tính thực hiện ba thao tác: Xác định số thao tác tối thiểu cần thiết để có được số N cho trước từ số 1. In số này và trên dòng tiếp theo một tập hợp các thao tác đã thực hiện có dạng “111231”. Giải pháp đơn giản nhất là chia số đó cho 3 càng lâu càng tốt, nếu không thì chia cho 2 nếu có thể, nếu không thì trừ đi một, v.v. cho đến khi nó trở thành một. Đây là quyết định sai lầm vì... chẳng hạn, nó loại bỏ khả năng trừ một số rồi chia cho ba, điều này có thể gây ra lỗi ở các số lớn (chẳng hạn như 32718). Giải pháp đúng là tìm cho mỗi số từ 2 đến N số hành động tối thiểu dựa trên các phần tử trước đó, nói cách khác: F(N) = min(F(N-1), F(N/2), F (N/3) ) + 1 . Cần nhớ rằng tất cả các chỉ mục phải là số nguyên. Để tạo lại danh sách các hành động, bạn cần đi theo hướng ngược lại và tìm chỉ số i sao cho F(i)=F(N), trong đó N là số phần tử được đề cập. Nếu i=N-1, viết 1 ở đầu dòng, nếu i=N/2 - hai, nếu không - ba. Mỗi ô của bảng hình chữ nhật N*M chứa một số. Ban đầu, người chơi ở ô phía trên bên trái. Trong một nước đi, anh ta được phép di chuyển sang ô liền kề sang phải hoặc xuống (cấm di chuyển sang trái và lên). Khi đi qua một ô, người chơi được lấy số kg thức ăn bằng với con số ghi trong ô này (thức ăn cũng được lấy ở ô đầu tiên và ô cuối cùng trên đường đi của mình). Bạn cần tìm trọng lượng tối thiểu của thực phẩm tính bằng kilogam để người chơi có thể đưa vào góc dưới bên phải.Tạo ngăn xếp chỉ mục
Được rồi, toán học thật đẹp. Còn những nhiệm vụ không được giao mọi thứ thì sao?
Ý tưởng giải pháp
Thực hiện thông qua đệ quy
riêng tư tĩnh int f(int n)( if(n==1) trả về 1; if(n==2) trả về 2; if(n==3) trả về 4; trả về f(n-1)+f(n -2)+f(n-3) Có phải nó được viết ở trên cùng về một loại động lực học hai chiều nào đó không?..
Ý tưởng giải pháp
Thực hiện thông qua đệ quy
Thực hiện thông qua một loạt các giá trị
int dp = int mới; for(int i=0; i Tuyệt vời, tôi hiểu mọi thứ. Tôi nên kiểm tra kỹ năng của mình về điều gì?
Nguy cơ nổ
Giải pháp
Thực hiện
Leo cầu thang
Giải pháp
Thực hiện
Máy tính
Giải pháp
Thực hiện
int N; //Nhập bàn phím int a = new int; a= 0; ( int phút; for(int i=2; i Cách rẻ nhất
