Bài toán mã đi tuần c++

Mã đi tuần (xuất xắc hành trình dài của quân mã) là bài bác toán về bài toán dịch rời một quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt tại 1 ô trên một bàn cờ trống nó phải di chuyển theo luật lệ của cờ vua nhằm đi qua từng ô trên bàn cờ đúng một lần. Trong bài bác này, công ty chúng tôi xin reviews về bài toán thù độc đáo này cùng hầu hết điều có thể khai quật được qua bài toán thù.

You watching: Bài toán mã đi tuần c++

Trong cờ vua, quân Mã là quân tất cả giải pháp đi phức hợp độc nhất vô nhị. Xét một quân Mã vẫn đứng bên trên bàn cờ với tất cả các hình chữ nhật 2 x 3 nhấn ô cơ mà quân Mã kia đã đứng làm đỉnh. Quân Mã kia rất có thể đi tới các đỉnh khác color với đỉnh nó vẫn đứng của bất kỳ hình chữ nhật 2 x 3 nào, miễn sao đỉnh đó ko ở ngay gần đỉnh nó đã đứng.Quân Mã hoàn toàn có thể nhảy đầm qua tất cả các quân khác để cho ô nó mong muốn, miễn là ô kia không bị ai chỉ chiếm giữ. Nói nôm mãng cầu là quân Mã không biến thành cản. Khác với cờ tướng tá, địa điểm nhưng quân Mã rất có thể bị cản trường hợp bao gồm quân như thế nào đứng tức thì trước khía cạnh nó, trong cờ vua, nước đi của quân Mã không tồn tại tính chất này.lúc một quân Mã đứng ở cạnh bàn cờ, số nước đi hoàn toàn có thể của chính nó sẽ bị thu hạn hẹp xuống còn những độc nhất là một nửa số nước đi ban đầu. Đặc biệt, giả dụ nó đứng sống 1 trong bốn góc bàn cờ, nó chỉ đi được tối nhiều nhì nước. Câu nói “Mã ngơi nghỉ rìa tương tự như thứ trang trí” trường đoản cú đây mà ra.

*

 

Xuất xđọng bài bác toán

Bài toán quân Mã đi tuần là 1 trong dạng của bài bác toán tổng thể hơn là bài toán thù search lối đi Hamilton vào l‎ý tngày tiết thứ thị, là một trong những bài toán NP-vừa đủ. Bài tân oán kiếm tìm hành trình đóng góp của quân mã là 1 trong những bài xích tân oán rõ ràng của bài bác tân oán kiếm tìm chu trình hamiltonian.

hầu hết trở thành thể của chủ đề này được các đơn vị toán thù học nghiên cứu, trong những số đó gồm đơn vị toán thù học tập Euler. Các đổi khác rất có thể theo các hướng:

Tgiỏi thay đổi form size bàn cờ.

See more: Tết Trung Thu Còn Có Tên Gọi Nào Khác, Bạn Có Biết Tết Trung Thu Còn Gọi Là Gì Không

Biến thành trò nghịch hai bạn theo bốn tưởng này.

Giảm nhẹ các yên cầu trên đường đi của quân Mã.

See more: Khắc Phục Lỗi This Computer Does Not Meet The Minimum Requirements For Installing The Software

BÀI TOÁN QUÂN MÃ ĐI TUẦN TRONG TIN HỌC

1. Ý tưởng cơ bản

Dùng thuật tân oán tảo lui; xuất hành từ là một ô, Hotline số nước đi là t=1 , ta mang lại quân mã demo đi tiếp 1 ô (có 8 nước đi tất cả thể), nếu như ô đi tiếp này chưa trải qua thì lựa chọn làm cho bước tiến tiếp theo. Tại mỗi nước đi soát sổ xem tổng thể nước đi bằng n x n chưa, giả dụ bởi thì mã sẽ trải qua toàn bộ các ô ⇒ ngừng (vì chưng chỉ cần search một giải pháp). Trường đúng theo ngược chở lại, Gọi đệ quy nhằm lựa chọn nước đi tiếp theo sau. Bên cạnh đó, trường hợp trên một bước tra cứu đường đi, ví như không tìm được đường đi tiếp thì thuật toán thù sẽ con quay lui lại nước đi trước và kiếm tìm đường đi khác.

2. Cấu trúc dữ liệu

Mảng board: lưu bàn cờ, trong các số ấy board là ô (i, j); cực hiếm của board là 0 khi quân mã chưa trải qua, và >0 lúc quân mã vẫn trải qua, giá trị board lúc này đó là thiết bị từ bỏ nước đi bên trên hành trình dài.Mảng dr<8>, dc<8>: lưu giữ các độ dời của bước đi kế tiếp, bao gồm tám nước đi hoàn toàn có thể cho địa điểm quân mã hiện giờ. Do kia để đi nước máy i ta chỉ cần cộng thêm dr đến cái cùng dc đến cột.dr<> = -2, -2, -1, -1, 1, 1, 2, 2 dc<> = -1, 1, -2, 2, -2, 2, -1, 1

3. Thuật giải đệ quy

Tại mỗi bước theo lần lượt mang đến quân mã thử tất cả các nước đi sau đó (tám nước đi kế tiếp). Với mỗi bước đi, chất vấn coi ví như nước đi thích hợp lệ (không đi qua và sống trong bàn cờ) thì thử đi nước này. Nếu quân mã đã đi qua hết bàn cờ thì xuất kết quả. trái lại thì Điện thoại tư vấn đệ quy tiếp mang lại địa chỉ new demo bên trên. Lưu ý là mỗi lúc vị trí vẫn đi qua được ghi lại chính bằng chủ yếu vật dụng tự nước đi bên trên bàn cờ. Sau khi không test vị trí này thì cần bỏ lưu lại để chọn giải pháp khác (trường đúng theo quay lui).Nếu coi các ô của bàn cờ là các đỉnh của trang bị thị và những cạnh là nối thân hai đỉnh tương ứng với nhị ô mã giao chân thì thường thấy rằng hành trình của quân mã nên search đang là một đường đi Hamilton. Ta có thể desgin hành trình bởi thuật toán thù quay lui phối hợp với cách thức duyệt ưu tiên Warnsdorff: Nếu gọi deg(x, y) là số ô kề với ô (x, y) và chưa trải qua (kề tại đây theo nghĩa đỉnh kề chứ đọng không phải là ô kề cạnh) thì từ 1 ô ta sẽ không thử xét lần lượt các hướng đi có thể, nhưng ta sẽ ưu tiên demo hướng đi tới ô có deg nhỏ độc nhất vô nhị trước. Trong trường hợp có tồn tại lối đi, cách thức này chuyển động với tốc độ giỏi vời: Với gần như n chẵn trong vòng từ bỏ 6 tới 18, với tất cả vị trí ô xuất phát, vừa phải thời gian tính trường đoản cú cơ hội bắt đầu tới thời gian tìm ra một nghiệm

*


Chuyên mục: Blog