Wikipedia

Khác biệt giữa bản sửa đổi của “Bài toán mã đi tuần”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
n clean up, General fixes, replaced: → (19) using AWB
n clean up, replaced: → (7) using AWB
Dòng 15:
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]].<ref>A. Conrad, T. Hindrichs, H. Morsy, and I. Wegener. "[https://www.sciencedirect.com/science/article/pii/0166218X9200170Q Solution of the Knight's Hamiltonian Path Problem on Chessboards]." ''Discrete Applied Math'', volume 50, no.2, pp.125-134. 1994. {{DOI|10.1016/0166-218X(92)00170-Q}}</ref>
 
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]].<ref>{{chú thích sách|author = Satyadev, Chaudhary|title = Kavyalankara of Rudrata (Sanskrit Text, with [[Tiếng Hindi|Hindi]] translation);|publisher = Parimal Sanskrit Series No. 30|location = Delhi}}</ref>
 
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]].
Dòng 50:
 
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
# Chọn ô thứ nhất thuộc tập <math> A_1 \cap A_2 </math>.
# Khi đó ô thứ hai phải thuộc <math> B_1 \cap B_2 </math>.
# Ô thứ ba thuộc tập <math> A_1 \cap A_2 </math>.
# Ô thứ tư thuộc tập <math> B_1 \cap B_2 </math>.
#...
 
Như thế hành trình này không chưa các ô thuộc <math> A_1 \cap B_2 </math> và <math> B_1 \cap A_2 </math> do đó không thể chứa tất cả các ô trên bàn cờ..
 
=== Điều kiện 3 ===
Lấy từ “https://vi.wikipedia.org/wiki/Bài_toán_mã_đi_tuần”