IKC - Intelligent King of Chess
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.
Thông báo nội bộ IKC
Đề nghị các thành viên IKC khi copy bài viết từ các website khác cần ghi rõ nguồn tư liệu ở cuối bài viết.
Đăng Nhập

Quên mật khẩu

Latest topics
March 2024
SunMonTueWedThuFriSat
     12
3456789
10111213141516
17181920212223
24252627282930
31      

Calendar Calendar

Tìm kiếm
 
 

Display results as :
 


Rechercher Advanced Search

LIÊN KẾT BẠN BÈ
New Page 1 Công báo tỉnh Quảng Trị
Like/Tweet/+1

Bài Toán Mã Đi Tuần

+2
chan_ga
quydnvn2002
6 posters

Go down

Bài Toán Mã Đi Tuần Empty Bài Toán Mã Đi Tuần

Bài gửi by quydnvn2002 Thu Jan 20, 2011 4:49 am

[left][left]Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua ( 8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần.
Bài Toán Mã Đi Tuần Knight's_tour_anim

Có rất nhiều lời giải cho bài toán này, chính xác là 26.534.728.821.064 lời giải trong đó quân mã có thể kết thúc tại chính ô mà nó khởi đầu.

Một hành trình như vật được gọi là hành trình đóng. Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là hành trình mở.

Bài Toán Mã Đi Tuần Knights-Tour-Animation

Nhiều biến thể của chủ đề này được các nhà toán học nghiên cứu, trong đó có nhà toán học Euler. Các biến đổi có thể theo các hướng:

* thay đổi kích thước bàn cờ
* biến thành trò chơi hai người theo tư tưởng này
* giảm nhẹ các yêu cầu trên đường đi của quân mã.

Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong l‎ý thuyết đồ thị, là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình hamiltonian.

Hành trình của quân mã trên nửa bàn cờ đã được giới thiệu dưới dạng thơ trong một tác phẩm tiếng Phạn.

Giải thuật đầu tiên đầy đủ cho bài toán về hành trình của quân mã là Giải thuật Warnsdorff, công bố lần đầu năm 1823 bởi H. C. Warnsdorff

Định lý Schwenk

Cho bàn cờ m × n bất kỳ với m nhỏ hơn hoặc bằng n, không có hành trình đóng nào của quân mã nếu một trong ba điều kiện dưới đây xảy ra:

1. m và n đều là lẻ
2. m = 1, 2, hoặc 4; m và n đều khác 1
3. m = 3 và n = 4, 6, hoặc 8

Điều kiện 1

Dễ dàng chứng minh rằng khi điều kiện 1 thỏa mãn, không thể có hành trình đóng của quân mã.

Trên bàn cờ vua, các ô đen và trắng xen kẽ nhau, một quân mã luôn đi từ một ô tới ô khác màu.

Vì m và n đều là lẻ nên khi đó số các ô đen và trắng trên bàn cờ là khác nhau. Chẳng hạn bàn cờ 5×5 có 13 ô đen và 12 ô trắng.

Một đường đi đóng của quân mã phải có số ô đen và trắng bằng nhau, tổng số ô trên mọi hành trình đóng là số chẵn. Do đó một hành trình đóng không thể đi qua mỗi ô đúng một lần khi số các ô trên bàn cờ là số lẻ.

Điều kiện 2

Điều kiện 2 xảy ra khi độ dài cạnh ngắn là 1, 2, hoặc 4, cũng không thể có đường đi đóng.

Dễ thấy rằng khi m = 1 hoặc 2 không thể có hành trình của quân mã: quân mã không thể đi qua mọi ô (trừ trường hợp bàn cờ 1x1).

Cũng có thể thấy rằng bàn cờ 4 × n không có hành trình đóng của quân mã.

Giả sử một bàn cờ kích thước 4 × n có một hành trình đóng của quân mã. Ta xét hai tập con các ô trên bàn cờ, A1 và B1, A1 gồm các ô thuộc nửa màu đen và B1 gồm các ô màu trắng. Theo quy tắc cờ vua quân mã luôn di chuyến liên tiếp giữa hai tập các ô đen và tập các ô trắng và ngược lại (A1 và B1).
Con mã phải đi xen kẽ giữa màu xanh và màu đỏ.

. Ta lại xét hình minh họa bên phải. Ta định nghiã A2 là tập các ô màu xanh lá cây và B2 là tập các ô mày đỏ trên hình vẽ. Các tập này có số ô bằng nhau. Chú ‎y rằng từ một ô trong A2 quân mã chỉ có thể nhảy sang một ô trong B2. Ngoài ra, vì quân mã phải đi qua tất cả các ô, nên ngược lại khi quân mã đứng ở một ô trong B2 ở bước tiếp theo nó phải nhảy về một ô thuộc A2 (nếu không như vậy số thì trên hành trình kín ấy quân mã phải có hai ô liên tiếp trong A2 điều đó không xảy ra).

Ta sẽ tìm thấy mâu thuẫn trong lập luận sau đây.

Vì có một hành trình đóng của quân mã, nên có thể chọn bất kỳ ô nào làm ô thứ nhất của hành trình

1. Chọn ô thứ nhất thuộc tập
2. Khi đó ô thứ hai phải thuộc
3. ô thứ ba thuộc tập
4. ô thứ tư thuộc tập
5. ...

http://upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Grid4xnColoredSquares.jpg/200px-Grid4xnColoredSquares.jpg[/center]

Như thế hành trình này không chưa các ô thuộc và do đó không thể chứa tất cả các ô trên bàn cờ..

Điều kiện 3

Điều kiện 3 được chứng minh cho từng trường hợp Tuy nhiên, chúng vẫn có thể có lời giải với hành trình mở. Chẳng hạn với bàn cờ 3 x 4 ta có 4 hành trình mở sau:

Bài Toán Mã Đi Tuần Knight_3x4

Bài Toán Mã Đi Tuần 500px-Knight_8x8
quydnvn2002
quydnvn2002

Tổng số bài gửi : 4
Join date : 20/01/2011
Age : 36
Đến từ : TP Đà Nẵng

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by chan_ga Thu Jan 20, 2011 7:07 am

Uhm 1 bài viết rất thú vị
Ngày xưa học ngành IT tớ cũng có học và làm tiểu luận bài toán này... :twisted:
chan_ga
chan_ga

Tổng số bài gửi : 457
Join date : 17/01/2011
Age : 42
Đến từ : Quảng Trị

https://ikc-club.forum-viet.com

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by utan Thu Jan 20, 2011 10:56 am

Đây là một bài toán đơn giản hơn nhiều so với bài toán cho một bàn cờ 5.5 hoặc 6.6 hoặc 7.7.Con mã đứng ở một ô bất kì và tìm số đoạn thẳng nhiều nhất nối các nước đi của con mã trên bàn cờ đó.Điều kiện là các đoạn thẳng nối từ tâm của ô vuông và không được cắt nhau.Dây là một bài toán khó và mất rất nhiều thời gian,giấy mực để giải nó.Một tạp chí toán học của mĩ đã ra câu đố này và nó đã lan rộng ra toàn thế giới.Không có một lời giải tổng quát nên kích thích nhiều bộ óc tham gia.Mình đã tìm ra 24 nước với bàn 7.7 sau một thời gian nghiên cứu.Dám chắc rằng ở việt nam không có nhiều người vượt qua được con số 23 nước^^
utan
utan

Tổng số bài gửi : 975
Join date : 17/01/2011
Age : 33
Đến từ : Nam Định

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by dragontooth1712 Fri May 27, 2011 9:09 am

anh chan_ga oi :( giúp em cái code bài mã đi tuần này dc ko :D em chuẩn bị thuyết trình mà làm mãi ko dc :(

dragontooth1712

Tổng số bài gửi : 3
Join date : 27/05/2011

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by [IKC]INTER Fri May 27, 2011 9:22 am

[b]
[IKC]INTER
[IKC]INTER

Tổng số bài gửi : 108
Join date : 04/05/2011
Age : 35
Đến từ : DAK LAK

https://ikc-club.forum-viet.com

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by chan_ga Fri May 27, 2011 9:24 am

Lên google mà search. Thiếu gì hả em
anh ra trường gần 10 năm rồi. giờ lười lắm. Chuyên môn chính bây giờ là chém gió thôi 140
chan_ga
chan_ga

Tổng số bài gửi : 457
Join date : 17/01/2011
Age : 42
Đến từ : Quảng Trị

https://ikc-club.forum-viet.com

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by [IKC]INTER Fri May 27, 2011 9:26 am

:lol:
[IKC]INTER
[IKC]INTER

Tổng số bài gửi : 108
Join date : 04/05/2011
Age : 35
Đến từ : DAK LAK

https://ikc-club.forum-viet.com

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by dragontooth1712 Fri May 27, 2011 3:43 pm

giúp em đi mà anh gà :(( ko làm dc bài này là bọn em học lại nguyên đám :((((((((((((((((((((

dragontooth1712

Tổng số bài gửi : 3
Join date : 27/05/2011

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by INTER_chan_gai_pro Sat May 28, 2011 8:27 am

anh ra trường gần 5 năm rồi. giờ lười lắm. Chuyên môn chính bây giờ là chém gió thôi 680
INTER_chan_gai_pro
INTER_chan_gai_pro

Tổng số bài gửi : 4
Join date : 27/05/2011
Age : 27
Đến từ : Đắk Lắk.

https://ikc-club.forum-viet.com

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by dragontooth1712 Sat May 28, 2011 4:37 pm

123

dragontooth1712

Tổng số bài gửi : 3
Join date : 27/05/2011

Về Đầu Trang Go down

Bài Toán Mã Đi Tuần Empty Re: Bài Toán Mã Đi Tuần

Bài gửi by Sponsored content


Sponsored content


Về Đầu Trang Go down

Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết