HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
MÔN HỌC: TRÍ TUỆ NHÂN TẠO
ĐỀ TÀI: GIẢI THUẬT TÌM KIẾM THEO
CHIỀU SÂU (DEPTH FIRST SEARCH)
Giảng viên : Thầy NGÔ HỮU
PHÚC
SV thực hiện : ĐÀO NGỌC ANH
Lớp : TIN HỌC 5A
HÀ NỘI, THÁNG 3 NĂM 2010
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
A. Thuật toán tìm kiếm theo chiều sâu (Depth First Search)
• Việc tìm kiếm tối ưu trong không gian trạng thái là công việc đã sớm được nghiên cứu trong
ngành Trí Tuệ Nhân Tạo. Việc tiếp cận này đòi hỏi chúng phải giải quyết một số lượng lớn
thông tin (bùng nổ tổ hợp), đôi khi đòi hỏi một thời gian tìm kiếm không thể chấp nhận được
(có khi lên đến hàng vạn năm). Do đó, việc tìm ra một giãi thuật tìm kiếm nhanh, hiệu quả là
công việc cần thiết. Trong phần này, chúng ta sẽ lần lượt tìm hiểu hai giải thuật cổ điển cũng
như đánh giá khả năng của nó.Sau đó, chúng ta sẽ demo 1 chương trình được viết trong ngôn
ngữ C# (trong bộ.net của Microsoft).
1. Khái niệm:
• Tìm kiếm theo chiều sâu luôn luôn mở rộng một trong các nút ở mức sâu nhất của cây. Chỉ
khi phép tìm kiếm đi tới một điểm cụt (một nút không phải đích mà không có phần mở rộng),
việc tìm kiếm sẽ quay lại và mở rộng đối với những nút nông hơn.
2. Đánh giá:
• Đủ? Không đủ (không gian vô hạn hoặc loop)
o Nếu sửa để tránh trùng lặp  đủ trong không gian hữu hạn.
• Thời gian? O(b
m
)
o Rất xấu nếu m lớn hơn nhiều so với d
o Nhưng nếu mật độ lời giải trong không gian lớn thì có thể nhanh hơn BFS

So sánh giữa DFS và BrFS :
Khi DFS thực hiện thì nó luôn chiếm dụng nhiều cùng nhớ hơn (do đặc thù của Stack) và nó luôn tìm
kiếm trên những vùng không cần thiết. Trong khi, BrFS lại luôn tìm thấy lời giải trong một kết quả tối
ưu.
Demo việc tìm kiếm DFS:
Mô tả bài toán: Không gian trạng thái được mô tả là ma trận có kích thước mxn. Trên khôn gian trạng
thái, có nơi được phép đến, có nơi không được phép đến. Hãy xây dựng chương trình tạo ngẫu nhiên
không gian trạng thái này, vị trí bắt đầu, vị trí cần tìm và sử dụng giải thuật tìm kiếm theo chiều sâu.
Đánh giá giải thuật thông qua không gian trạng thái thực tế.
• Ta sẽ tạo ra một ma trận bất kỳ với 2 giá trị 0 và 1 tương ứng với:
o 0 = đi được
o 1 = không đi được
o Từ ma trận này ta sẽ nhập vào vị trí của điểm bắt đầu và điểm kết thúc để chương trình
kiểm tra xem có đường đi hay không có đường đi từ điểm bắt đầu đến điểm kết thúc.
o Sau đó sẽ thể hiện kết quả trên phần ”Mô phỏng” bằng hình vẽ để người xem dễ dàng
nhận ra kết quả của bài toán.
• Mô hình của bài toán bao gồm:
o Class ”banco”
o Form
• Class ”banco”
class banco
{
int dong,cot;
int[,] a;
int step = 25;
public banco(int d, int c,int[,] ain)
{
dong = d; cot = c;
a = ain;
}

- Ma trận xác lập đường đi:
+ arrX = { 0, 1,0, -1 }
+ arrY = { -1, 0, 1, 0 }
- Ma trận arrCheck để đánh dấu điểm nào đã duyệt qua. (có cùng kích cỡ với ma trận được tạo
ra)
- pC: là điểm (đỉnh) được “pop” ra ngoài để kiểm tra.
- Điều kiện: if (i >= 0 && i <= cot-1 && j >= 0 && j <= dong-1) để tránh xét ra ngoài ma trận
Trang 4
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
Trang 5
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
• Hàng: nhập số hàng của ma trận
• Cột: nhập số cột của ma trận
 khi click vào button ” Tạo ma trận” thì ma trận sẽ được thể hiện trên ô Richtextbox ngay bên
cạnh.
Trang 6
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
• Điểm đầu: nhập vị trí (x,y) của điểm bắt đầu. Ví dụ: 0,0
• Điểm cuối: nhập vị trí đích đến (x,y) của điểm kết thúc. Ví dụ: 5,5
 Khi click vào button “Tìm đường” sẽ có 2 trường hợp xảy ra:
- Nếu tìm được tới đích sẽ xuất hiện messagebox “
Trang 7
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
- Ngược lại nếu ko tìm được đường đi sẽ xuất hiện message box “khong co duong di” như
sau:
Trang 8
Thuật toán Depth First Search- Đào Ngọc Anh – TIN HỌC 5A
• Mô phỏng:
- Khi chương trình tìm ra được đường đi, nó sẽ mô phỏng trên ô picturesBox như sau:
Trang 9