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

BÁO CÁO
THỰC NGHIỆM/THÍ NGHIỆM
Học phần:

TRÍ TUỆ NHÂN TẠO – IT6043
Đề Tài:
XÂY DỰNG CHƯƠNG TRÌNH
GIẢI BÀI TỐN TRỊ CHƠI 8 SỐ VỚI THUẬT TỐN
TÌM KIẾM CHIỀU RỘNG, CHIỀU SÂU (C++)
Lớp: 20221IT6043001
Nhóm 9: Vũ Mạnh Dũng - 2020605565
Vũ Huy Công - 2020605358
Võ Văn Đức – 202060

Giảng viên HD: TS. Trần Thanh Huân

Hà Nội, 11/2022
1


MỤC LỤC
LỜI NĨI ĐẦU................................................................................4
TĨM TẮT BÁO CÁO.......................................................................5
DANH SÁCH CÁC HÌNH VẼ...........................................................6
CÁC TỪ VIẾT TẮT.........................................................................6
MỞ ĐẦU.......................................................................................7
CHƯƠNG 1: TỔNG QUAN.............................................................8
1.1. Giới thiệu về trí tuệ nhân tạo...........................................8

1.1.1. Khái niệm...................................................................8
1.1.2. Vai trị.........................................................................9
1.1.3. Các kĩ thuật cơ bản....................................................9
1.2. Giới thiệu trò chơi 8 số (8 puzzle)...................................11
1.2.1. Giới thiệu bài toán....................................................11
1.2.2. Xác định trạng thái đích...........................................11
1.2.3. Kiểm tra trạng thái đích...........................................14
CHƯƠNG 2: CÁC THUẬT TỐN CHIỀU RỘNG, CHIỀU SÂU.........15
2.1. Thuật tốn tìm kiếm theo chiều rộng (BFS)...................15
2.1.1. Khái niệm.................................................................15
2.1.2. Tư tưởng...................................................................15
2.1.3. Thuật toán................................................................16
2.1.4. Ưu, nhược điểm.......................................................16
2.2. Thuật tốn tìm kiếm theo chiều sâu (DFS).....................17
2


2.2.1. Khái niệm.................................................................17
2.2.2. Tư tưởng...................................................................17
2.2.3. Thuật toán................................................................18
2.2.4. Ưu, nhược điểm.......................................................19
2.3. Sự khác nhau giữa 2 thuật toán.....................................20
CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH......................................21
3.1. Tìm kiếm theo chiều rộng (BFS).....................................22
3.2. Tìm kiếm theo chiều sâu (DFS).......................................27
KẾT LUẬN...................................................................................32
TÀI LIỆU THAM KHẢO.................................................................32
ĐỐI CHIẾU VIỆT – ANH...............................................................32

3



LỜI NĨI ĐẦU
Để hồn thiện được đề tài Bài tập lớn mơn Trí tuệ nhân tạo, chúng em xin gửi
lời cảm ơn chân thành đến trường Đại học Công nghiệp Hà Nội, khoa Công nghệ
thông tin đã tạo điều kiện cho chúng em được học tập. Chúng em xin gửi lời cảm ơn
chân thành đến các thầy cô trong khoa Công nghệ thông tin đã truyền đạt cho chúng
em rất nhiều kiến thức trong quá trình học tập tại trường. Đặc biệt chúng em xin
chân thành cảm ơn đến cô giáo TS. Trần Thanh Huân. Trong suốt quá trình làm
bài tập lớn thầy ln giúp đỡ, hướng dẫn tận tình, truyền đạt kiến thức và kinh
nghiệm của mình để chúng em hoàn thành đề tài này.
Chúng em đã cố gắng hoàn thiện báo cáo bài tập lớn tốt nhất nhưng khơng thể
tránh được những thiếu sót. Chúng em rất mong nhận được sự góp ý của các thầy cơ
và các bạn để báo cáo này của chúng em được hoàn thiện hơn. Chúng em xin chân
thành cảm ơn!

4


TĨM TẮT BÁO CÁO
Chương 1:
Mục đích:
- Tìm hiểu tổng quan về trí tuệ nhân tạo
- Giới thiệu về trị chơi tám số
Kết luận:
- Khái niệm, vai trò, các kĩ thuật cơ bản của TTNT
- Giới thiệu cách chơi trò chơi 8 số, xác định trạng thái đich, cách kiểm
tra trạng thái đích
Chương 2:
Mục đích:

-

Tìm hiểu thuật tốn tìm kiểm theo chiều rộng (BFS)
Tìm hiểu thuật tốn tìm kiếm theo chiều sâu(DFS)

Kết luận: Đưa ra được khái niệm, tư tưởng, thuật toán, ưu nhược điểm và so
sánh giữa 2 thuật toán
Chương 3:
Mục đích: Cài đặt chương trình
Kết luận: Đưa ra được các bước cài đặt chương trình, và chương trình hồn
chỉnh

5


.

DANH SÁCH CÁC HÌNH V
Hình
Hình
Hình
Hình
Hình
Hình
Hình
Hình
Hình
Hình
Hình


1. Các trạng thái đích...............................................................10
2. Giải thuật xác định trạng thái đích.......................................12
3. Giải thuật kiểm tra trạng thái đích.......................................12
4. Thứ tự thăm các đỉnh của BFS..............................................14
5. Thứ tự thăm các đỉnh của DFS..............................................16
6. Ví dụ giải thuật DFS..............................................................17
7. Lớp Node thể hiện các trạng thái của puzzle.......................20
8. Code puzzle theo BFS...........................................................21
9. Chạy trương trình theo BFS..................................................24
10. Code puzzle theo DFS.........................................................26
11. Chạy chương trình theo DFS...............................................29

CÁC TỪ VIẾT TẮT
-

AI: Artificial Intelligence
TTNT: Trí tuệ nhân tạo
BFS: Breadth First Search
DFS: Deep First Search

6


MỞ ĐẦU
Tên đề tài:
“Xây dựng chương trình giải bài tốn trị chơi 8 số với thuật tốn
chiều sâu, chiều rộng (C++)”

Lý do chọn đề tài:
Trong ngành khoa học máy tính, một giải thuật tìm kiếm là một thuật tốn lấy

đầu vào là một bài toán và trả về kết quả là một lời giải cho bài tốn đó, thường là sau
khi cân nhắc giữa một loạt các lời giải có thể. Tập hợp tất cả các lời giải có thể cho bài
tốn được gọi là khơng gian tìm kiếm. Có những thuật tốn tìm kiếm “sơ đẳng” khơng
có thơng tin, đây là những phương pháp đơn giản và trực quan, trong khi đó các thuật
tốn tìm kiếm có thơng tin sử dụng hàm đánh giá heuristic giúp ta giảm đáng kể thời
gian cần thiết cho việc tìm kiếm lời giải.

Mục đích của đề tài:
Trình bày về 2 thuật tốn chúng em tìm hiểu, nêu ra cơ chế và ưu nhược điểm
của mỗi thuật tốn, áp dụng vào thực tế (trị chơi 8 số)

Bốc cục đề tài:
Nội dung đề tài được trình bày trong 3 chương:
Chương 1: Tổng quan
Chương 2: Thuật tốn chiều rộng, chiều sâu
Chương 3: Xây dựng chương trình

7


CHƯƠNG 1: TỔNG QUAN
1.1.

Giới thiệu về trí tuệ nhân tạo

1.1.1.

Khái niệm

Trong khoa học máy tính, trí tuệ nhân tạo hay AI (tiếng anh: Artificial

Intelligence), đơi khi được gọi là trí thơng minh nhân tạo, là trí thơng
minh được thể hiện bằng máy móc, trái ngược với trí thơng minh tự
nhiên của con người. Thơng thường, thuật ngữ "trí tuệ nhân tạo" thường
được sử dụng để mơ tả các máy móc (hoặc máy tính) có khả năng bắt chước
các chức năng "nhận thức" mà con người thường phải liên kết với tâm trí,
như "học tập" và "giải quyết vấn đề".
Trí tuệ nhân tạo là một lĩnh vực nghiên cứu của khoa học máy tính và
khoa học tính tốn nói chung. Có nhiều quan điểm khác nhau về Trí tuệ
nhân tạo. Do đó có nhiều định nghĩa khác nhau về lĩnh vực này. Sau đây là
một số định nghĩa:
- Sự nghiên cứu các năng lực trí tuệ thơng qua việc sử dụng các mơ
hình tính tốn (Charniak và McDormott, 1985).
- Nghệ thuật tạo ra các máy thực hiện các chức năng đòi hỏi sự
thông minh khi được thực hiện bởi con người (Kurweil, 1990).
- Lĩnh vực nghiên cứu tìm cách giải thích và mô phỏng các hành vi
thông minh trong thuật ngữ các q trình tính tốn (Schalkoff,
1990).
- Sự nghiên cứu các tính tốn để có thể nhận thức, lập luận và hành
động (Winston, 1992).
- Một nhánh của khoa học máy tính liên quan đến sự tự động hóa
các hành vi thơng minh (Luger and Stubblefield, 1993).
- TTNT là sự nghiên cứu thiết kế các tác nhân thông minh (Poole,
Mackworth and Goebel, 1998).
Trí tuệ nhân tạo là một nhánh của khoa học và cơng nghệ liên quan đến
việc làm cho máy tính có những năng lực của trí tuệ cong người, tiêu biểu
như các khả năng biết suy nghĩ và lập luận để giải quyết vấn đề, biết giao
tiếp do hiểu ngôn ngữ và tiếng nói, biết học và tự thích nghi,…

8



1.1.2.

Vai trị

Trí tuệ nhân tạo nghiên cứu kỹ thuật làm cho máy tính có thể “suy nghĩ
một cách thơng minh” và mơ phỏng q trình suy nghĩ của con người khi
đưa ra những quyết định, lời giải. Trên cơ sở đó, ta có thể thiết kế các
chương trình cho máy tính để giải quyết bài tốn.
Sự ra đời và phát triển của TTNT đã tạo ra một bước nhảy vọt về chất
trong kỹ thuật và kỹ nghệ xử lý thông tin. Trí tuệ nhân tạo chính là cơ sở của
cơng nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền
thống dựa trên văn bản giấy tờ. Điều này được thể hiện qua các mặt sau:
- Nhờ những cơng cụ hình thức hố (các mơ hinh logic ngôn ngữ,
logic mờ,...), các tri thức thủ tục và tri thức mơ tả có thể biểu diễn
được trong máy. Do vậy q trình giải bài tốn được thực hiện
hiệu quả hơn.
- Mơ hình logic ngơn ngữ đã mở rộng khả năng ứng dụng của máy
tính trong lĩnh vực địi hỏi tri thức chun gia ở trình độ cao, rất
khó như: y học, sinh học, địa lý, tự động hóa.
- Một số phần mềm trí tuệ nhân tạo thể hiện tính thích nghi và tính
mềm dẻo đối với các lớp bài toán thuộc nhiều lĩnh vực khác nhau.
- Khi máy tính được trang bị các phần mềm trí tuệ nhân tạo, việc sử
dụng mạng sẽ cho phép giải quyết những bài toán cỡ lớn và phân
tán.

1.1.3.

Các kĩ thuật cơ bản
Các kỹ thuật Trí tuệ nhân tạo cơ bản bao gồm:

- Lý thuyết giải bài tốn và suy diễn thơng minh: Lý thuyết giải bài
toán cho phép viết các chương trình giải câu đố, các trị chơi
thơng qua các suy luận mang tính người.
- Lý thuyết tìm kiếm may rủi: Lý thuyết này bao gồm các phương
pháp và kỹ thuật tìm kiếm với sự hỗ trợ của thơng tin phụ để giải
bài tốn một cách có hiệu quả.
- Các ngơn ngữ về TTNT: Để xử lý các tri thức người ta khơng chỉ
sử dụng các ngơn ngữ lập trình dùng cho các xử lý dữ liệu số, mà
cần có ngơn ngữ khác. Các ngôn ngữ chuyên dụng này cho phép
lưu trữ và xử lý thông tin ký hiệu. Một số ngôn ngữ được nhiều
người biết đến là LISP, PROLOG,...
- Lý thuyết thể hiện tri thức và hệ chuyên gia: Trí tuệ nhân tạo là
khoa học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, logic
vị từ, Frame,… là các phương pháp biểu diễn tri thức thông dụng.
Việc gắn liền cách thể hiện và sử dụng tri thức là cơ sở hình thành
hệ chuyên gia.

9


-

-

-

Lý thuyết nhận dạng và xử lý tiếng nói: Giai đoạn phát triển đầu
của TTNT gắn với lý thuyết nhận dạng. Ứng dụng của phương
pháp này trong việc nhận dạng chữ viết, âm thanh,…
Người máy: Cuối những năm 70, người máy trong công nghiệp đã

đạt được nhiều tiến bộ. Người máy có bộ phận cảm nhận và các
cơ chế hoạt động được nối ghép theo sự điều khiển thông minh.
Khoa học về cơ học và TTNT được tích hợp trong khoa học người
máy.
Tâm lý học xử lý thông tin : Các kết quả nghiên cứu của tâm lý
học giúp Trí tuệ nhân tạo xây dựng các cơ chế trả lời theo hành vi,
có ý thức; nó giúp cho việc thực hiện các suy diễn mang tính
người.
Ngồi ra, xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui và
xử lý cú pháp hình thức là những kỹ thuật cơ bản của tin học
truyền thống có liên quan trực tiếp đến TTNT.

Các loại cơng nghệ tích hợp AI:
-

-

Tự động hóa
Máy móc
Thị giác máy
Xử lý ngơn ngữ tự nhiên
Robotics
Xe tự lái

10


1.2. Giới thiệu trò chơi 8 số (8 puzzle)
1.2.1.


Giới thiệu bài tốn

Bài tốn 8-puzzle (hay cịn gọi là 8 số) là một bài toán quen thuộc với
những người bắt đầu tiếp cận với mơn Trí tuệ nhân tạo. Bài tốn có nhiều
phiên bản khác nhau dựa theo số ơ, như 8-puzzle, 15-puzzle, ở mức độ đơn
giản nhất, chúng em xem xét dạng bài tốn 8-puzzle.
Bài tồn gồm một bảng ơ vng kích thước 3x3, có tám ơ được đánh số
từ 1 tới 8 và một ô trống. Trạng thái ban đầu, các ô được sắp xếp một cách
ngẫu nhiên, nhiệm vụ của người chơi là tìm cách đưa chúng về đúng thứ tự
như 2 hình dưới:

Hình 1. Các trạng thái đích

Trong q trình giải bài tồn, tại mỗi bước, ta giả định chỉ có ơ trống là
di chuyển, như vậy, tối đa ơ trống có thể có 4 khả năng di chuyển (lên trên,
xuống dưới, sang trái, sang phải).

1.2.2.

Xác định trạng thái đích

Có những trạng thái của bảng số khơng thể chuyển về trạng thái đích 1
mà chỉ chuyển về trạng thái 2 hoặc ngược lại. Người ta chứng minh, để có
thể xác định trạng thái đích, thì ta phải kiểm tra trạng thái đầu bằng cách
như sau:
Ta xét lần lượt từ trên xuống dười, từ trái sang phải, với mỗi ô số đang
xét (giả sử là ô thứ i), ta kiểm tra xem phía sau có bao nhiêu ơ số có giá trị
nhỏ hơn ơ đó.
-


Sau đó ta tính tổng N = n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8. Nếu:
11


+ N mod 2 = 1
⇨ Ta xác định được trạng thái đích 1 như hình dưới
1

2

8
7

3
4

6

5

+ N mod 2 = 0
⇨ Ta xác định được trạng thái đích 2 như hình dưới
1

2

3

4


5

6

7

8

2

1

3

8

5

7

Ví dụ: Cho trạng thái đầu sau:

6

4

12


Xét ơ thứ 1 có giá trị 6: Phía sau có 5 ơ nhỏ hơn (5, 4, 3, 2, 1)


=> n1 = 5

Xét ơ thứ 2 có giá trị 2: Phía sau có 1 ơ nhỏ hơn (1)

=> n2 = 1

Xét ơ thứ 3 có giá trị 1: Phía sau khơng cịn ơ nào nhỏ hơn

=> n3 = 0

Xét ơ thứ 5 có giá trị 3: Phía sau khơng cịn ô nào nhỏ hơn

=> n5 = 0

Xét ô thứ 6 có giá trị 8: Phía sau có 3 ơ nhỏ hơn (4, 5, 7)

=> n6 = 3

Xét ô thứ 7 có giá trị 4: Phía sau khơng cịn ơ nào nhỏ hơn

=> n7 = 0

Xét ơ thứ 8 có giá trị 5: Phía sau khơng cịn ơ nào nhỏ hơn

=> n8 = 0

Xét ơ thứ 9 có giá trị 7: Phía sau khơng cịn ơ nào

=> n9 = 0


N=5+1+0+0+3+0+0+0=9

Hàm countStart() đếm giá trị N:

Hình 2. Giải thuật xác định trạng thái đích

Ta có: sum = 9  9 mod 2 = 1
⇨ Ta xác định được trạng thái đích 1

13


1.2.3.

Kiểm tra trạng thái đích

Nếu checker = 1, ta kiểm tra xem các giá trị trong ô đã đúng trạng thái
đích 1 chưa, ngược lại ta kiểm tra trạng thái đích 2

Hình 3. Giải thuật kiểm tra trạng thái đích

Hàm checkFinish() xác định trạng thái đích:
Sẽ trả về true nếu đã đúng trạng thái đích 1 hoặc 2
Ngược lại trả về false.

14


CHƯƠNG 2: CÁC THUẬT TỐN CHIỀU RỘNG,

CHIỀU SÂU
2.1. Thuật tốn tìm kiếm theo chiều rộng (BFS)
2.1.1.

Khái niệm

Là một thuật tốn duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi
nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi khơng gặp được đỉnh liền kề
trong bất kỳ vịng lặp nào. Thuật tốn ưu tiên duyệt các đỉnh gần với gốc
nhất theo thứ tự từ trái => phải hoặc ngược lại ở mức tiếp theo
Mục đích của thuật tốn:
+ Tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích
+ Tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác

2.1.2.

Tư tưởng

Tư tưởng của thuật toán Ta giả sử đầu vào thuật toán là
một đồ thị H = (A, B), ta sẽ phải thực hiện lập lịch duyệt cho
các đỉnh của đồ thị H. Việc duyệt các đỉnh sẽ được ưu tiên
sao cho đỉnh nào gần với nó nhất sẽ được duyệt trước. Tức là
nó bắt đầu từ mức thấp nhất của khơng gian bài tốn, sẽ
duyệt theo chiều từ trái sang phải hoặc ngược lại ở mức tiếp
theo, nếu khơng thấy lời giải ở mức này nó sẽ chuyển xuống
mức kế để tiếp tục...cứ như vậy đến khi tìm được lời giải
(nếu có).
Ta xét ví dụ sau: Ví dụ : Bắt đầu ta thăm đỉnh S. Việc thăm
đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh (x[1], x[2], ..

,x[p]) kề với S (những đỉnh gần S nhất). Khi thăm đỉnh x[1]
sẽ lại phát sinh yêu cầu duyệt những đỉnh (u[1], u[2], ...,
u[q]) kề với x[1]. Nhưng rõ ràng các đỉnh u này xa S hơn
những đỉnh x nên chúng chỉ được duyệt khi tất cả các đỉnh x
đã được duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã
thăm x[1] sẽ là : (x[2], x[3], ..., x[p], u[1], u[2],..., u[q])

15


Hình 4. Thứ tự thăm các đỉnh của BFS

Hình trên minh họa thứ tự duyệt của thuật tốn tìm kiếm
theo chiều rộng: ta nhận thấy quá trình duyệt của đồ thị sẽ
là S => x1 => x2 =>... xp => u1 => u2…=>…uq………….

2.1.3.

Thuật toán
void BFS(int u){
queue = φ;
u <= queue; /*nạp u vào hàng đợi*/
chuaxet[u] = false;/* đổi trạng thái của u*/
while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
queue<=p; /*lấy p ra từ khỏi hàng đợi*/
Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/
for (v ∈ke(p) ) {/* đưa các đỉnh v kề với p nhưng chưa được xét
vào hàngđợi*/
if (chuaxet[v] ) {
v<= queue; /*đưa v vào hàng đợi*/

chuaxet[v] = false;/* đổi trạng thái của v*/
}
}
} /* end while*/
}/* end BFS*/

2.1.4.

Ưu, nhược điểm

- Ưu điểm
16


Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn khơng gian
trạng thái bài tốn vì vậy sẽ tìm được lời giải nếu có.
+ Đường đi tìm được thỏa mãn đi qua ít đỉnh nhất.
+

- Nhược điểm
+ Tìm kiếm lời giải theo thuật tốn đã định trước, do vậy
tìm kiếm một cách máy móc; khi khơng có thơng tin bổ
trợ cho q trình tìm kiếm, khơng nhận ra ngay lời giải.
+ Khơng phù hợp với khơng gian bài tốn có kích thước
lớn. Đối với loại bài tốn này thì phương pháp tìm kiếm
chiều rộng đối diện với các khó khăn về nhu cầu:
 Cần nhiều bộ nhớ theo số nút cần lưu trữ.
 Cần nhiều công sức xử lý các nút, nhất là khi các
nhánh cây dài, số nút tăng.
 Dễ thực hiện các thao tác khơng thích hợp, thừa,

đưa đến việc tăng đáng kể số nút phải xử lý.
+ Không hiệu quả nếu lời giải ở sâu. Phương pháp này
khơng phù hợp cho trường hợp có nhiều đường dẫn đến
kết quả nhưng đều sâu.
+ Giao tiếp với người dùng không thân thiện. Do duyệt
qua tất cả các nút, việc tìm kiếm khơng tập trung vào
một chủ đề.

2.2. Thuật tốn tìm kiếm theo chiều sâu (DFS)
2.2.1.

Khái niệm

Là một thuật tốn duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị.
Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và
phát triển xa nhất có thể theo mỗi nhánh
Ưu tiên duyệt xuống sâu nhất có thể trước khi quay lại
Mục đích của thuật tốn:
+ Tìm kiếm trạng thái mục tiêu trong bài tốn tìm kiếm trên khơng
gian trạng thái
+ Kiểm tra tính liên thơng của đồ thị

2.2.2.
-

Tư tưởng
Từ đỉnh xuất phát duyệt một đỉnh kề
Các đỉnh của đồ thị được duyệt theo các nhánh đến nút lá
Nếu chưa tìm thấy đỉnh TG thì quay lui tới một đỉnh nào đó để sang
nhánh khác

17


-

Việc tìm kiếm kết thúc khi tìm thấy đỉnh TG hoặc đã hết các đỉnh

Hình 5. Thứ tự thăm các đỉnh của DFS

2.2.3.

Thuật toán
Lưu trữ: sử dụng DONG và MO
Trong đó:
+ DONG: chứa các đỉnh đã xét, hoạt động theo kiểu FIFO (hàng
đợi)
+ MO: chứa các đỉnh đang xét, hoạt độgn theo kiểu FILO (ngăn
xếp)
MO = ; MO = MO  {T0}
while (MO != ){
n = get(MO)
if (n == TG)
return TRUE
DONG = DONG  {n}
for các đỉnh kề v của n
if (v chưa được xét)
MO = MO  {v}
father(v) = n
}


Ví dụ: T0 = 1; TG = 8

18


n
1
2
3
4
5
6
7
8

B(n)
2, 6, 7
3, 5
4



8
Là

MO
1
2, 6, 7
3, 5, 6, 7
4, 5, 6, 7

5, 6, 7
6, 7
7
8
dừng

Hình 6. Ví dụ giải thuật DFS

DONG

1
1, 2
1, 2, 3
1, 2, 3, 4
1, 2, 3, 4, 5
1, 2, 3, 4, 5, 6
1, 2, 3, 4, 5, 6, 7

Cha
1
1
1
2
2
3
7

Con
2
6

7
3
5
4
8

đích
Đường đi: 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8

2.2.4.
Ưu, nhược điểm
- Ưu điểm
+ Nếu bài tốn có lời giải, phương pháp tìm kiếm theo chiều sâu
đảm bảo tìm ra lời giải.
+ Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài

+

lòng khi các câu hỏi tập trung vào vấn đề chính.
Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật sâu
sẽ tiết kiệm thời gian

- Nhược điểm
19


+ Tìm sâu khai thác khơng gian bài tốn để tìm lời giải theo thuật
tốn đơn giản một cách cứng nhắc. Trong q trình tìm nó khơng
có thơng tin nào để phát hiện lời giải. Nếu nút con ban đầu khơng
thích hợp có thể khơng dẫn tới đích của bài tốn.

+ Khơng phù hợp với khơng gian bài tốn lớn, kỹ thuật tìm kiếm
sâu có thể khơng đi đến lời giải trong khoảng thời gian vừa phải
(nếu cố định thời gian).
+ Không cần quan tâm đến số lượng các bước liên quan đến tìm
kiếm vàchỉ quan tâm đến chi phí đường dẫn. Do đó giả thuật này
có thể bị mắtkẹt trong một vịng lặp vơ hạn

2.3.

Sự khác nhau giữa 2 thuật toán

Đặc điểm
Căn bản
Cấu trúc của cây

BFS
Dựa trên vertex
Rộng và ngắn

DFS
Dựa trên cạnh
Hẹp và dài

xây dựng được
Tìm được đích
Tiêu thụ bộ nhớ
Tối ưu

Chắc chắn tìm được
Khơng hiệu quả

Tối ưu cho việc tìm

Khơng chắc chắn tìm được
Hiệu quả
Khơng tối ưu

Chi phí

khoảng cách ngắn nhất
Chi phí cao

Chi phí thấp

20


CHƯƠNG 3: CÀI ĐẶT CHƯƠNG TRÌNH
Tạo 1 lớp node như là các trạng thái của puzzle

21


22


Hình 7. Lớp Node thể hiện các trạng thái của puzzle

3.1. Tìm kiếm theo chiều rộng (BFS)

23



Hình 8. Code puzzle theo BFS

Sau khi tìm được trạng thái đích, biến check nhận giá trị true, lúc này
chuỗi way sẽ lưu lại đường đi từ trạng thái đầu đến trạng thái đích và thốt
khỏi vịng lặp.

24


25