HCMUS - AI Course Report [PDF]

Zitiervorschau

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN

MÔN CƠ SỞ TRÍ TUỆ NHÂN TẠO

BÁO CÁO ĐỒ ÁN MÔN HỌC 1 THUẬT TOÁN A* VÀ BÀI TOÁN N-PUZZLE

Sinh viên thực hiện: Họ và tên

MSSV

Bùi Hữu Lễ 1312318

Lớp TH2013/2 Khóa 2013 Năm học: 2014 – 2015

Mục lục 1. Tổng quan về đồ án ............................................................................................................. 1 1.1. Tình hình thực hiện đồ án ........................................................................................... 1 1.2. Tài liệu tham khảo ........................................................................................................ 1 2. Chương trình giải bài toán 8-puzzle bằng thuật toán A* .............................................. 1 2.1. Tổng quan về chương trình......................................................................................... 1 2.2. Hướng dẫn sử dụng ..................................................................................................... 1 2.3. Mô tả cài đặt chương trình .......................................................................................... 3 2.3.1. Sơ đồ UML .............................................................................................................. 4 2.3.2. Mô tả các lớp đối tượng ........................................................................................ 5 3. Khảo sát kết quả giải 8 puzzle bằng thuật toán A* với các hàm Heuristic khác nhau. .......................................................................................................................................... 6 3.1. Thống kê......................................................................................................................... 6 3.2. Nhận xét ......................................................................................................................... 6 4. Khảo sát kết quả giải 8 puzzle bằng thuật toán A* với giá trị cân bằng khác nhau .. 7 4.1. Thống kê......................................................................................................................... 7 4.2. Nhận xét ......................................................................................................................... 7

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1

1. Tổng quan về đồ án 1.1. Tình hình thực hiện đồ án Yêu cầu Cài đặt chương trình giải bài toán 8-puzzle bằng thuật toán A*

Trạng thái Hoàn thành

thực nghiệm thuật toán A* (w = 0.5) với các hàm heuristic khác nhau Hoàn thành và viết báo cáo thực nghiệm thuật toán A* (w = 0.5) với các hàm heuristic khác (w ≠ 0.5) và viết báo cáo

Hoàn thành

1.2. Tài liệu tham khảo [1] http://en.wikipedia.org/wiki/15_puzzle [2] http://en.wikipedia.org/wiki/A*_search_algorithm [3] http://docs.oracle.com/javase/8/docs/api/ [4] https://www.cs.princeton.edu/courses/archive/fall12/cos226/assignments/8puzzle. html [5] Lê Hoài Bắc – Tô Hoài Việt, 2014, Cơ sở trí tuệ nhân tạo, Nhà xuất bản Khoa học và Kỹ thuật.

2. Chương trình giải bài toán 8-puzzle bằng thuật toán A* 2.1. Tổng quan về chương trình    

Ngôn ngữ lập trình: Java Nền tảng: Java SE Runtime Environment 8 Giao diện: dòng lệnh Tên tập tin thực thi: 1312318.jar

2.2. Hướng dẫn sử dụng  Để chạy được chương trình, hệ thống cần cài máy ảo Java 8 (JVM 8), download tại link sau: http://www.oracle.com/technetwork/java/javase/downloads/jre8-downloads2133155.html  Chương trình giao diện dòng lệnh của Java không thể thực thi khi mở, để chạy chương trình loại này trên Windows, ta phải sử dụng command line.  Tại cửa sổ command line, ta di chuyển đến thư mục chứa file thực thi .jar bằng các lệnh cd, sau đó gõ lệnh với cú pháp java –jar []  Ví dụ 1

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1

 Sau khi thực thi dòng lệnh trên, chương trình kết quả sẽ xuất ra màn hình và file output.txt

2

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1

2.3. Mô tả cài đặt chương trình

3

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1 2.3.1. Sơ đồ UML

4

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1

2.3.2. Mô tả các lớp đối tượng Lớp

Puzzle

AStar

SearchTester

Mô tả lớp

Cài đặt trạng thái của bài toán

Cài đặt thuật toán AStar

Phương thức chính

Chức năng của phương thức

slide

Thực hiện 1 bước di chuyển ô trống

getNeighbor

Sinh ra các trạng thái con

equal

So sánh 2 trạng thái bằng nhau

compareTo

So sánh độ ưu tiên của 2 trạng thái

misplaceCount

Đếm số ô sai vị trí

ManhattanDistance

Tính tổng khoảng cách Manhattan

isReachable

Kiểm tra xem trạng thái đang xét có đến được 1 trạng thái đích cho trước hay không

Solve

Giải bài toán 8 puzzle với 2 trạng thái truyền vào bằng A*

calcCost

Tính độ ưu tiên của trạng thái trong hàng đợi

Phần chính của singleTest chương trình, nhận các thông số từ dòng lệnh, thực hiện giải bằng thuật toán

Gọi thuật toán giải bài toán, đo thời gian thực hiện

5

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1 đưa vào, đo các chỉ số cần thiết, trả về kết quả thực hiện Main

Chứa hàm main của chương trình

isValidArgument

Kiểm tra tham số dòng lệnh đầu vào

solveTest

Thực hiện chạy A* bằng cách gọi phương thức singleTest của SearchTester

outputResult

Xuất kết quả

3. Khảo sát kết quả giải 8 puzzle bằng thuật toán A* với các hàm Heuristic khác nhau. 3.1. Thống kê Chú thích:   

H1: tìm kiếm theo chiều rộng. H2: số ô nằm sai vị trí của trạng thái đầu so với trạng thái đích. H3: tổng khoảng cách Manhattan giữa trạng thái đầu và trạng thái đích. Số trạng thái được mở

Độ sâu lời giải

Hệ số phân nhánh trung bình

Thời gian thực hiện (ms)

h1

517409.32

21.46

1.783459993

3174.29

h2

19610.12

21.46

1.535848814

47.92

h3

1568.31

21.46

1.375683067

5.62

Bảng kết quả thống kê trung bình với 100 bộ test (Bảng thống kê chi tiết xem trong file HeuristicTestResult.xlsx) 3.2. Nhận xét Qua bảng thống kê trên ta thấy hàm Heuristic h3 (tổng khoảng cách Manhattan) có kết quả tốt nhất (số trạng thái mở, hệ số phân nhánh, thời gian thực hiện thấp). Ngược lại hàm Heuristic h1 (tìm kiếm theo chiều rộng) có kết quả “xấu” nhất. Tóm 6

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1 lại, đối với 1 bài toán 8 puzzle nói riêng và các bài toán tìm kiếm nói chung, khi có thêm thông tin (dựa vào 1 hàm Heuristic chấp nhận được) thì việc tìm kiếm trở nên nhanh hơn, tiết kiệm tài nguyên hơn do “đi đúng hướng” hơn.

4. Khảo sát kết quả giải 8 puzzle bằng thuật toán A* với giá trị cân bằng khác nhau 4.1. Thống kê Số trạng thái được mở

W

Độ sâu lời giải

Hệ số phân nhánh trung bình

Thời gian thực hiện (ms)

0

356.09

55.25

1.125672

2.53

0.1

494.61

36.73

1.192327

2.18

0.2

529.4

29.63

1.235402

1.83

0.3

726.23

24.87

1.288858

2.44

0.4

984.86

22.35

1.329666

3.05

0.5

1822.8

21.93

1.374687

4.85

0.6

10971.61

21.93

1.47987

35.32

0.7

42851.89

21.93

1.574559

126.68

0.8

133613.45

21.93

1.654049

520.12

0.9

343132.69

21.93

1.721787

2006.94

1

706875.83

21.93

1.773932

5194.53

Bảng kết quả thống kê trung bình với 100 bộ test với hàm Heuristic h3 (Bảng thống kê chi tiết xem trong file BalanceTestResult.xlsx) 4.2. Nhận xét Dựa vào bảng thống kê ta có thể đánh giá các giá trị cân bằng w như hình sau:

7

Cơ sớ trí tuệ nhân tạo TH2013/2 - Đồ án 1

Minh họa các giá trị cân bằng w khác nhau Nếu lấy 0.5 là mức cân bằng, ta thấy rằng các giá trị w phân hóa thành 2 nhóm: 



Nhóm 1 (w < 0.5) thiên về tìm kiếm tham lam, độ ưu tiên của trạng thái dựa nhiều vào thông tin Heuristic của trạng thái. Khi giá trị w càng gần 0, số trạng thái được mở ra càng ít, vì vậy lời giải được tìm ra nhanh hơn nhưng lời giải không tối ưu (độ sâu của lời giải cao). Nhóm 2 (w > 0.5) thiên về tìm kiếm chi phí đồng nhất, độ ưu tiên của trạng thái dựa nhiều vào độ sâu của trạng thái hơn là giá trị Heuristic. Khi giá trị w càng gần 1, số trạng thái được mở ra càng nhiều, thời gian thực hiện lâu hơn nhưng bù lại lời giải tìm ra có độ sâu tối ưu hơn nhóm 1.

8