Báo Cáo Cài đặt thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng bằng ngôn ngữ C

LỜI NÓI ĐẦUTrí tuệ nhân tạo (TTNT) là một lĩnh vực của khoa học máy tính, nghiên cứu sự thiết kế của các tác nhân thông minh. Các áp dụng của TTNT rất đa dạng và phong phú, hiện nay đã có rất nhiều hệ thông minh ra đời như: các hệ chuyên gia, các hệ điều khiển tự động, các hệ nhận dạng, Kỹ thuật của TTNT đã được sử dụng trong việc xây dựng các hệ mềm nhằm tạo ra các hệ mềm mang yếu tố thông minh, linh hoạt và tiện dụng.
Một trong những nghiên cứu đó là đưa ra các giải thuật tìm kiếm tối ưu nhất phục vụ việc giải quyết các vấn đề của bài toán một cách nhanh nhất có thể. Giải thuật tìm kiếm là một thuật toá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 toán đó. Hầu hết các thuật toán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là các thuật toán tìm kiếm. Tập hợp tất cả các lời giải có thể đối với một bài toán được gọi là không gian tìm kiếm. Tìm kiếm vét cạn (brute-force search) hay các thuật toán tìm kiếm cơ bản sử dụng phương pháp đơn giản nhất và trực quan nhất. Trong khi đó, các thuật toán tìm kiếm có thông tin sử dụng hàm Heuristics để áp dụng các tri thức về cấu trúc của không gian tìm kiếm nhằm giảm thời gian cần thiết cho việc tìm kiếm. Để hiểu rõ bản chất của thuật giải Heuristic, chúng ta nhất thiết phải nắm vững hai chiến lược tìm kiếm cơ bản là tìm kiếm theo chiều sâu (Depth First Search) và tìm kiếm theo chiều rộng (Breath First Search). Cụ thể chúng em sẽ trình bày việc cài đặt thuật toán tìm kiếm theo chiều sâu và tìm kiếm theo chiều rộng bằng ngôn ngữ C#.
Trong quá trình thực hiện đề tài, tuy có nhiều cố gắng nhưng sẽ không tránh khỏi những sai sót, rất mong được thầy hướng dẫn và góp ý. Chúng em xin chân thành cảm ơn thầy Nguyễn Trí Nhân đã tận tình hướng dẫn và tạo điều kiện tốt trong quá trình học tập cũng như trong quá trình chúng em hoàn thành đề tài này.

MỤC LỤC

LỜI NÓI ĐẦU 1
MỤC LỤC 2
I. Phân tích bài toán. 3
1. Mục đích bài toán. 3
a. Tìm kiếm theo chiều sâu. 3
b. Tìm kiếm theo chiều rộng. 3
2. Cách làm 3
a. Tìm kiếm theo chiều sâu. 3
b. Tìm kiếm theo chiều rộng. 5
II. Cấu trúc dữ liệu và cách biểu diễn các trạng thái của bài toán. 6
1. Tìm kiếm theo chiều sâu. 7
2. Tìm kiếm theo chiều rộng. 7
3. Một số bài toán liên quan. 8
a. Trạng thái xa nhất 8
b. Mã trên bàn cờ 5x5. 9
III. Mã giả các thuật toán được sử dụng. 9
1. Tìm kiếm theo chiều sâu. 9
a. Giải thuật. 9
b. Ví dụ. 10
c. Ưu và nhược điểm: 12
2. Tìm kiếm theo chiều rộng. 12
a. Giải thuật. 12
b. Ví dụ. 13
c. Ưu và nhược điểm: 15
IV. So sánh thuật toán tìm kiếm theo chiều sâu và theo chiều rộng. 16
V. Ngôn ngữ sử dụng: C-Sharp. 17
VI. Một số giao diện và kết quả chạy chương trình. 20
1. Giao diện chính của trương trình. 20
2. Giao diện tìm kiếm theo chiều sâu. 21
3. Giao diện tìm kiếm theo chiều rộng. 22
Tài liệu tham khảo. 24