PHƯƠNG PHÁP NGHIÊN CỨU
KHOA HỌC TRONG TIN HỌC
“Tìm hiểu và ứng dụng giải thuật
Heuristic trong một số bài toán”
HV : Bùi Duy Linh
Lớp : CHK7
1
Thuật ngữ Heuristic xuất phát từ tiếng Hy
Lạp là ″heuriskein″ có nghĩa là ″tìm kiếm″
hoặc ″phát minh″. Chắc chắn chúng ta vẫn
còn nhớ câu chuyện về nhà bác học
Archimedes. Khi phát hiện ra định luật về
trọng lượng riêng, ông đã trần truồng chạy
ra đường và kêu lớn ″tôi tìm ra rồi″. Thực
ra, lúc đó ông đã kêu lên ″heureka″, về sau
này người ta đổi từ này thành ″eureka″. .
I. Giới thiệu về thuật toán Heuristic
2
II.Ứng dụng Heuristic trong một số bài toán
1. Bài toán người đưa thư
1. Mô tả bài toán
2. Cài đặt
3. Kết luận
2. Bài toán tô màu cho đồ thị
1. Mô tả bài toán
2. Cài đặt thuật toán
3
1. Bài toán người đưa thư
1. Giới thiệu :
Bài toán: Để tiết kiệm thời gian đi đưa thư trong một
địa phương. Người đưa thư phải đi qua tất cả các

8
Cài đặt thuật toán
Có thể thấy rằng bài toán tô màu này sao cho số màu
được dùng là ít nhất là một bài toán NP-đầy đủ.
Lúc này, ta tìm một lời giải tốt có thể chấp nhận
được theo một thuật toán heuristic như sau:
Ban đầu chọn một màu và một đỉnh xuất phát. Ta tô
màu đỉnh này và tất cả các đỉnh khác có thể tô
được mà vẫn thoả mãn điều kiện của bài toán.
Chúng ta chọn màu mới và một đỉnh xuất phát mới
(chưa được tô), ta tô đỉnh này và tất cả các đỉnh
khác (còn chưa được tô) có thể tô được bằng màu
thứ hai, và cứ như vậy…cho đến khi tô hết các đỉnh
của G thì thôi
9
Cài đặt thuật toán
Dữ liệu vào
: file INPUT.TXT chứa 8 số nguyên dương
trong dòng đầu tiên mô tả trạng thái đích.
Dữ liệu ra
: trong dòng đầu tiên của file
OUTPUT.TXT chứa một số L là số lượng phép biến
đổi của dãy các phép biến đổi tìm được. Trong L
dòng tiếp theo phải ghi dãy tên các phép biến đổi
cơ bản theo trình tự thực hiện, mỗi tên ghi ở vị trí
đầu tiên của mỗi dòng
10
Kết luận
Thuật toán Heuristic tuy có nhiều điểm mạnh nổi
bật, nhưng trong một vài lĩnh vực nghiên cứu nào