HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Giáo viên hướng dẫn: Ngô Hữu Phúc
HÀ NỘI 3/2010
Đồ án
Nhập môn trí tuệ nhân tạo
Đề tài: Không gian trạng thái là ma trận kích thước m*n. Trên không gian trạng
thái có nơi được phép đến, có nơi không được phép đến. 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 rộng.
Thầy giáo hướng dẫn: Ngô Hữu Phúc
Học viên : Đàm Ngọc Anh
Lớp : Tin học 5A
Hà Nội, tháng 3 năm 2010
Mục lục
Lời nói đầu 4
I. Cơ sở lí thuyết 4
II. Chương trình: 5
III. Kết quá thu được từ chương trình tìm đường sử dụng thuật toán Nhánh và cận: 10
Lời nói đầu
Kỹ thuật tìm kiếm được chia ra làm 3 loại:
- Kỹ thuật tìm kiếm mù: Trong bài toán này, chúng ta hoàn toàn không biết gì về các
đối tượng để hướng dẫn tìm kiếm mà chỉ đơn thuần là xem xét tất cả các đối tượng
của 1 hệ thống để phát hiện ra đối tượng cần tìm. Một số kỹ thuật tìm kiếm mù: Tìm
kiếm theo chiều rộng (Breadth-first search) và tìm kiếm theo chiều sâu (depth-first
search)
- Kỹ thuật tìm kiếm có kinh nghiệm (Tìm kiếm với hàm Heuristic): Hàm Heuristic là
hàm đánh giá được xây dựng nhờ vào kinh nghiệm và sự hiểu biết của chúng ta về vấn
đề cần giải quyết. Một số kỹ thuật tìm kiếm có kinh nghiệm: Tìm kiếm beam, Tìm

Trường hợp không tìm được đường đi, chương trình sẽ đưa ra thông báo
Trong chương trình em đã sử dụng các đoạn thuật toán:
- Tạo ma trận bất kỳ
- Mảng father để lưu lại các đỉnh đã đi qua.
- Mảng 2 chiêu bool bao gồm các phần tử true, false, ánh xạ của ma trận
ban đầu.
bool[,] arrCheck = new bool[dong, cot];
- Đoạn chương trình mô tả thuật toán tìm kiếm BFS

- Đoạn chương trình hiển thị kết quả
III. Kết quá thu được từ chương trình tìm đường sử dụng
thuật toán Nhánh và cận:
Khuôn khổ của đồ án này chỉ giới hạn trong việc minh họa cho thuật toán
tìm kiếm theo chiều rộng chứ chưa hướng tới việc áp dụng trong thực tế
Nếu muốn áp dụng cho thực tế thì sẽ cần nhiều thời gian và quá trình tìm
hiểu hơn nữa nên sau khi kết thúc môn học này, em mong thầy có thể giúp đỡ để em
có thể hoàn thiện chương trình của em hơn.
Em xin cám ơn thầy!
V. Tài liệu tham khảo:
- Slide bải giảng AI: TS.Ngô Hữu Phúc.
- Vở ghi trên lớp.