intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Huy Đạt | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST
Báo xấu
534
lượt xem 46
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
5=>2