Bài toán mã đi tuần quay lui c++ năm 2024

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 Phiên bản cập nhật ngày 18/05/

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.

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 5

3. 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 được lờ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ã

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ệc tìm đường đi cho con Mã. Trong quá trình cài đặt và chạy thử, Heuristic này đảm bả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í V 1 ,V 2 , ..., Vn có thể đi tới ở bước k+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 :

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

1. 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/2004 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. 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 5 3. 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 được lờ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ã 1
2. Tà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ệc tìm đường đi cho con Mã. Trong quá trình cài đặt và chạy thử, Heuristic này đảm bả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ước k+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ỳ. 2
3. Tà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, TOADO DiTiep[], 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, TOADO DiTiep[], int &n) { n = 0; for (i = 0; i < DONG; i++) { 3
4. Tà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&& Buoc
5. Tà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 } 5