Quy hoạch tối ưu một bảng hai chiều - Bài toán tổng quát
Đỗ Sơn Huỳnh
Córất nhiều bài toán tối ưu trên một bảng cho trước gồm M dòng, N cộtnhư các dạng bài
tìm một hành trình đi từ dòng thứ nhất tới dòngthứ M thoả mãn một điều kiện tối ưu nào
đó. Nhưng cũng có nhữngbài toán tối ưu với số liệu ban đầu là các mảng phần tử một
chiềuđều có thể đưa về bài toán quy hoạch tối ưu trên một bảng hai chiều.Một ví dụ dễ
thấy và dễ gặp nhất là bài toán tìm xâu con lớn nhất,tìm đoạn dãy con đơn điệu dài nhất,
bài toán cây xăng, và điểnhình nhất là bài toán cái túi (với dữ liệu đầu vào là nguyên).
Tất cả các bài toán đó chúng ta đều có thể đưa về một dạngtổng quát mà tôi tạm gọi là
″Bài toán tổng quát quy hoạch tốiưu trên một bảng hai chiều ″. Bài viết này là sự tổng
hợp củabản thân tôi trong quá trình học môn tin học PASCAL.Xin nêu ra để các bạn có
thể tham khảo và cho nhữngý kiến quý báu.
Phát biểu bài toán
Cho một bảng gồm M dòng, N cột. Hãy tìm một phương án tối ưuđể ″đi ″ từ dòng thứ
nhấtđến hết dòng thứ M với các nguyên tắc sau:
1.Điều kiện tối ưu:
Làđiều kiện bài toán đưa ra. Đường đi tối ưu được tính bằng tổngtrọng số các ô đi qua.
Trọng số của một ô phụ thuộc quy tắc tínhtrọng số của bài toán.
2.Quy tắc tính trọng số:
-Trọng số bằng trị sốchính số liệu tại ô.
-Trọng số được tính bằngquy tắc do ô đứng trước quy định tuỳ theo từng bài toán.
-Trọng số phụ thuộc vàoô đứng trước ô đang xét.
3.Quy tắc ″Đitừ trên xuống dưới ″:
Từdòng thứ i bạn có thể đi ngang sang trái hoặc sang phải trên dòng đóvà đi xuống dưới
dòng thứ (i+1) theo các hướng chéo hoặc thẳng đứng.
Thuậtgiải chung
1.Bước 0:Mô hình hoá:
Nếu bài toán không phải là dạng tối ưu trênmột bảng hai chiều, ta phải tìm cách mô hình
hoá để đưa nó về dạngnày.
2.Bước 1:Xây dựng các quy tắc tính trọng số:
Xin lưu ý rằng điều kiện tối ưu ở đâyđã có sẵn ngay từ đầu.

45(lượng thức ăn Max)
(1,1)(2,1) (2,2) (2,3) (3,3)
Thuật giải
-Bước 0:Bỏ qua vì đây là bài toán đúng dạng
-Bước 1:Trọng số ở đây là lượng thức ăn trên mỗi ô.
-Bước 2:Quy tắc đi:
Bước 3:Công thức quy hoạch
B[i,j]là lượng thức ăn lớn nhất đi từ ô (1,1) đến ô (i,j)
B[1,j]= A[1,j] với j = 1..N
B[i,1]= A[i,1]+B[i-1,1] với i = 2..M
B[i,j]=Max{B[i-1,j],B[i,j-1]} + A[i,j] với i = 2..M và j = 2..N
2.Bài toán ″Sa mạc ″:
Mộtbãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạccó một độ cao
nào đó. Một người muốn đi từ bờ đầu này sang bờcuối cùng bên kia. Người đó chỉ có thể
đi từ ô đang đứng tới mộtô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả thiết
rằngngười đó không được vượt ra hai mép trái và phải của sa mạc.
Hãytìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất.Mỗi lần đi từ
một ô sang ô mới tiếp theo người đó phải đi hết quãngđường bằng độ chênh cao giữa hai ô
đó.
SAMAC.INP
SAMAC.OUT
12(Quãng đường Min)
(1,3)(2,4) (3,3) (4,2) (5,2)
Thuật giải-Bước 0:Bỏ qua
- Bước 1:Trọng số là độ chênh cao giữa hai ô liên tiếp.
- Bước 2:Quy tắc đi.
-Bước 3:Công thức tối ưu:
B[i,j]là quãng đường nhỏ nhất đi từ bờ đầu tiên đến ô (i,j).
B[1,j]= 0 với j = 1..N
B[i,1]= Min { B[i-1,1] + abs(A[i,1] - A[i-1,1]);

M dòng tiếp theo ghi sốlượng hàng quy định tại mỗi ngăn chứa. Mỗi dòng gồm N số cách
nhaubởi ít nhất một dấu trắng.
Kếtquả ghi ra FILE văn bản SHOP.OUT như sau:
Dòng một là sốlượng hàng nhiều nhất.
-Dòng hai điểm xuất phátvà quá trình mua hàng. Mỗi ngăn chứa đi qua được biểu diễn theo
dạng ″(x,y) ″ trong đó (x,y) là vị trí của ngăn chứa.
SHOP.INP
SHOP.OUT
80(Lượng hàng mua được Max)
(1,3)(1,2) (2,2) (2,1) (3,1) (3,2) (3,3) (3,4) (4,4)
Thuật giải:
Bước 0:Bỏ qua
Bước 1:Trọng số ở đây là số lượng hàng tại các ngăn chứa. Đồng thời khithoả mãn điều
kiện ″khuyến mãi ″ thì trọng số sẽ được tăng thêmsố lượng bằng số các con số may mắn
(phụ thuộc vào ô đứng trước).
Bước 2:Quy tắc đi
Bước 3:Công thức
B[i,j]là lượng hàng max khi đi từ tầng 1 cho đến ngăn chứa (i,j)
B[0,j]= 0 với j =1..N
B[i,0]= 0 với i =1..M
B[i,j]= Max{B[i,j-1]+KM1, B[i-1,j] + KM2,
B[i-1,k]+ SA[i,u]+KM3}+A[i,j]
Với i =1..M , j =1..(N-1) , k =(j+1)..M , u = j+1..k
KM1 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i,j-1]) là con sốmay mắn.
KM2 là lượng hàng khuyến mãi nếu Abs(A[i,j]-A[i-1,j]) là con sốmay mắn.
KM3 là tổng số lượng hàng khuyến mãi nếu Abs(A[i,k]-A[i-1,k]) vàAbs(A[i,t]-A[i,t+1])
với t = j..(u-1) là các con số may mắn.
B[i,N]= Max{B[i,N-1]+KM1,B[i-1,N]+KM2}+A[i,N]
Với i =1..M
KM1 là lượng hàng khuyến mãi nếu abs(A[i,N]-A[i,N-1]) là con sốmay mắn.