Tài Liệu Hướng Dẫn Thực Hành BÀI TOÁN MÃ ĐI TUẦN - TaiLieu.VN

Mạng xã hội chia sẻ tài liệu Upload Đăng nhập Nâng cấp VIP Trang chủ » Công Nghệ Thông Tin » Kỹ thuật phần mềm5 trang 665 lượt xem 460Tà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.

Chủ đề:

holongtuong

Thủ thuật máy tính

Tài liệu hướng dẫn Thủ thuật máy tính

SaveLikeShareReport Download AI tóm tắt /5 Tài liệu hướng dẫn thực hành 1 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ấnKhoa 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ã Tài liệu hướng dẫn thực hành 2 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 = Vkmiễ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ỳ. Tài liệu hướng dẫn thực hành 3 •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++) { Tài liệu hướng dẫn thực hành 4 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<DONG*COT) { //Kết thúc không thành công //Thoát } for (i = 0; i < n;i++) { h = Heuristic(BanCo, DiTiep[i]); if (h < gtmin) { //Ghi nhận lại vị trí Tmp Tài liệu hướng dẫn thực hành 5 } } //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 }

Tài liệu liên quan

Top 10 thủ thuật trong Word

24 trang

Mô đun Năng lực số (Trình độ cao đẳng và trung cấp)

62 trang

Tài liệu khoá tập huấn Nâng cao nhận thức, kỹ năng về an toàn, an ninh thông tin cho cán bộ công chức

55 trang

Dự án Go Digital ASEAN: Mạng Internet và Ứng dụng di động cơ bản (Tài liệu dành cho cán bộ giảng dạy)

38 trang

Tài liệu hướng dẫn Khóa học kỹ năng số cơ bản

119 trang

Tài liệu học tập Kỹ năng sử dụng công nghệ thông tin cơ bản

W 31 trang

Tài liệu Hướng dẫn sử dụng MS Project 2016

60 trang

Tài liệu giảng dạy Lịch sử khoa học máy tính

43 trang

Toàn bộ 45 phím tắt trong AutoCAD mà bạn nên biết

W 33 trang

Tài liệu chuyên đề 11: Kỹ năng ứng dụng cộng nghệ thông tin cho cộng đồng, người dân trong hoạt động sản xuất kinh doanh (Lưu hành nội bộ - Nhóm Cộng đồng)

92 trang

Tài liêu mới

Giáo trình Tin học ứng dụng (Module 01 – Làm chủ nền tảng công nghệ)

46 trang

Bài giảng Scratch mở rộng (Phiên bản 3.0) - Lại Đại Vương

49 trang

Bài giảng Scratch cơ bản (Phiên bản 3.0) - Lại Đại Vương

91 trang

Giáo trình N8N AI automation

77 trang

62 câu trắc nghiệm Lập trình hướng đối tượng có đáp án

18 trang

Bài giảng Google Studio cơ bản

83 trang

Lecture The Object-Oriented Thought Process - Chapter 5: Class design guidelines

21 trang

Lecture The Object-Oriented Thought Process - Chapter 4: The anatomy of a class

8 trang

Lecture The Object-Oriented Thought Process - Chapter 3: Advanced object-oriented concepts

18 trang

Lecture The Object-Oriented Thought Process - Chapter 2: How to think in terms of objects

12 trang

Lecture The Object-Oriented Thought Process - Chapter 1: Introduction to object-oriented concepts

40 trang

Tài liệu học tập Lập trình Java cơ bản

112 trang

Đề thi cuối học kì 1 môn Lập trình ứng dụng trong kỹ thuật năm 2025-2026

10 trang

Bài giảng Công nghệ web: Bài 9 - Kiều Tuấn Dũng

24 trang

Bài giảng Công nghệ web: Bài 8 - Kiều Tuấn Dũng

7 trang

AI tóm tắt

- Giúp bạn nắm bắt nội dung tài liệu nhanh chóng!

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

Zalo/Tel:

093 303 0098

Email:

[email protected]

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Chịu trách nhiệm nội dung: Nguyễn Công Hà Doanh nghiệp quản lý: Công ty TNHH Tài Liệu trực tuyến Vi Na - GCN ĐKDN: 0307893603 Địa chỉ: 54A Nơ Trang Long, P. Bình Thạnh, TP.HCM - Điện thoại: 0283 5102 888 - Email: [email protected]ấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015