Khi một thuật toán đã hình thành thì ta không xét đến việc chứng minh thuật toán đó mà chỉ chú trọng đến việc áp dụng các bước theo sự hướng dẫn sẽ có kết quả đúng. Việc chứng minh tính đầy đủ và tính đúng của các thuật toán phải được tiến hành xong trước khi có thuật toán. Nói rõ hơn, thuật toán có thể chỉ là việc áp dụng các công thức hay qui tắc, qui trình đã được công nhận là đúng hay đã được chứng minh về mặt toán học.
"Thuật toán" hiện nay thường được dùng để chỉ thuật toán giải quyết các vấn đề tin học. Hầu hết các thuật toán tin học đều có thể viết thành các chương trình máy tính mặc dù chúng thường có một vài hạn chế (vì khả năng của máy tính và khả năng của người lập trình). Trong nhiều trường hợp, một chương trình khi thiết kế bị thất bại là do lỗi ở các thuật toán mà người lập trình đưa vào là không chính xác, không đầy đủ, hay không ước định được trọn vẹn lời giải của vấn đề. Tuy nhiên cũng có một số bài toán mà hiện nay người ta chưa tìm được lời giải triệt để, những bài toán ấy gọi là những bài toán NP-không đầy đủ.
2 trang |
Chia sẻ: tlsuongmuoi | Lượt xem: 2385 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Thuật toán nâng cao, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
- 1 -
Trí Tuệ Nhân Tạo
Đại Học Khoa Học Tự Nhiên Tp.HCM
227 Nguyễn Văn Cừ, Q5
GVHD: Lê Ngọc Thành
Quách Khả Gia
Phạm Trọng Nghĩa
Bài tập thực hành
Thuật toán A*
1. Nội dung
Thực hiện cài đặt thuật toán A* trên 8 puzzle.
2. Yêu cầu
Cài đặt thuật toán A* để tìm lời giải tối ưu cho bài toán 8-puzzle.
Độ ưu tiên của một trạng thái: f = g + h, trong đó g: độ sâu của trạng thái, h là hàm heuristic và có
thể có các giá trị sau:
• h1 = 0 (tương đương breadth-first search)
• h2 = tổng khoảng cách Mahattan
• h3 = số ô nằm sai vị trí của trạng thái đầu so với trạng thái đích
Bài giống nhau 0 điểm. Chương trình do máy chấm!
3. Yêu cầu chi tiết
Chương trình đọc các ô số ban đầu và kết thúc từ tập tin input.txt trong đó các ô số được biểu diễn
bằng cách ma trận kích thước 3x3. Các số trong ma trận mang giá trị từ 1 đến 8 và ô số 0 biểu diễn cho ô
trống của trạng thái. Chương trình thực hiện thuật toán A* để tìm lời giải tối ưu (nếu có) và xuất kết quả ra
tập tin mssv.txt dưới dạng các trạng thái trung gian, mỗi trạng thái ứng với kết quả của một lần đẩy (lưu ý:
chỉ xuất ra các trạng thái trên đường đi đến đích).Trong trường hợp không có lời giải, sinh viên xuất ra “-
1”.
Chương trình được viết dưới dạng tham số dòng lệnh với thứ tự chi tiết như sau:
mssv.exe input.txt output.txt heurictic
Trong đó mssv.exe là tên chương trình, input.txt là tên file chứa nội dung đưa vào chương trình,
output.txt là tên file cần xuất ra kết quả, heurictic là chỉ mục hàm heurictic được chọn để thực hiện thuật
toán A* và có giá trị 1,2,3 ứng với h1, h2,h3.
Ví dụ:
012345.exe nhap.txt xuat.txt 2: nghĩa là chương trình nhận dữ liệu từ file có tên là
nhap.txt, xuất ra file có tên là xuat.txt và thực hiện A* với hàm h2.
3.1 Nội dung file input.txt
- 3 dòng đầu: ma trận xuất phát, kích thước 3x3.
- 1 dòng tiếp: dòng trống.
- 3 dòng sau: ma trận xuất phát, kích thước 3x3.
3.2 Nội dung file xuất ra mssv.txt
- 3 dòng đầu: ma trận trạng thái bắt đầu.
- 3 dòng một tiếp theo là các trạng thái trung gian của lần đẩy cho đến trạng thái đích.
Ví dụ:
1
0
/2
0
1
0
1 4 5
3 0 6
7 2 8
1 2 3
4 5 6
7 8 0
- 2 -
Trường hợp đặc biệt:
1 4 5
3 0 6
7 2 8
1 4 5
3 6 0
7 2 8
…
1 2 3
4 5 6
7 8 0
Không có
đường đi
-1
Các file đính kèm theo tài liệu này:
- Thuật toán nâng cao.pdf
