BÀI THU HOẠCH MÔN PHƯƠNG PHÁP
NGHIÊN CỨU KHOA HỌC TRONG TIN
HỌC

Đề tài : “Tìm hiểu về thuật toán Heuristic và
ứng dụng trong việc giải quyết một số bài toán”
Bùi Duy Linh – CHK7
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
MỤC LỤC
MỤC LỤC 2
LỜI MỞ ĐẦU
Đối với nhiều bài toán, hoặc không có lời giải, hoặc độ phức tạp tính toán là
hàm mũ, hoặc là bài toán NP-đầy đủ…, có nghĩa là nó không có lời giải khả thi,
thì thông thường thay vì tìm lời giải tối ưu cho chúng, chúng ta cố gắng tìm lời
giải có thể chấp nhận được, đáp ứng được yêu cầu của thực tế. Các lời giải này
chính là các thuật toán Heuristic.
Các thuật toán tìm kiếm luôn luôn đóng vai trò quan trọng trong việc giải
các bài toán tin học. Các thuật toán loại này rất phong phú, có thể kể đến như: vét
cạn, đệ quy quay lui, nhánh cận, nhị phân…Tuy nhiên, khi gặp những bài toán có
không gian tìm kiếm lớn (đặc biệt trong các trò chơi cờ) thì các thuật toán tìm
kiếm thông thường không cho kết quả hoặc kết quả không tối ưu (do những hạn
chế về thời gian và bộ nhớ). Một hướng tiếp cận độc đáo có thể đáp ứng được đòi
hỏi cho nhiều bài toán loại này là dùng thuật toán Heuristic.
Để hiểu rõ hơn về thuật toán này, em đã có bài “Tìm hiểu về thuật toán
Heuristic”. Trong quá trình làm bài không tránh khỏi sự thiếu xót, em rất mong
được sự góp ý của thầy giáo và các bạn.
2 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
I – Khái quát về thuật toán Heuristic

ứng nổi. Do vậy, thủ tục duyệt toàn thể không thể chấp nhận được. Trong phần lớn
các bài toán chứng minh định lý sử dụng logic, số khả năng cần phải xét trở lên vô
hạn. Việc lựa chọn một nước đi tốt nhất trong trò chơi đòi hỏi phải tìm kiếm trong
khoảng 10
40
khả năng khác nhau, thậm chí đối với chơi cờ, số khả năng cỡ 10
120
.
Một cách xử lý tốt trong những trường hợp này là sử dụng thao tác rút gọn các
hướng tìm kiếm.
Vấn đề quan trọng là ở chỗ, chúng ta biết khai thác khéo léo thông tin tại
mỗi trạng thái để tìm ra thứ tự ưu tiên và đẩy nhanh quá trình tìm kiếm. Thông
thường ta gắn với mỗi trạng thái của bài toán với một số đo (một hàm đánh giá)
nào đó để đánh giá mức độ gần đích của nó.
Một kỹ thuật Heuristic được coi là hợp lý khi nó cho phép tiến hành đánh
giá các khả năng để làm rõ khả năng nào tốt hơn các khả năng còn lại. Những ví
dụ điển hình về các hàm đánh giá là các ước lượng khoảng cách đường chim bay
từ một đỉnh nào tới đỉnh đích trong bài toán xác định đường đi ngắn nhất, hay các
đánh giá ước lượng mức độ quan trọng của các quân cờ trong mỗi thế cờ dựa trên
tổ hợp các trọng số của chúng…
4 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
II - Ứng dụng thuật toán Heuristic vào giải quyết một số bài toán
1- Bài toán người đưa thư
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 điểm cần phát thư rồi trở về vị trí ban đầu với đường đi
ngắn nhất. Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số
dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban
đầu.

+ G: dùng đ trể ỏ tới các giá trị của ma trận.
+ v[Gr.n + 1]: dùng đ lể ưu trữ đ ng đi theo thuườ ật giải Heuristic.
+ Gr.G[ i][j ]: đ thồ ị dưới dạng ma trận.
+ x: là đ nh đ u tiên xuỉ ầ ất phát.
+ initGraph(Graph &Gr): Hàm dùng đ khể ởi tạo một đ thồ ị mới từ cấu trúc đã tổ
chức.
6 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
+ ReadGraph(Graph &Gr): dùng đ đ c đ thể ọ ồ ị từ file .txt
+ inputHandle( Graph &Gr): dùng đ nhể ập đ thồ ị bằng tay.
+ outputGraph(Graph Gr): dùng đ xuể ất đ thồ ị đã đ c nhượ ập ra màn hình.
+ testGraph(int a, int* v, Graph Gr): Kiểm tra điểm đang duyệt có trùng với điểm
đã duyệt trên ma trận không. Đ c gượ ọi trong hàm topNear(…).
+ topNear(int a, Graph Gr, int* v) : Hàm tìm đ nh kỉ ế tiếp theo thuật giải
Heuristic. Đ c gượ ọi lại trong hàm FindWay(…) .
7 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
+ FindWay(int x, Graph Gr, int* v): Hàm tìm đ ng đi theo giườ ải thuật Heuristic.
Dựa theo cách tìm đ ng đi có trườ ọng số nhỏ nhất đ đi bể ước tiếp theo.
- Giao diện chương trình: console Aplication.
Khi thực thi, chương trình sẽ yêu cầu chọn nhập ma trận đ thồ ị bằng tay hay
bằng file “graph.txt”. Ví dụ như hình trên chọn nhập ma trận bằng file txt. Ta
nhập tiếp đ nh bỉ ắt đ u (ầ ở đây nhập 1), thì chương trình sẽ cho ra đáp án cho ví dụ
trên:
Đ ng đi là: 1 – 2 – 5 – 3 – 4 – 1ườ
Chi phí cho đ ng đi này theo giườ ải thuật Heuristic là: 14.
8 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong

sáng tạo ra dạng phẳng của trò chơi này gọi là trò chơi các ô vuông thần bí. Đây là
một bảng gồm 8 ô vuông bằng nhau (xem Hình 1).
Chúng ta xét bảng trong đó mỗi ô vuông có một màu khác nhau. Các màu
được ký hiệu bởi tám số nguyên dương đầu tiên (xem Hình 1). Trạng thái của
bảng được cho bởi dãy ký hiệu màu của các ô được viết lần lượt theo chiều kim
đồng hồ bắt đầu bởi ô ở góc trái trên và kết thúc tại ô ở góc trái dưới. Ví dụ, trạng
thái của bảng trong hình 1 được cho bởi dãy (1, 2, 3, 4, 5, 6, 7, 8). Trạng thái này
10 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học
được gọi là trạng thái khởi đầu (hay trạng thái đích).
Có thể dùng 3 phép biến đổi cơ bản đối với bảng có tên là′A′, ′B′, ′C′:
′A′: đổi chỗ dòng trên và dòng dưới. Ví dụ sau phép biến đổi ′A′thì hình 1
thành:
′B′: thực hiện một phép hoán vị vòng quanh sang phải. Ví dụ sau phép biến
đổi ′B′ thì hình 1 thành:
′C′: quay theo chiều kim đồng hồ bốn ô giữa. Ví dụ sau phép biến đổi ′C′ thì
hình 1 thành:
Biết rằng từ một trạng thái khởi đầu luôn có thể chuyển về một trạng thái bất
kỳ bằng cách dùng các phép biến đổi cơ bản nói trên.
Hãy viết chương trình tìm các phép biến đổi cơ bản để chuyển bảng từ trạng
thái khởi đầu cho trong hình 1 về một trong các trạng thái cho trước (Câu A), bạn
sẽ được thêm hai điểm nếu số lượng phép biến đổi tìm được không vượt quá 300
(Câu B).
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
11 | P a g e
Bùi Duy Linh – CHK7 Phương pháp nghiên cứu khoa học trong
tin học