____________________________________________________

BÀI TẬP LỚP
MÔN: PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN

Học viên: Đỗ Đức Thọ.
Lớp

: Cao học HTTT - K25B.

Tháng 5 năm 2014


Mục lục
LỜI CẢM ƠN.....................................................................................3
1. Nội dung bài toán................................................................................................................4
Có 1 phòng để để chức các cuộc họp. Các cuộc họp được xếp vào lịch nếu khoảng thời gian
làm việc của chúng giao nhau không nhiều hơn thời điểm tiếp nối. Cho 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. Hãy xếp lịch để phục vụ được
nhiều cuộc họp nhất................................................................................................................4
2. Diễn giả bài toán.................................................................................................................4
3. Hướng giải quyết bài toán...................................................................................................4
1.Thuật ngữ.............................................................................................................................5
2.Phương thức tiếp cận............................................................................................................5
3.Các bước để giải bài toán Quy Hoạch Động........................................................................5
1.Mô hình bài toán..................................................................................................................6
2.Xây dựng thuật toán QHĐ để tìm nghiệm tối ưu của bài toán............................................6
3.Đánh giá thuật toán..............................................................................................................9
a.Độ phức tạp dữ liệu..........................................................................................................9
b.Độ phức tạp tính toán.......................................................................................................9
4.Cải tiến thuật toán:...............................................................................................................9

nhiều cuộc họp nhất.

2. Diễn giả bài toán.
Bài toàn bao gồm
Dữ liệu vào: S={[a1, b1],…, [an-1, bn-1], [an, bn]} trong đó :
+n:

Số lượng cuộc họp (n>0).

+ [ai, bi] : Khoảng thời gian diễn ra cuộc họp thứ i (1 ≤ i ≤ n) với:
- ai là thời điểm bắt đầu cuộc họp và
- bi là thời điểm kết thúc cuộc họp.
Dữ liệu ra:
+ Tập hợp Smax= {[ai1, bi1], [ai2, bi2], …, [aimax, bimax]} , 1
-

Đặc điểm :
•

Thường dùng để giải các bài toán tối ưu.

•

Phân rã thành bài toán con, hình thành lời giải từ bài toán con.

•

Lưu trữ lời giải của bài toán con trong một bảng dữ liệu thay cho giải lại các
bài toán con (đệ quy).

2. Phương thức tiếp cận.
Quy hoạch động thường dùng một trong hai cách tiếp cận:
-

Top-down (Từ trên xuống): Bài toán được chia thành các bài toán con, các bài toán
con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại chúng.
Đây là đệ quy và lưu trữ được kết hợp với nhau.

-

Bottom-up (Từ dưới lên): Tất cả các bài toán con có thể cần đến đều được giải trước,
sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. Cách tiếp cận này hơi
tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy nhiên, đôi khi
việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài toán cho trước

•

Nhập bằng file (dữ liệu nhiều cuộc họp).

Phần thực hiện chương trình:
•

Dùng thuật toán sắp xếp để sắp xếp, để sắp xếp dữ liệu cuộc họp đầu vào tăng
dần theo thời gian kết thúc cuộc họp

•
-

Xây dựng thuật toán quy hoạch động để tìm ra nghiệm tối ưu của bài toán.

Phần dữ liệu đầu ra:
•

Hiển thị kết quả trên màn hình.

•

Xuất kết quả ra file.

2. Xây dựng thuật toán QHĐ để tìm nghiệm tối ưu của bài toán.
Hàm mục tiêu: f là số lượng cuộc họp.
- Gọi S là dãy các cuộc họp được bố trí thoả mãn yêu cầu đầu bài. Vì số lượng cuộc họp
trong S chỉ phụ thuộc vào dãy các cuộc họp đã cho ban đầu chính vì vậy bảng phương án
chỉ là một bảng 1 chiều.
- Ta bổ xung vào 2 đầu của dãy S hai cuộc họp thứ 0 ([-maxint, -maxint]) và cuộc họp thứ

jmax:=n+1;
for j:=i+1 to n+1 do
if (a[j]>=b[i]) and (L[j]>L[jmax]) then jmax:=j;
L[i]:=L[jmax]+1;
<Ghi nhận lại vết đã đi qua>;
end;
end;
Bước 3: Lập bảng phương án.
Sử dụng mảng 1 chiều Trace[] để lưu lại dãy các cuộc họp theo nguyên tắc Trace[i]
sẽ cho biết cuộc họp đứng liền sau cuộc họp i trong dãy các cuộc họp dài nhất bắt đầu từ
cuộc họp i.
Bước 4: Tìm nghiệm của bài toán con thông qua nghiệm của bài toán con nhỏ hơn dựa
vào công thức truy hồi tại bước 2.
Bước 5: Xây dựng nghiệm của bài toán thông qua bảng phương án (mảng 1 chiều
Trace[]).
- Tại mỗi bước xây dựng L(i)= L(jmax)+1 với i+1 ≤ jmax ≤ n+1 thì Trace[i]= jmax để
lưu lại rằng cuộc họp Trace[i] đứng ngay sau cuộc họp i.
- Sau khi tính xong dãy L(i) và mảng Trace[] ta bắt đầu tại Trace[0] và kết thúc tại
n+1 nghĩa là dãy chỉ số các cuộc họp sẽ là:
Trace[0] → Trace[Trace[0]]… → n+1.



Quá trình truy vết có thể diễn tả thông qua thủ tục sau:
procedure truyvet;
var i,j,k:integer;
begin
i:=Trace[0];
while (in+1) do
begin


Tóm lại về tổng thể độ phức tạp dữ liệu và độ phức tạp tính để giải quyết bài toán này
là O(n2) và nó đã nhỏ hơn rất nhiều so với độ phức tạp của thuật toán vét cạn.

4. Cải tiến thuật toán:
a. Đổi thuật toán sắp xếp
-

Sử dụng thuật toán sắp xếp nhanh, với độ phức tạp là O(nlogn)

b. Cải tiến thuật toán quy hoạch động tìm nghiệp tối ưu.
-

Với mỗi số k, gọi St[k] là chỉ số x của cuộc họp x thoả mãn:


•

Dãy các cuộc họp dài nhất bắt đầu từ x có độ dài k. Nếu có nhiều cuộc họp
cùng thoả mãn điều kiện này thi ta chọn cuộc họp có a x là phần tử lớn nhất.
Việc tính các giá trị của St[k] được thực hiện đồng thời với việc tính các giá
trị L[?] bằng phương pháp sau:
St[1]:=n+1;
m:=1;
for i:=n downto 0 do
begin
<Tính L(i); đặt k:=L(i)>;
if (k>m) then
begin
m:=k;

a. Sử dung thuật toán ban đầu.
-

-

-

Dữ liệu đầu vào :
Số thứ tự các cuộc họp

Thời điểm bắt đầu

Thời điểm kết thúc

1

9

13

2

8

10

3

9


8

9

7

8

Số thứ tự các cuộc họp

Thời điểm bắt đầu

Thời điểm kết thúc

1

1

2

2

3

5

3

4


13

9

9

15

Sau khi sắp xếp chọn:

Bảng kết quả chương trình:
Tính toán

i

0

1

2

3

4

5

6

7


3

3

2

2

2

1

Trace[i]

1

2

5

5

6

7

7

10


1

9

13

2

8

10

3

9

15

4

4

6

5

4

5


1

1

2

2

3

5

3

4

5

4

4

6

5

5

8

I

0

1

2

3

4

5

6

7

8

9

[ai, bi]

[-M,-M]

[1,2]

[3,5]


Trace[i]

1

4

6

6

6

9

9

10

10

10

0

St[i]

0

10


Chương trình ( Lập trình bằng ngôn ngữ C)

1. Chương trình ban đầu
a. Mô tả.
-

Đầu vào : Nhập từ bàn phím

-

Chương trình:
•

Thuật toán sắp xếp chọn. Phức tạp O(N2)

•

Thuật toán chưa cải tiến. Phức tạp O(N2)

-

Đầu ra: Hiển thị kết quả trên màn hình

-

File Source : Source.c

b. Code.
#include <stdio.h>
#include <conio.h>

// Phần chương trình
int main(int argc, char* argv[])
{
// khai bao bien
int n; // Số n, số cuộc họp
int batdau[1001]; // Mảng lưu thời gian bắt đầu của các cuộc họp
int ketthuc[1001]; // Mảng lưu thời gian kết thúc của các cuộc họp
int L[1001];// Lưu lại số lượng cuộc họp được bố trí vi trí thứ i, i=1,n
int VT[1001]; // Lưu lại vị trí mà L[i] đạt max
int jmax;
int i;// Chỉ số duyệt dùng để duyệt mảng
int j;// Chỉ số duyệt dùng để duyệt mảng
/*------------------ Phần nhập dữ liệu đầu vào ------------------------*/
// Nhập số lượng cuộc họp, nếu số cuộc < 1 và lớn hơn 1000 thì nhập lại
do
{
printf("Nhap so cuoc hop:= ");
scanf("%d",&n);
}
while (n<1|| n>1000);


// Nhập thời gian bắt đầu và thời gian kết thúc của n cuộc họp
for (i=1;i
jmax =j;
}
}
L[i] = L[jmax]+1;
// lưu lại vị trí jmax bằng mảng vị trí
VT[i] = jmax;
}
/*--------------- Phần hiển thị kế quả ra màn hình----------------*/
// Hiển thị số cuộc họp
printf("Do dai Max :=%4d",L[0]-2);
// Hiển thị các cuộc họp được chọn
printf("\nDanh sach cuoc hop can tim la:=");
i = VT[0];
printf("{");
while (i!=n+1)
{
printf(" [%d,%d] ",batdau[i],ketthuc[i]);
i=VT[i];
}
printf("}");
getch();
}


2. Chương trình cải tiến.
a. Mô tả.
-

Đầu vào : File Input.txt ( hoặc Input1.txt kết quả thực nghiệm)


#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hàm hoan vi
// Hàm phụ trợ sắp xếp nhanh.
void quickSort(int *a,int *b, int l, int r)
{
int key = b[(l+r)/2];
int i = l, j = r;
while(i key) j--;

// tim phan tu ben trai ma >=key
// tim phan tu ben trai ma
int VT[1001]; // Lưu lại vị trí mà L[i] đạt max
int ST[1001];
int m;
int i;// Chỉ số duyệt dùng để duyệt mảng
int j;
int k;
/*-------------------- Phần nhập dữ liệu đầu vào -----------------------*/
// Nhập số lượng cuộc họp tu file
n=0;
// fInp = fopen ("Input1.txt", "r");
fInp = fopen ("Input.txt", "r");
while (!feof(fInp)) {
n++;
fscanf(fInp, "%d %d", &batdau[n], &ketthuc[n]);
}
fclose(fInp);
/*---------- Phần thuật toán xử lý chương trình--------------------*/
// Sử dụng hàm phụ trợ xắp xếp nhanh
quickSort(batdau,ketthuc,1,n);
// Khởi tạo
batdau[0] = 0;
ketthuc[0] =0;
batdau[n+1] = 32767; // max của kiểu số nguyên trong C
ketthuc[n+1] = 32767;
// Chương trình
for (i=0;i
printf("Du lieu ket qua duoc ghi ra file, Hay mo file OutPut.txt de xem ket qua");
fOutp = fopen("OutPut.txt","w");
fprintf(fOutp,"Do dai Max :=%4d",L[0]-2);
fprintf(fOutp,"\nDanh sach cuoc hop can tim la:={");
i = VT[0];
while (i!=n+1)
{
fprintf(fOutp," [%d,%d] ",batdau[i],ketthuc[i]);
i=VT[i];
}


fprintf(fOutp,"}");
fclose(fOutp);
// hien thi ket qua ra man hinh
printf("\nDo dai Max :=%4d",L[0]-2);
printf("\nDanh sach cuoc hop can tim la:=");
i = VT[0];
printf("{");
while (i!=n+1)
{
printf(" [%d,%d] ",batdau[i],ketthuc[i]);
i=VT[i];
}
printf("}");
getch();
}


Tài liệu tham khảo