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 643 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

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

Factors that can affect differences in students' computational thinking

8 trang

Tài liệu giảng dạy Tin học cơ sở - Trường Đại học Quy Nhơn

95 trang

Tài liệu bồi dưỡng kỹ năng sử dụng công nghệ thông tin cơ bản (Dành cho cán bộ, công chức, viên chức và các đối tượng khác) - Trường Cao đẳng Cộng đồng Kon Tum

171 trang

Hướng dẫn sử dụng cơ sở dữ liệu quản lý thuyền viên (dành cho cơ quan quản lý nhà nước)

19 trang

Hướng dẫn sử dụng cơ sở dữ liệu quản lý thuyền viên (dành cho chủ tàu, tổ chức cung ứng thuyền viên)

25 trang

Tài liêu mới

Bài giảng Thiết kế hướng đối tượng: Chương 4 - Thiết kế hệ thống

95 trang

Bài giảng Thiết kế hướng đối tượng: Chương 3 - Phân tích hệ thống

138 trang

Bài giảng Thiết kế hướng đối tượng: Chương 2 - Ngôn ngữ mô hình hóa hướng đối tượng

58 trang

Bài giảng Thiết kế hướng đối tượng: Chương 1 - Tổng quan thiết kế hướng đối tượng

40 trang

Bài giảng Lập trình website - ThS. Trần Thịnh Mạnh Đức

79 trang

Tài liệu ôn tập môn Lập trình web 1

W 34 trang

Tài liệu thực hành Phát triển ứng dụng Web 1

189 trang

Bài thuyết trình: Xây dựng hệ thống hỗ trợ dạy và học trực tuyến với tích hợp công nghệ Android cho di dộng

35 trang

Bài giảng Lập trình hướng đối tượng - ThS. Trương Thị Minh Châu

35 trang

Bài giảng Lập trình Java: Chương 5 - Kết nối cơ sở dữ liệu (JDBC)

26 trang

Bài giảng Lập trình Java: Chương 4 - Luồng (streams)

25 trang

Bài giảng Lập trình Java: Chương 3 - Kế thừa - Đa hình - Đóng gói

11 trang

Bài giảng Lập trình Java: Chương 2 - Đối tượng - lớp - phương thức

13 trang

Bài giảng Lập trình Java: Chương 1 - Tổng quan ngôn ngữ Java

29 trang

Bài tập lớn: Quản lý thư viện

W 202 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