Viện Công nghệ thông tin và truyền thông
Đại Học Bách Khoa Hà Nội
Bài Tập Lớn
Lập lịch giảng dạy trong trường học
Môn học: Trí tuệ nhân tạo
Giáo viên hướng dẫn: Phạm Văn Hải
Nhóm sinh viên thực hiện: Nhóm 11
Nguyễn Quang Quân MSSV: 20102043
Phạm Hoàng Đạt MSSV: 20101358
Phạm Công Hiếu MSSV: 20101523
Đặng Văn Long MSSV: 20101793
Lê Văn Thọ MSSV: 20102256
Hà Nội 8/2013
1
MỤC LỤC
MỤC LỤC…………………………………………………………………… 2
Lời mở đầu…………………………………………………………………… 3
I. Đặt vấn đề……………………………………………………………………4
II. Mô tả bài toán lập thời khóa biểu…………………………………………4
a. Các thông tin của bài toán………………………………………… 4
b. Các rang buộc của bài toán………………………………………….5
III. Mô hình bài toán………………………………………………………….5
IV. Thiết kế thuật giải…………………………………………………………7
V. Chương trình demo………………………………………………………10
VI. Vấn đề…………………………………………………………………….11
Tài liệu tham khảo……………………………………………………………12
2
Lời mở đầu
Bất kỳ trường học nào cũng cần thiết phải lập ra một thời khóa biểu
giảng dạy cho các thầy cô lên lớp, để làm sao phải phù hợp với chương trình
đào tạo mà chính phủ, bộ giáo dục đã đề ra cũng như với chuyên môn của mối

không được xét đến trong chương trình này.
4
II. Mô tả bài toán lập thời khóa biểu.
a. Các thông tin của bài toán.
• Danh sách giáo viên gồm: mã số, tên, số giờ dạy tối đa.
• Danh sách các phòng học gồm: mã phòng, tên phòng.
• Danh sách các môn học: mã môn học, tên môn học, số tiết trong tuần.
b. Các ràng buộc của bài toán.
o Ràng buộc về ngày học: Một tuần có 5 ngày đi học quy định từ
thứ 2 đến thứ 6. Thứ 7 và chủ nhật là ngày nghỉ cho nên
chương trình không xếp lịch học vào các ngày thứ 7 và chủ nhật.
o Ràng buộc về giáo viên: Lịch giảng dạy của mỗi giáo viên không
bị chồng chéo lên nhau. Tức là tại một thời điểm, giáo viên chỉ
đảm nhiệm giảng dạy một lớp học.
o Ràng buộc về số tiết tối đa trong tuần của giáo viên: Số tiết dạy
của giáo viên không được vượt quá số tiết tối đa trong tuần của
giáo viên đó.
o Ràng buộc về số tiết/buổi: Số tiết học trong một buổi không quá
6 tiết/buổi.
o Ràng buộc về lớp học: Mỗi phòng học tại một thời điểm chỉ có
một lớp học.
Mục tiêu:
Tìm ra được một thời khóa biểu phù hợp, thỏa mãn tất cả các rang
buộc đã nêu ở trên.
5
III. Mô hình bài toán.
- Các chỉ số:
g: chỉ số giáo viên.
t: chỉ số ngày
p: chỉ số phòng

dem < gvtd[teacher[i]]
+ Ràng buộc về số tiết/buổi: Số tiết học trong một buổi không quá 6
tiết/buổi.
hour[i] + duration[i]) > 6
+ Ràng buộc về lớp học: Mỗi phòng học tại một thời điểm chỉ có một lớp
học.
((room[i] == room[j]) && (day[i] == day[j])) && (((hour[j]+duration[j])
> hour[i]) || ( hour[i] + duration[i]) > hour[j]))
IV. Thiết kế thuật giải
1. Thuật toán quay lui (backtracking)
Giải thuật tìm kiếm quay lui (backtracking)
- Gán giá trị lần lượt cho các biến – việc gán giá trị của biến này chỉ
được làm sau khi hoàn thành gán giá trị cho biến khác.
- Sau mỗi phép gán kiểm tra các ràng buộc có được thoả mãn bởi tất cả
các biến đã được gán giá trị cho tới thời điểm hiện tại – Quay lui nếu
có lỗi (không thoả mãn ràng buộc).
Nhược điểm của thuật toán quay lui:
7
- Lặp đi lặp lại lỗi: Bỏ qua các lý do của mâu thuẫn
- Lặp lại các kiểm tra ràng buộc không cần thiết
- Phát hiện muộn các mâu thuẫn (vi phạm ràng buộc)
Ưu tiên biến:
Việc ưu tiên biến nhằm cải thiện hiệu quả của thuật toán
- duration vì liên quan đến nhiều ràng buộc nhất
- day và teacher
- room
Code (java):
- Hàm chính
public void XepLich(int i){ //i là số thứ tự môn đang xét
if(i == Tmon){

if((t == day[j])&&((hour[j]+duration[j])>bd)&&(g==teacher[j])) {
return false;
}
//Ràng buộc về lớp học
if(((p == room[j])&&(t == day[j]))&&((hour[j]+duration[j])>bd)) {
return false;
}
if(g==teacher[j]){
dem = dem+duration[j];
}
}
if(dem>gvtd[g]){
//Ràng buộc về số tiết tối đa trong tuần của giáo viên
return false;
}
return true;
}
Cây lời giải:
9
2. Thuật toán kiểm tra tiến (Forward Checking)
Thuật toán kiểm tra tiến (Forward Checking):
Mục đích của thuật toán kiểm tra tiến là để tránh các thất bại bằng
kiểm tra trước các ràng buộc.
Kiểm tra tiến đảm bảo sự phù hợp giữa biến đang được xét gán giá trị
và các biến khác có liên quan (ràng buộc) trực tiếp với nó.
Ý tưởng:
• Ở mỗi bước gán giá trị, theo dõi các giá trị hợp lệ (có thể được
gán) đối với các biến chưa được gán giá trị.
• Loại bỏ (dừng) hướng tìm kiếm hiện tại khi có bất kỳ một biến
(chưa được gán giá trị) nào đó không còn giá trị hợp lệ.

A[t][j][p][g] = false;
for(int k=0;k<Tgv;k++){//Ràng buộc về lớp học
A[t][j][p][k] = false;
}
for(int m=0;m<Tphong;m++){//Ràng buộc về giáo viên
A[t][j][m][g] = false;
}
}
11
day[i] = t;
hour[i] = n;
room[i] = p;
teacher[i] = g;
FC(i+1,A);
break C;
}
}
}
}
}
}
}
- Hàm kiểm tra tiến
boolean CheckForward(int i, boolean A[][][][]) {
int maxD = 0;
for(int j=i+1;j<Tmon;j++){
if(duration[j]>duration[maxD]) maxD = j;
}
//kiem tra voi mon co so tiet trong tuan lon nhat
//neu mon nay con xep dc cho thi cac mon khac cung xep dc

- Xem các môn học, giáo viên, danh sách phòng.
- Chỉnh sửa CSDL
- Thoát chương trình.
13
VI. Vấn đề.
*) Các khó khăn trong quá trình thực hiện:
- Thiết kế, tổ chức chương trình.
- Kết nối đến cơ sở dữ liệu
*) Dự tính ban đầu của nhóm là sử dụng cả thuật toán di truyền để giải bài
toán này nhưng do gặp phải khó khăn nên nhóm đã quyết định sử dụng dừng
lại ở hai thuật toán back tracking và forward checking.
Bên cạnh đó thì chương trình này vẫn chưa phân chia tốt độ ưu tiên
giữa việc thứ tự gán giá trị cho các biến, thứ tự giá trị được gán với mỗi biến.
*) Trong thời gian tới, nhóm sẽ nghiên cứu thêm về việc sử dụng giải thuật di
truyền với nhiều ràng buộc hơn kết hợp với các tri thức bổ sung cụ thể của
bài toán để giải bài toán tối ưu hơn. Bổ sung thêm các chức năng tạo các cơ
sơ dữ liệu về giáo viên, phòng học, lớp học…
Tài liệu tham khảo
14
1. Slide “Trí tuệ nhân tạo” – Phạm Văn Hải, Viện Công nghệ thông tin và
truyền thông, Đại học Bách Khoa Hà Nội
2. On The Forward Checking Algorithm - Fahiem Bacchus and Adam
Grove
3. />15