Tài liệu hướng dẫn thực hành BÀI TOÁN MÃ ĐI TUẦN

1. Mô tảCho trước một bàn cờ vua có n x n ô (xét n = 8) và một vị trí đặt con Mã trên bàn cờ đó. Tìm cách cho con Mã nhảy qua tất cả các ô của bàn cờ (n x n ô), mỗi ô chỉ nhảy qua duy nhất một lần và phải nhảy đúng theo luật của cờ Vua.
Nội dung trích xuất từ tài liệu:
Tài liệu hướng dẫn thực hành BÀI TOÁN MÃ ĐI TUẦN Tài liệu hướng dẫn thực hành BÀI TOÁN MÃ ĐI TUẦN Văn Chí Nam – Nguyễn Đức Hoàng Hạ Lu Boun Vinh – Nguyễn Anh Tuấn Khoa Công nghệ Thông tin, trường Đại học Khoa học Tự nhiên Tp.HCM Phiên bản cập nhật ngày 18/05/20041. Mô tả Cho trước một bàn cờ vua có n x n ô (xét n = 8) và một vị trí đặt con Mãtrên bàn cờ đó. Tìm cách cho con Mã nhảy qua tất cả các ô của bàn cờ (n x n ô),mỗi ô chỉ nhảy qua duy nhất một lần và phải nhảy đúng theo luật của cờ Vua.2. Nước đi của Mã Theo luật cờ Vua, tại một vị trí bất kỳ con mã có thể đi tiếp tối đa 8 vị trí,như hình vẽ dưới đây : 1 2 8 3 X 7 4 6 53. Heuristic để giải bài toán Đây là một bài toán không có thuật toán (algorithm) nhưng có thể tìm đượclời giải thông qua phương pháp vét cạn. Dưới đây mô tả hai heuristic được dùngđể tìm cách đi của Mã 1Tài liệu hướng dẫn thực hành Cách 1 (Heuristic 1) : Heuristic 1 được mô tả như dưới đây có thể nói đạt hiệu quả tốt trong việctìm đường đi cho con Mã. Trong quá trình cài đặt và chạy thử, Heuristic này đảmbảo tìm thấy đường đi cho hầu hết các vị trí đặt Mã ban đầu trên bàn cờ 8x8. Giả sử sau bước nhảy thứ k, Mã có n vị trí V1 ,V2 , ..., Vn có thể đi tới ở bướck+1, làm sao để chọn một trong các vị trí trên để đặt Mã. Heuritic 1 miêu tả nhưsau: + Tính f(Vi) = số vị trí con Mã có thể nhảy tới từ vị trí Vi. + So sánh cácgiá trị f(Vi) lấy giá trị nhỏ nhất. Tức là chọn M = Vk miễn là Vk nhỏ nhất làm vị trí nhảy tiếp theo. Cách 2 (Heuristic 2) : So với Heuristic 1, heuristic này có vẻ đơn giản hơn nhưng thực tế hiệu quảkhông cao. Vị trí (i,j) được chọn khi h(i,j) = min(8 – i, i –1) + min(j – 1, 8 –j) là nhỏnhất.4. Cấu trúc dữ liệu đề nghị int DeltaX[DONG] = {-2,-1,1,2,-2,-1,1,2}; int DeltaY[COT] = {1,2,2,1,-1,-2,-2,-1}; typedef struct { int X; int Y; }TOADO; int BanCo[DONG][COT]; Diễn giải : • DeltaX, DeltaY : mảng hằng số dùng để phát sinh vị trí đi nước đi của Mã tại một vị trí bất kỳ. 2Tài liệu hướng dẫn thực hành • TOADO : cấu trúc mô tả vị trí của Mã. • BanCo : mảng hai chiều ghi nhận các nước đi của Mã. • BanCo[i][j] = 0. Mã chưa nhảy đến ô có toạ độ (i,j). • BanCo[i][j] = m (m ≠0). Mã đã nhảy đến ô có toạ độ (i,j) ở bước thứ m.5. Cách chọn vị trí đi tiếp Bước 1 : Phát sinh các vị trí có thể đi được từ vị trí hiện hành. Bước 2 : Tính heuristic (heuristic 1, heuristic 2) cho từng vị trí. Bước 3 : Chọn vị trí có heuristic là nhỏ nhất để đi ở bước kế tiếp Bước 4 : Cập nhật lại bàn cờ Bước 5 : Quay lại bước 1.6. Các hàm thực hiện Hàm Phát sinh nước đi của Mã void PhatSinhNDMa(int BanCo[][COT], TOADO P, TOADODiTiep[], int &n) BanCo : mảng 2 chiều mô tả trạng thái hiện hành của bàn cờ. P : điểm hiện tại của Mã cần được phát sinh các nước đi kế tiếp. DiTiep : các vị trí đi tiếp của Mã ở nước đi kế tiếp. n : số vị trí phát sinh được. void PhatSinhNDMa(int BanCo[][COT], TOADO P, TOADODiTiep[], int &n) { n = 0; for (i = 0; i < DONG; i++) { 3Tài liệu hướng dẫn thực hành X = P.X + DeltaX[i]; Y = P.Y + DeltaY[i]; if (X >=0 && ....&& BanCo[X][Y] == 0) { .. . n++; } } } Hàm thực hiện void main() { //Đọc vị trí bắt đầu //Khởi tạo ma trận BanCo Buoc = 0; while (Chưa kết thúc) { PhatSinhNDMa(BanCo,P,DiTiep,n); if (n == 0&& BuocTài liệu hướng dẫn thực hành } } //Cập nhật lại mảng BanCo //P = Tmp, thực hiện tiếp Buoc++; //kết thúc khi Buoc >= DONG*COT } //Xuất mảng BanCo } ...