1. Bài toán MÃ ĐI TUẦN:

Trên bàn cờ NxN (với 5<=N<=100) đặt một quân mã tại một vị trí bất kỳ. Hãy tìm cách cho mã nhảy theo luật nhảy của quân mã và nhảy hết tất cả các ô trên bàn cờ đó, mỗi ô chỉ nhảy vào đúng một lần.

2. Phân tích và xây dựng chương trình:

Khi quân mã nhảy hết tất cả các ô trên bàn cờ, và tại ô cuối cùng quân mã có thể nhảy về vị trí của ô xuất phát chính là một chu trình Euler (Nhảy qua tất cả các ô, mỗi ô đúng một lần và nhảy về vị trí xuất phát). Còn nếu vị trí cuối cùng không thể nhảy về vị trí xuất phát được chính là một đường đi Euler. Ta thử tìm cách bài toán tìm đường đi Euler qua tất cả các ô của bàn cờ theo luật nhảy của quân mã, mỗi ô chỉ nhảy vào một lần.

a. Phương pháp đệ quy truyền thống:

Với phương pháp đệ quy cho bài mã đi tuần này đã có nhiều bài báo đề cập và có nhiều cải tiến như số 6-2003, số 7-2003. Tuy nhiên chỉ giải quyết được với N<30. Xin nhắc lại sơ phương pháp truyền thống như sau:

Từ vị trí xuất phát trên bàn cờ NxN ta gán giá trị là 1, theo luật nhảy của quân mã có tối đa là 8 vị trí kế tiếp để quân mã nhảy tới theo luật nhảy. Ta lần lượt kiểm tra 8 vị trí này xem vị trí đó có nằm trong bàn cờ hay không, quân mã đã nhảy đến ô này hay chưa nếu chưa nhảy đến và ô này nằm trong bàn cờ thì nhảy vào ô này. Sau đó dùng đệ quy để tiếp tục quá trình trên cho đến khi quân mã nhảy hết tất cả các ô.

b. Phương pháp mới :“xử lý những đoạn gen”

i. Mô tả:

Ta để ý rằng đáp án của bài toán là mội chuỗi những bước nhảy liên tiếp qua hết tất cả các ô trên bàn cờ giống như một “đoạn gen” duy nhất gồm nhiền “nhiễm sắc thể” nối tiếp nhau. Các nhiễm sắc thể tức là các ô của bàn cờ. Hai nhiễm sắc thể liên tiếp được nối với nhau nếu thỏa mãn luật nhảy của quân mã . Như vậy ta có thể đưa bài toán về một bài toán khác là từ những “nhiễm sắc thể” đơn lẻ hãy tìm cách ghép nối chúng lại với nhau sao cho tạo thành một “đoạn gen” duy nhất.

Ví dụ: Ta xem đáp án của bàn cờ 5x5 và “đoạn gen” hoàn chỉnh:

ii. Định nghĩa các thuật ngữ:

1. Nhiễm sắc thể: là một ô trên bàn cờ NxN

2. Đoạn gen: là một chuỗi gồm một hoặc nhiều nhiễm sắc thể liên tiếp nhau.Hai nhiễm sắc thể liên tiếp nhau trong một đoạn gen thỏa mãn luật nhảy của quân mã. Mỗi đoạn gen sẽ có đầu và đuôi, đoạn gen gồm duy nhất một nhiễm sắc thể thì đầu và đuôi là một.

(hình trên gồm 7 đọan gen có đầu là các ô tô đậm)

3. Nối gen: Ta nối đầu (hay đuôi) của đoạn gen A vào đầu (hay đuôi) của đoạn gen B tạo thành đoạn C thỏa mãn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ đoạn gen A và đoạn gen B.

4. Trộn gen: Ta trộn gen A vào trong gen B như sau: Từ đầu và đuôi của đoạn gen A ta nối vào tại một bước nhảy nào đó của đoạn gen B tạo thành đoạn C thỏa mãn đoạn C là một đoạn gen có các nhiễm sắc thể là các nhiễm sắc thể từ A và B.

5. Cắt gen: Cắt hai đoạn gen A và đoạn B tạo thành hai đoạn gen C và đoạn gen D như sau: ta tìm trên đoạn gen B vị trí để có thể nối đầu (hay đuôi) của đoạn gen A vào và tạo thành đoạn gen C. Phần còn lại của đoạn gen B sẽ bị cắt ra ngoài tạo thành đoạn gen D.

iii. Chứng minh quy tắc:

Với ba công cụ biến đổi những đoạn gen như trên: nối gen, trộn gen và cắt gen ta chứng minh rằng sẽ luôn tìm ra lời giải cho bài toán đặt ra: nối các nhiễm sắc thể riêng lẻ lại và tạo thành một đoạn gen duy nhất

Ta thấy rằng với phương pháp nối gen, từ hai đoạn gen A và đoạn gen B ban đầu sau khi nối tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Như vậy số đoạn gen sau khi thực hiện một phép nối sẽ giảm đi một đoạn.

Trộn đoạn gen A vào đoạn gen B tạo thành đoạn gen C chứa các nhiễm sắc thể có trong A và B. Nên sau khi thực hiêm một phép trộn gen số đoạn gen sẽ giảm đi một đoạn.

Với phép cắt gen, đoạn gen A cắt vào đoạn gen B, tạo thành đoạn gen C và đoạn gen D trong đó đoạn gen C và đoạn gen D chứa các nhiễm sắc thể của đoạn gen A và đoạn gen B. Như vậy số đoạn gen sau khi thực hiện phép cắt gen sẽ không đổi (nhưng nó sẽ tạo ra những trường hợp mới để có thể thực hiện hai phép nối gen và trộn gen.

Vì quân mã tại một vị trí bất kỳ trên bàn cờ có tối thiểu là 2 cách chọn cho bước nhảy kế tiếp nên ta luôn luôn tồn tại hai cặp gen nào đó mà chúng có thể cắt nhau được.

Từ đó ta có thể kết luận rằng số đoạn gen ban đầu N*N đoạn sau nhiều lần biến đổi gen (dùng lần lượt ba phép biến đổi trên) sẽ tạo thành một đoạn gen duy nhất chính là lời giải ta cần tìm.

iv. Tiến hành xây dựng chương trình

Bước 1: Chuyển N*N ô bàn cờ vào các đoạn ghen ta sẽ được N*N đoạn ghen. Mỗi đoạn ghen có chiều dài là 1.

Bước 2: Thược hiện các phép “nối ghen”, “trộn gen” và “cắt gen” cho đến khi chỉ còn một đoạn gen duy nhất. Đoạn gen này có chiều dài là N*N chính là đáp án của bài toán.

Tuy nhiên để tiết kiệm bộ nhớ ta có thể thực hiện theo các sau : Ngay từ khi khởi tạo ta dùng phương pháp đệ quy truyền thống nhưng chỉ cho chương trình đệ quy tới giá trị N*(N-1), sau đó mới áp dụng phương pháp xử lý các đoạn gen như sau.

Bước 1. Ban đầu ta dùng cách đệ quy truyền thống cho mã nhảy đến một giá trị là N*(N-1) thì dừng lại. (Còn lại N ô chưa điền)

Bước 2. Lần lượt điền những ô chưa điền với những giá tri tăng dần N*(N-1)+1, N*(N-1)+2,... đến N*N thì dừng lại (nhu vậy tất cả các ô đều được điền nhưng không đúng luật nhảy của quân mã).

Bước 3. Biến đổi mảng mảng 2 chiều đã điền thành các đoạn gen

Bước 4. Sau đó ta phân tích bàn cờ hai chiều (đã đánh số từ 1=>NxN) thành các đoạn gen.

Bước 5. Tiến hành xử lý các đoạn gen dùng lần lượt 3 công cụ “nối gen”, “trộn gen” và “cắt gen” để nối các đọan gen thành một đoạn gen duy nhất.

Bước 6. Xuất kết quả ra file.

Chương trình minh họa được viết bằng ngôn ngữ Pascal (Free Pascal Compiler Version 1.0.4) load trên trang web: http://www.freepascal.org/
Khi viết trong Free Pascal bộ nhớ có thể mở rộng phù hợp cho việc khai báo của bài toán trên.

Chương trình viết bằng ngôn ngữ Visual C (cho phép N<=87) vớn ngôn ngữ Free Pascal (N<=80 có thể khai báo maxN=90 nhưng khi khởi động có thể hơi lâu).

v. Những lưu ý khi khi xây dựng chương trình

Khi “nối gen” và “trộn gen” không thể thực hiện được nữa chương trình thường chạy “cắt gen”. Sau khi đoạn gen A cắt đoạn gen B và sinh ra đoạn gen C và gen D thì ta phải đảo ngược đoạn gen C này để tránh trường hợp đoạn gen C lại cắt đoạn gen D sẽ sinh ra đoạn gen A và B thì chương trình sẽ bị lặp.

Tuy nhiên ta không thể dự đoán trước được có những trường hợp bị lặp đặc biệt nào đó nên cách giải quyết tốt nhất là khi đoạn gen A cắt đoạn gen B ta tìm hết các vị trí cắt trên B mà A có thể cắt (tối đa là 8 vị trí), nếu có vị trí cắt ta lấy ngẫu nhiên một vị trí trên B trong các vị trí có thể đó để làm điểm cắt. Như thế chương trình sẽ tránh được những trường hợp lặp đặc biệt nào đó.

vi. Đánh giá và mở rộng bài toán:

- Với chương trinh đệ quy truyền thống cũng như đệ quy có tri thức (thuật tóan Warnsdorff) thì chỉ giải quyết đuợc vói những bàn cờ kích thước nhỏ và thời giai đưa ra kết quả khá lâu. Không những thế một số vị trí xuất phát và hướng nhảy của quân mã trên bàn cờ có thể sẽ đưa ra lời giải trong thời gian khá lâu cho dù N bé vì đệ quy chính là “vét cạn” các trường hợp nếu đáp án nằm ở vị trí cuối của các lần lặp đệ quy ban đầu.

- Với cách giải quyết qua các “đoạn gen” khắc phục được những điểm yếu của đệ quy truyền thống. Kích thước của bàn cờ có khả năng đạt đến là 87x87 khi sử dụng mảng lưu trữ tĩnh. Kích thức của bàn cờ có thể lớn hơn nữa nếu tổ chức dữ liệu bằng danh sách liên kết.

3. Bài tập:

1. Lập trình giải bài toán tìm đường đi Euler dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng tĩnh.

2. Lập trình giải bài toán tìm đường đi Euler (hay bài MÃ ĐI TUẦN) dùng cách “xử lý các đoạn gen” như trên dùng cấu trúc lưu trữ mảng động.

4. Tài liệu tham khảo:

Giáo trình trí tuệ nhân tạo – Cấu trúc dữ liệu + thuật giải di truyền = Lập trình tiến hóa Ts. Nguyễn Đình Thúc (NXB LĐ-XH)