BÀI TẬP LỚN MÔN TRÍ TUỆ NHÂN TẠO AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY

Trí tuệ là gì?Theo từ điển Bách khoa toàn thư Webster:Trí tuệ là khả năng:Phản ứng thích hợp lại những tình huống mới thông qua điều chỉnh hành vimột cách thích hợp. Hiểu rõ mối liên hệ giữa các sự kiện của thế giới bên ngoài nhằm đưa ranhững hành vi phù hợp để đạt được mục đích.
Nội dung trích xuất từ tài liệu:
BÀI TẬP LỚN MÔN TRÍ TUỆ NHÂN TẠO " AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY " BÀI TẬP LỚN MÔN: TRÍ TUỆ NHÂN TẠOĐỀ TÀI: AKT ĐỂ TÌM ĐƯỜNG ĐI TỐI ƯU CHO CẤU TRÚC CÂY Sinh viên thực hiện: Trịnh Minh Châu. 1. Trần Thị Minh Hải. 2. Nguyễn Bá Nguyện. 3. Vũ Quý Thăng. 4. Phạm Trọng Toàn. 5. Giảng viên hướng dẫn: Ths Trần Hùng Cường. 1LỜI NÓI ĐẦU....................................................................................................3Phân tích bài toán................................................................................................4 Mục đích bài toán............................................................................................4 Cách làm. .......................................................................................................5Cấu trúc d ữ liệ u và cách biểu diễn tr ạng thái c ủa bài toán .....................................7 Lớp khai báo đối tượng ...................................................................................7 Hàm tạo mẫ u chuỗi nhập vào ...........................................................................8 Hàm xử lý chuỗi nhập vào ..............................................................................9 Hàm xác đ ịnh tọa độ cho các nút vẽ ............................................................... 11 Hàm vẽ đồ thị ............................................................................................... 12 Hàm giả i thuật AKT ...................................................................................... 13 Các hàm cho giả i thuật .................................................................................. 15Giao diện chương trình ...................................................................................... 19Tài liệu tham khảo ............................................................................................ 20 2 LỜI NÓI ĐẦUTrí tuệ là gì?Theo từ điển Bách khoa toàn thư Webster:Trí tuệ là khả năng:  Phản ứng thích hợp lại những tình huống mới thông qua điều chỉ nh hành vi một cách thích hợp.  Hiểu rõ mối liên hệ giữa các s ự kiện c ủa thế giới bên ngoài nhằm đưa ra những hành vi phù hợp để đạt được mục đích.Vậy trí tuệ nhân tạo là gì?Thuật ngữ trí tuệ nhân tạo(Artifical Intellegence) được Jonh McCarthly đưa ratrong hội thảo ở Darthouth vào mùa hè năm 1956. Đã có rất nhiều định nghĩa khácnhau về trí tuệ nhân tạo. Với trí tuệ nhân tạo, máy tính đã giúp con người giảiquyết các vấn đề một cách thông minh nhất. Ta s ẽ tìm hiểu một s ố phương phápgiải quyết vấn đề cơ bản. Cụ thể là phương pháp tìm kiếm trong không gian trạngthái với thuật giải AKT . 3 1. P hân tích bài toá n. Mục đích bài toán. 1.1.Giả s ử ta có một đồ thị dạng cây như hình vẽ: A B C D E F G H I JTa c ần tìm đường đi từ điểm A J. Biết g(n) là chi phí thực từ n0 n.Thuật giải AKT là mở rộng c ủa thuật giải AT bằng cách s ử dụng thêm thông tin ướclượng h(n).Thuật giải AT là thuật giải tìm đường đi tối ưu mà nó chỉ xét đến đỉ nh và giá c ủachúng (g). Tuy nhiên giải thuật này không còn phù hợp khi gặp phải những bàitoán phức tạp do phải tháo một lượng nút lớn(có kích thước bài toán tăng theo hàmmũ từ đó d ẫn đến bùng nổ về tổ hợp) đ ể khắc phục nhược điểm này người ta s ửdụng thêm các thông tin b ổ sung xuất phát từ bản thân bài toán đ ể tìm ra các đ ỉ nhcó triển vọng, tức là đường đi tối ưu s ẽ tập trung xung quanh đường đi tốt nhất nếus ử dụng các thông tin đ ặ tả về bài toán. 4Vậy theo đ ịnh nghĩa các thông tin này được gọi là các Heuristics: h(n) hay chính làchi phí ước lượng từ n  G.Các kỹ thuật s ử dụng h(n) gọi là các mẹo giải, ta có thể đưa ra các mẹo giải sau: - Chọn toán tử xây dựng cung sao cho có thể loại bớt các đ ỉ nh không liên quan và tìm ra các đ ỉ nh có triển vọng. - Sử dụng thêm các thông tin b ổ sung nhắm xây d ựng tập MO và cách lấy các đỉ nh trong tập MO.Để làm được việc này, người ta phải đưa ra đ ộ đo, tiêu chuẩn ...