BÀI TOÁN QUY HOẠCH
Bài toán quy hoạch là bài toán tối ưu: gồm có một hàm f gọi là hàm mục tiêu hay hàm đánh giá; các hàm g1, g2,…., gn cho giá trị logic gọi là hàm ràng buộc.
Yêu cầu của bài toán là tìm một cấu hình x thỏa mãn tất cả các ràng buộc g1,g2,…, gn : gi(x) = TRUE ( với mọi giá trị i mà 1<= i <= n) và x là tốt nhất, theo nghĩa không tồn tại một cấu hình y nào khác thỏa mãn các hàm ràng buộc mà f(y) tốt hơn f(x).
Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương pháp tối ưu cho bài toán có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con.
Đối với nhiều thuật toán đệ quy, nguyên lý chia để trị ( divide ang conquer) thường đóng vai trò chỉ đạo trong thiết kế thuật toán.
Để giải quyết một bài toán lớn, ta có thể chia nó làm nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. Trong phương pháp quy hoạch động, nguyên lý này càng được thể hiện rõ.
Khi không biết cần phải giải quyết những bài toán con nào, ta sẽ đi giải quyết tất cả các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn.
Đó chính là điểm khác nhau giữa Quy hoạch động và phép nhân giải đệ quy và cũng là nội dung phương pháp quy hoạch động:
· Phép nhân giải đệ quy bắt đầu từ bài toán lớn phân rã thành nhiều bài toán con và đi giải từng bài toán đó. Việc giải từng bài toán con lại đưa về phép phân rã tiếp thành nhiều bài toán nhỏ hơn và lại đi giải tiếp bài toán nhỏ hơn đó bắt kể nó đã được giải quyết hay chưa.
· Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất ( bài toán cơ sở) để từ đó từng bước giải quyết những bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất ( bài toán ban đầu).
+Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thỏa mãn những yêu cầu dưới đây hay không:
1) Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của bài toán con đó cho ta lời giải của bài toán lơn.
2) Vì quy hoạch động là đi tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải ( bộ nhớ, đĩa,…) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.
3) Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước.
Các khái niệm
+ Bài toán giải theo phương pháp quy hoạch động gọi là bài bài toán quy hoạch động
+Công thức phối hợp nghiệm của bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi ( hay phương trình truy toán) của quy hoạch động.
+Tập các bài toán nhỏ nhất có ngay lời giải để từ đó giải quyết cacs bài toán lớn hơn gọi là cơ sở quy hoạch động .
+Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động.
CÁC BƯỚC CÀI ĐẶT MỘT CHƯƠNG TRÌNH SỬ DỤNG QUY HOẠCH ĐÔNG:
1) Giải tất cả các bài toán cơ sở ( thông thường rất dễ), lưu các lời giải vào bảng phương án.
2) Dùng công thức truy hồi phối hợp những bài toán nhỏ đã lưu trong bảng phương án để tìm ra lời giải của những bài toán lớn hơn và lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu được giải.
3) Dựa vào bảng phương án, truy vết nghiệm tối ưu.
MÔT SỐ BÀI TOÁN QUY HOẠCH ĐÔNG
BÀI TOÁN 1: DÃY CON ĐƠN ĐIÊU TĂNG DÀI NHẤT
Cho dãy số nguyên A = a[1…n] ( n<= 10^6 và -10^6 <= a[i] <= 10^6). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự . Như vậy A có 2^n dãy con.
Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.
Ví dụ: A = ( 1,2,3,4,9,5,6,7 ). Dãy con đơn điệu tăng dài nhất: ( 1,2,3,4,,5,6,7).
Input: file văn bản INCSEQ.INP
+Dòng 1 : Chứa số n
+Dòng 2: Chứa n số a[1],a[2],…,a[nư cách nhau ít nhất một dấu cách.
Output: File văn bản INCESEQ.OUT
+Dòng 1: Ghi độ dài dãy con tìm được
+Dòng 2: Ghi dãy con tìm được và chỉ số những phần tử được chọn vào dãy con đó.
INCSEQ.INP | INCSEQ.OUT |
11 1 2 3 8 9 4 5 6 20 9 10 | 8 A[1] = 1 A[2] = 2 A[3] = 3 A[6] = 4 A[7] = 5 A[8] = 6 A[10] = 9 A[11] = 10 |
Bổ sung vào A hai phần tử : a[0] = âm vô cùng và a[n+1] = dương vô cùng. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a[0] và kết thúc ở a[n+1].
Với mọi i : 0 <= i <= n +1. Ta sẽ tính L[i] = độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại a[i].
1.1. CƠ SỞ QUY HOẠCH ĐÔNG ( bài toán nhỏ nhất):
L[n+1] = độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại a[n+1] = dương vô cùng. Dãy này chỉ gồm mỗi một phần tử ( dương vô cùng) nên L[n+1] = 1;
1.2. CÔNG THỨC TRUY HỒI:
Giả sử với i chạy từ n về 0, ta cần tính L[i]: độ dài dãy con tăng dài nhất bắt đầu tại a[i]. L[i] được tính trong điều kiện L[i+1….n+1] đã biết:
Dãy con đơn điệu tăng dài nhất bắt đầu từ a[i] sẽ được thành lập bằng cách lấy a[i] ghép vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí a[j] đứng sau a[i]. Ta sẽ chọn dãy nào để ghép a[i] vào đầu?
Tất nhiên là chỉ ghép a[i] vào đầu những dãy con bắt đầu tại a[j] nào đó lớn hơn a[j] ( để đảm bảo tính tăng) và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép a[i] vào đầu ( để đảm bảo tính dài nhất).
Vậy L[i] được tính như sau:
Xét tất cả các chỉ số j trong khoảng từ i +1 đến n +1 mà a[j] > a[i], chọn ra chỉ số jamx có có L[jmax] lớn nhất. Đặt L[i] := L[jmax] + 1:
1.3. TRUY VẾT:
Tại bước xây dựng dãy L , mỗi khi gán L[i] := L[jmax] + 1, ta đặt T[i] = jmax. Để lưu lại rằng: Dãy con dài nhất bắt đầu tại a[i] sẽ có phần tử thứ 2 kế tiếp là a[jmax].
Sau khi tính xong hai dãy L và T, ta bắt đầu từ T[0].
T[0] chính là phần tử đầu tiên được chọn
T[T[0]] là phần tử thứ 2 được chọn
T[T[T[0]]] là phần tử thứ ba được chọn
// Giai thuat: DAY CON DON DIEU TANG DAI NHAT
procedure Optimize; { Quy hoach dong }
var
i,j,jmax : Integer;
begin
a[0] := Low(Integer); a[n+1] := High(Integer);
{ Them 2 phan tu canh 2 dau day a }
L[n+1] := 1; { Dien co so cua quy hoach dong vao bang phuong an }
for i:= n downto 0 do { Tinh bang phuong an }
begin
jmax := n+1;
for j:= i+1 to n+1 do
if(a[j] > a[i]) and ( L[j] > L[jmax]) then jmax := j;
L[i] := L[jmax] + 1;
{ Luu do dai day con tang dai nhat bat dau tai a[i] }
T[i] := jmax;
{Luu vet phan tu dung truoc lien sau a[i] trong day con}
{ tang dai nhat do la a[jmax]}
end;
end;
//Truy vet va tinh toan
#include<iostream>
#define MAX 1000000
#define minValue -36767
#define maxValue 36767
int a[MAX+1], L[MAX +1], T[MAX + 1];
int n;
void Enter()
{
std::cin>>n;
for ( int i =1;i<= n;++i)
std::cin>>a[i];
}
void Optimize()
{
int i,j, jmax;
a[0] = minValue;
a[n+1] = maxValue;
L[n+1] = 1;
for( i =n; i>=0;--i)
{
jmax = n+1;
for( j = i+1; j<= n+1;++j)
if(a[j] > a[i] && L[j] > L[jmax])jmax = j;
L[i] = L[jmax] + 1;
T[i] = jmax;
}
}
void Result()
{
int i = T[0];
while ( i!= n+1)
{
std::cout<< " "<<"a[ "<<i<<" ] = "<<a[i]<<std::endl;
i = T[i];
}
}
int main()
{
Enter();
Optimize();
Result();
std::cout<<std::endl;
return 0;
}
1.1. Cải tiến:
Khi bắt đầu một lần lặp với một giá trị i, ta biết được:
+ m : Độ dài dãy con đơn điệu tăng dài nhất của dãy a[i+1…n+1]
+StartOf[k] ( 1<= k <= m): Phần tử a[StartOf[k]] là phần tử lớn nhất trong số các phần tử trong đoạn a[i+1….n+1] thỏa mãn: dãy on đơn điệu tăng dài nhất bắt đầu từ a[StartOf[k]] có độ dài k. Do thứ tự tính toán được áp đặt như trong sơ đồ trên, ta dễ dàng nhận thấy rằng:
a[StarOf[k]] < a[StartOf[k-1]] < ….. < a[StartOf[1]].
Điều kiện để dãy con đơn điệu tăng độ dài p + 1 bắt đầu tại a[i] chính là a[StartOf[p]] > a[i] ( vì theo thứ tự tính toán thì khi bắt đầu một lần lặp với giá trị i , a[StartOf[p]] luôn đứng sau a[i]).
Mặt khác nếu đem a[i] ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại a[StartOf[p]] mà thu được dãy tăng thì đem a[i] ghép vào đầu dãy con đơn điệu tăng dài nhất bắt đầu tại a[StartOf[p-1]] ta cũng thu được dãy tăng.
Vậy để tính L[i], ta có thể tìm số p lớn nhất thỏa mãn a[StartOf[p]] > a[i] bằng thuật toán tìm kiếm nhị phân rồi đặt L[i] := p + 1 ( và sau đó T[i] := StrtOf[p], tất nhiên).
//Cai tien thuat toan DAY CON DON DIEU DAI NHAT
procedure Init;
begin
a[0] := Low(Integer);
a[n+1] := High(Integer);
m := 1;
L[n+1] := 1;
StartOf[1] := n+1;
end;
{ Ham Find tim vi tri j ma neu dem a[i] ghep vao dau dau con don dieu }
{ tang dai nhat bat dau tu a[j] se nhan duoc day con don dieu tang dai }
{ nhat bat dau tu a[i] }
function Find ( i: Integer) : Integer;
var
inf,sup, median,j: Integer;
begin
inf := 1; sup := m+1;
repeat { Thuat toan tim kiem nhi phan }
median := (inf + sup) div 2;
j := StarOf[median];
if a[j] > a[i] then inf := median; { Luon de a[StartOf[inf]] > a[i] >= a[StarOf[suf]] }
else sup := median;
until inf + 1 = suf;
Find := StartOf[inf];
end;
procedure Optimize;
var
i,j,k: Integer;
begin
for i:= n downto 0 do
begin
j := Find(i);
k := L[j] +1;
if k>m then
begin
m:= k;
StartOf[k] := i;
end;
else
if a[StartOf[k]] < a[i] then
StarOf[k] := i;
L[i] := k;
T[i] := j;
end;
end;
#include<iostream>
#define MAX 100000
int a[MAX+2],L[MAX+2],StartOf[MAX + 2],T[MAX+2];
int n,m;
void Enter()
{
std::cin>>n;
for( int i =1;i<= n;++i)
std::cin>>a[i];
}
void Init()
{
a[0] = -36767;
a[n+1] = 36767;
m = 1;
L[n+1] =1;
StartOf[1] = n+1;
}
int Find(int i)
{
int inf,sup, median,j;
inf = 1; sup = m+1;
while(sup - inf !=1 )
{
median = (inf + sup)>>1;
j = StartOf[median];
if( a[j] > a[i]) inf = median;
else sup = median;
}
return StartOf[inf];
}
void Optimize()
{
int i,j,k;
for( i =n;i>= 0;--i)
{
j = Find(i);
k = L[j] +1;
if( k>m)
{
m = k;
StartOf[k] = i;
}
else if( a[StartOf[k]] < a[i])
StartOf[k] = i;
L[i] = k;
T[i] = j;
}
}
void Result()
{
std::cout<< m -2<<std::endl;
int i =T[0];
while(i != n +1)
{
std::cout<< " "<<a[i];
i = T[i];
}
}
int main()
{
Enter();
Init();
Optimize();
Result();
system("pause");
return 0;
}
.png)
.png)
.png)
0 comments:
Post a Comment