TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
---------------------------------------

BÁO CÁO MƠN TRÍ TUỆ NHÂN TẠO
CHỦ ĐỀ NGHIÊN CỨU: BÀI TOÁN NGƯỜI ĐƯA THƯ
Giáo viên hướng dẫn: giảng viên: Lê Thị Thủy
Lớp: KTPM01
Nhóm:

Khóa: K14

Nhóm 14

Thành viên nhóm:
-

Bùi Khơi Ngun_2019601721

-

Nguyễn Anh Tú_2019601375

-

Phạm Thảo Vân_2019600918

Hà Nội, năm 2022


MỤC LỤC

MỤC LỤC.............................................................................................................2
LỜI MỞ ĐẦU.......................................................................................................3
Chương I: Giới thiệu đề tài.................................................................................4
1. Khái niệm thuật toán Heuristic..................................................................4
2. Khái niệm về nguyên lý tham lam..............................................................4
3. Mơ tả bài tốn người đưa thư.....................................................................5
a) Lý do chọn bài toán.................................................................................5
b) Phát biểu bài toán....................................................................................5
c) Cách giải bài tốn.....................................................................................6
d) Vẽ khơng gian trạng thái của bài tốn...................................................6
e) Thuật toán.................................................................................................7
Chương II: Kết quả nghiên cứu..........................................................................9
1. Yêu cầu bài toán...........................................................................................9
2. Cài đặt thuật toán........................................................................................9
3. Kết quả........................................................................................................14
4. Đánh giá thuật toán....................................................................................16
TÀI LIỆU THAM KHẢO.................................................................................17

2


LỜI MỞ ĐẦU
Ngày nay cùng với sự phát triển về khoa học và kỹ thuật là sự phát triển mạnh mẽ của
nền cơng nghệ thơng tin. Trong q trình cơng nghiệp hóa và hiện đại hóa đất nước
thì cơng nghệ thơng tin là khơng thể thiếu. Cùng với nó là sự ra đời của các ngành
khoa học phục vụ cho lợi ích và nhu cầu của con người. Với quá trình phát triển của
khoa học kỹ thuật và cơng nghệ thì ngành cơng nghệ thơng tin đóng vai trị quan
trọng trong việc giải quyết các vấn đề khó khăn trong cơng việc như: kế tốn, quản lý
nhân sự, điều khiển tự động hóa, …

Trên thế giới cũng như ở Việt Nam, công nghệ thông tin đã trở thành một ngày cơng
nghiệp mũi nhọn, nó là một ngày khoa học kỹ thuật không thể thiếu trong việc áp dụng
vào các hoạt động xã hội và khoa học. Nền công nghiệp hiện nay mang tính chất tự
động hóa cao kèm theo đó là sự địi hỏi về việc ứng dụng cơng nghệ thơng tin cho lĩnh
vực này. Vậy để có thể đáp ứng tốt những yêu cầu của ngày càng cao hơn trong lĩnh
vực tự động hóa người ta đã tiến hành lập trình cho những cỗ máy, những người máy
có thể tư duy như con người nhằm giảm bớt các gánh nặng cơng việc.
Việc ứng dụng trí tuệ nhân tạo đã tạo ra một cuộc cách mạng lớn trong việc tìm hiểu
và chinh phục những điều mà con người không dám mơ tới. Đó là những robot thơng
minh, những cỗ máy thơng minh có thể thay thế con người làm việc trong những môi
trường khắc nghiệt hay chinh phục không gian bao la. Và bên cạnh đó là việc ứng dụng
những thành tựu đó vào lĩnh vực giải trí của con người. Đó là những con vật robot,
những trị chơi. Đó là những ứng dụng lớn lao của trí tuệ nhân tạo vào của sống của
con người.
Trong bài tập lớn này chúng em tìm hiểu thuật tốn tham lam áp dụng cho bài tốn
người đưa thư. Đây là một chương trình nhỏ có thể nó chưa được hồn thiện nhưng
quan trọng hơn đó là giúp mọi người hiểu được vai trị của việc ứng dụng trí tuệ nhân
tạo trong cuộc sống. Mặc dù rất cố gắng để hồn thành cơng việc, xong thời gian có
hạn và kiến thức cịn thiếu nên nếu có sai sót chúng em mong các thầy cơ bỏ qua cho
chúng em ạ!
Chúng em xin cảm ơn!

3


Chương I: Giới thiệu đề tài
1. Khái niệm thuật toán Heuristic
- Heuristic là nhưng tri thức rút ra từ những kinh nghiệm, trực giác của con
người
- Heuristic có thể đúng hoặc sai

- Heuristic thường được sử dụng trong trường hợp:
▪ Vấn đề có thể khơng có nghiệm chính xác do các mệnh đề không phát biểu chặt
chẽ hay thiếu dữ liệu để khẳng định kết quả.
▪ Vấn đề có nghiệm chính xác nhưng chi phí tính tốn để tìm nghiệm quá lớn
(bùng nổ tổ hợp)
- Heuristic là mở rộng khái niệm thuật tốn và có đặc điểm:
▪ Thường tìm lời giải tốt nhưng khơng tốt nhất
▪ Nhanh chóng tìm ra kết quả hơn so với thuật tốn vì vậy chi phí thấp hơn.
▪ Thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con
người
- Heuristic dựa trên 2 nguyên lý cơ bản:
▪ Nguyên lý vét cạn thông minh
▪ Nguyên lý tham lam
2. Khái niệm về nguyên lý tham lam
Lấy tiêu chuẩn tối ưu trên phạm vi tồn cục của bài tốn để làm tiêu chuẩn lựa
chọn hành động cho phạm vi cục bộ của từng bước trong quá trình tìm kiếm lời
giải.

4


3. Mơ tả bài tốn người đưa thư
a) Lý do chọn bài toán
- Bài toán “Người đưa thư” là một bài tốn hay, thực tế, nó được áp dụng rất lớn
trong thực tế để giải quyết các vấn đề phức tạp trong cuộc sống, chẳng hạn như
“Tìm kiếm lộ trình thu gom rác tối ưu trên địa bàn TP Hà Nội”,.....
b) Phát biểu bài toán
Bài toán: Người đưa thư phải đi đưa qua 5 thành phố, để 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.

Chuyển bài tốn về dạng tốn đồ thị.
Bài tố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, trừ
đỉnh ban đầu các đỉnh còn lại chỉ được đi qua một lần duy nhất. Theo kinh
nghiệm của con người trong thực tế thì khi ta đi trên những đoạn đường ngắn
nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất  sử dụng nguyên lý tham
lam.

5


c) Cách giải bài toán
- Xuất phát từ đỉnh 1 thì ta thấy trọng số từ đỉnh 1 tới tất cả các đỉnh còn lại là
Đỉnh

Trọng số

2

1

3

2

4

7

5


5

=> Ta thấy trọng số (đường đi) từ đỉnh 1 đến đỉnh 2 là nhỏ nhất => ta chọn
đường đi 1 -> 2
- Tiếp theo ta chọn đường đi từ đỉnh 2 cho đến các đỉnh còn lại (trừ đỉnh gốc)
Đỉnh

Trọng số

3

4

4

4

5

3

=> Ta thấy trọng số (đường đi) từ đỉnh 2 đến đỉnh 5 là nhỏ nhất => ta chọn
đường đi 2 -> 5
- Tiếp theo, chọn đường đi từ đỉnh 5 đến 2 đỉnh còn lại
Đỉnh

Trọng số

3


2

4

3

=> Ta thấy trọng số (đường đi) từ đỉnh 5 đến đỉnh 3 là nhỏ nhất => ta chọn
đường đi 5 -> 3
- Đường đi còn lại là 3 -> 4 -> 1
- Vậy ta có đường đi là 1 -> 2 -> 5 -> 3 -> 4 -> 1 và tổng đường đi là 14
d) Vẽ khơng gian trạng thái của bài tốn
- Trạng thái đầu: {1}
6


- Trạng thái cuối: {1}

e) Thuật toán
Bước 1: //Khởi đầu
a. Đặt Tour = {};
b. Cost = 0;
c. V = U; //V là đỉnh hiện tại đang thăm
Bước 2: //Thăm tất cả các thành phố
a. for (k=1; k<=n; k++)
b.qua bước 3
Bước 3: //Chọn cung kế tiếp
a. Đặt (V, W) là cung có chi phí nhỏ nhất từ V đến các đỉnh W chưa
đến;
b. Tour = Tour  {(V, W)};

c. Cost = Cost(V, W);
d. Đỉnh W được gán nhãn đã đến
e. Đặt V = W //Gán để xét bước kế tiếp
7


Bước 4: //Hoàn thành
a. Tour = Tour  {(V,U)}
b. Cost = Cost(V, U)
1. U = 1
2. Tour = {}
a. Cost = 0
b. V = 1
c. W  {2, 3, 4, 5} d. W = 2 //vì qua 2 có chi phí nhỏ nhất
3. Tour = Tour  {(1,2)} = {(1,2)}
e. Cost = Cost + Cost(1,2) = 0+1 = 1
f. V = 2
g. W  {3, 4, 5} -> W = 5
4. Tour = Tour  {(2,5)} = {(1,2),(2,5)}
e. Cost = Cost + Cost(2,5) = 1+3 = 4
f. V = 5
g. W  {3, 4} -> W = 3
5. Tour = Tour  {(5,3)} = {(1,2),(2,5),(5,3)}
e. Cost = Cost + Cost(5,3) = 4+2 = 6
f. V = 3
g. W  {4} -> W = 4
6. Tour = Tour  {(3,4)} = {(1,2),(2,5),(5,3),(3,4)}
e. Cost = Cost + Cost(3,4) = 6+1 = 7
f. V = 4
g. W  {4} -> W = 4

7. Tour = Tour  {(4,1)} = {(1,2),(2,5),(5,3),(3,4),(4,1)}
e. Cost = Cost + Cost(4,1) = 7+7 = 14 8.
8


8. Kết thúc
Kết quả: 1 – 2 – 5 – 3 – 4 – 1

Chương II: Kết quả nghiên cứu
1. Yêu cầu bài toán
- Ta chuyển đồ thị về dạng ma trận sau:
- Chương trình được viết trong mơi trường devC++
- Input: ma trận như hình bên
- Output: đường đi của thuật giải Heuristic, và chi phí của đường đi đó
2. Cài đặt thuật tốn
Bước 1: Khởi tạo
- Các giá trị cần khởi tạo:
+ n: số đỉnh của đồ thị
+ graph: mảng 2 chiều lưu trữ đồ thị
+ tourList: mảng 1 chiều lưu trữ đường đi theo giải thuật Heuristic
+ costList: mảng 1 chiều lưu trữ chi phí đường đi của giải thuật
+ u: Đỉnh đầu tiên xuất phát

- Để khởi tạo mảng graph để lưu trữ đồ thị, ta có thể chọn một trong hai cách
sau:
+ Cách 1: Sử dụng file lưu trữ đồ thị đã được chuẩn bị trước

9



+ Cách 2: Tự nhập đồ thị khi chạy chương trình

Bước 2: Tạo các hàm cần thiết
- Hàm checkDinh (int n, int *tourList, int x): Kiểm tra đỉnh đang duyệt có trùng
với đỉnh đã duyệt trên ma trận khơng.
+) n: số đỉnh của đồ thị
+) tourList: lưu trữ đường đi theo giải thuật Heuristic
+) x: đỉnh cần kiểm tra
10


- Hàm timCanhMin (int **g, int n, int v, int *tourList, int &minDinh, int
&minCost): Hàm tìm đỉnh kế tiếp theo thuật giải Heuristic (tìm đường đi tối ưu
nhất)
+ graph: mảng 2 chiều lưu trữ đồ thị
+ n: số đỉnh của đồ thị
+ v: đỉnh hiện tại đang xét
+ tourList: lưu trữ đường đi theo giải thuật Heuristic
+ minDinh: trả về kết quả là đỉnh tiếp theo mà từ đỉnh đang xét đến đỉnh này có
chi phí đường đi ít nhất
+ minCost: trả về kết quả là chi phí ít nhất từ đỉnh đang xét đến đỉnh tiếp theo

11


- Hàm greedy_algorithm (int **g, int n, int u, int *tourList, int *costList): Hàm
thực hiện thuật toán
+ graph: mảng 2 chiều lưu trữ đồ thị
+ n: số đỉnh của đồ thị
+ u: đỉnh bắt đầu

+ tourList: mảng 1 chiều lưu trữ đường đi theo giải thuật Heuristic
+ costList: mảng 1 chiều lưu trữ chi phí đường đi của giải thuật

12


13


3. Kết quả

14


15


4. Đánh giá thuật toán
- Ưu điểm: Thuật giải Heuristic cho bài tốn người đưa thư có độ phức tạp
O(n2) tốt hơn rất nhiều so với thuật toán tối ưu (có độ phức tạp O(n!)).
- Nhược điểm: thuật giải có những hạn chế, chưa cho ra lời giải chính xác.
- Kết luận: Thuật giải Heuristic cho bài toán người đưa thư tuy chưa đưa ra được
lời giải chính xác cho bài tốn, nhưng nó cho ra một lời giải có thể chấp nhận
được với độ phức tạp thấp hơn nhiều so với thuật toán tối ưu.

16


TÀI LIỆU THAM KHẢO
1. ThS.Trần Hùng Cường; ThS.Nguyễn Phương Nga - Giáo trình Trí Tuệ Nhân

Tạo – Trường Đại học Cơng nghiệp Hà Nội
2. Trần Hùng Cường_Giáo trình – slide TRÍ TUỆ NHÂN TẠO (Artificial
Intellegence – AI) 
3. Geogre F. Luger, William A. Stubblefield – Albuquerque – Artifical
Intelligence – Wesley Pubblishing Conpany, Inc – 1997 (Chapter 1) 
4. Bùi Xuân Toại – Trương Gia Việt (Biên dịch) – Trí tuệ nhân tạo – Các cấu
trúc và chiện lược giải quyết vấn đề - NXB Thống kê, 2000 (Phần 1)

17