So sánh thời gian thực hiện của thuật toán Tham lam và thuật toán Quy hoạch động

Bài toán: Bố trí phòng họp (mất tính thứ tự so với dãy ban đầu)

Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất.

Hướng dẫn bằng Quy hoạch động: Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (bi). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j<i và bj<=ai. Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên. Độ phức tạp thời gian O(n^2).

Thuật toán Tham lam:

–   Ý tưởng: Kết thúc sớm thì lựa chọn trước.

–   Thuật toán greedy:  Sắp xếp các cuộc họp theo thứ tự không giảm của thời điển kết thúc. Bắt đầu từ tập S là tập rỗng, ta lần lượt bổ sung các cuộc họp theo thứ tự đã sắp xếp vào S nếu nó không bị trùng với bất cứ cuộc họp nào trong S.

Độ phức tạp thời gian O(nlogn).

Người ta đã chứng minh được rằng thuật toán Tham lam trên đưa ra lời giải tối ưu. Như vậy, cùng một mục đích là tìm ra lời giải tối ưu, thuật toán Tham lam chạy còn nhanh hơn cả thuật toán Quy hoạch động.

Giải thích: Tham lam là kỹ thuật tìm kiếm dựa vào tri thức (nhiều giáo trình còn được biết đến với cái tên: Tìm kiếm kinh nghiệm). Còn thuật toán Quy hoạch động được dùng trong trường hợp này vẫn chỉ là Tìm kiếm mù.

Cái khó của thuật toán Tham lam là: Sau khi bạn xây dựng thuật toán. Bạn phải chứng minh thuật toán bạn xây dựng hoạt động đúng. Đôi khi điều này là rất khó.

Sau đây là code chương trình của thuật toán Tham lam.

const 
	finp	=	'SELECT.INP';
	fout	=	'SELECT.OUT';
	maxn	=	200;
type	
int		=	integer;
arrPoint	=	array[1..maxn] of int;
var
	a, b, C, S	:	arrPoint;
	n, m		: 	int;

procedure 	readInput;
var 	f	: text;  i : int;
begin
  assign(f, finp); reset(f);
  readln(f, n);
  for i := 1 to n do readln(f, a[i], b[i]);
  close(f);
end;

procedure 	writeOutput;
var 	f	: text;  i : int;
begin
  assign(f, fout); rewrite(f);
  writeln(f, m);
  for i := 1 to m do
     writeln(f, a[s[i]], '  ', b[s[i]]);
  close(f);
end;

procedure swap(var x, y : int);
var 	tg : int;
begin
   tg := x;   x := y; y := tg;
end;

procedure sapxep;
var 	i,j : int;
begin
          for i :=1 to n do C[i] := i;
	for i:=2 to n do
	for j:=n downto i do
	if b[j] < b[j-1] then
	begin
		swap(b[j], b[j-1]);
                swap(a[j], a[j-1]);
                swap(C[j], C[j-1]);
	end;
end;

procedure Greedy;
var  i : int;
begin
   {Da co C duoc sap xep tang dan theo dau mut phai}
    m := 0;  {Khoi tao nghiem bang rong}
    for i:= 1 to n do
    if (i=1) or ( (i>1) and (a[i] > b[s[m]])) then
    begin
      m := m + 1;
      s[m] := c[i];
    end;
end;

Begin
    readInput;
    Sapxep;
    Greedy; 
    writeOutput;
End.
Advertisements

One Response to “So sánh thời gian thực hiện của thuật toán Tham lam và thuật toán Quy hoạch động”

  1. panda Says:

    bạn ơi viết bằng ngôn ngữ c được ko


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: