Đệ quy và phép khử đặc biệt

Một vài phương pháp khử đệ quy đặc biệt

Trần Thành Thắng

Một số bài toán giải bằng phương pháp đệ quy cho ta lời giải rất gọn và có thể ra được lời

giải. Những bài toán giải bằng đệ quy truyền thống như: Tháp HÀ - NỘI, bài toán 8-HẬU,

bài toán MÃ ĐI TUẦN,... Tuy nhiên phương pháp đệ quy khi áp dụng chỉ giải được những

bài toán với cấu trúc dữ liệu nhỏ thường là với N < 30 (hay N x N < 30 x 30). Vì vậy bài

toán đặt ra là có thể giải quyết những bài toán như trên với dữ liệu lớn được hay không? Ví

dụ như: bài toán MÃ ĐI TUẦN và THÁP HÀ-NỘI với bàn cờ cỡ 80x80 hay không? Xin

trình bày một số phương pháp khử đệ quy để giải quyết những bài toán đệ quy truyền

thống.

1. Bài toán MÃ ĐI TUẦN:

Trên bàn cờ NxN (với 5 ≤ N ≤ 100) đặt một quân mã tại một vị trí bất kỳ. Hãy tìm cách

cho mã nhảy theo luật nhảy của quân mã và nhảy hết tất cả các ô trên bàn cờ đó, mỗi ô chỉ

nhảy vào đú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ả các ô trên bàn cò, và tại ô cuối cùng quân mã có thể nhảy về vị

trí của ô xuất phát chính là một chu trình Euler (Nhảy qua tấtt cả các ô, mỗi ô đúng một lần

và nhảy về vị trí xuất phát). Còn nếu vị trí cuối cùng không thể nhảy về vị trí xuất phát

được chính là một đường đi Euler. Ta thử tìm cách bài toán tìm đường đi Euler qua tất cả

các ô của bàn cờ theo luật nhảy của quân mã, mỗi ô chỉ nhảy vào một lần

a. Phương pháp đệ quy truyền thống:

Với phương pháp đệ quy cho bài mã đi tuần này đã có nhiều bài báo đề cập và có nhiều

cảii 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 lại

sơ lược phương pháp truyền thống như sau:

Từ vị trí xuất phát trên bàn cờ NxN ta gán giá trị là 1, theo luật nhảy của quân mã có tối đa

là 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í này xem

vị trí đó có nằm trong bàn cờ hay không, quân mã đã nhảy đến ô này hay chưa nếu chưa

nhảy đến và ô này nằm trong bàn cờ thì nhảy vào ô này. Sau đó dùng đệ quy để tiếp tục

quá trình trên cho đến khi quân mã nhảy hết tất cả các ô.

i. Mô tả:

Ta để ý rằng đáp án của bài toán là mội chuỗi những bước nhảy liên tiếp qua hết tất cả các

ô trên bàn cờ giống như một “đoạn gen” duy nhất gồm nhiền “nhiễm sắc thể” nối tiếp

nhau. Các nhiễm sắc thể tức là các ô của bàn cờ. Hai nhiễm sắc thể liên tiếp được nối với

nhau nếu thỏa mãn luật nhảy của quân mã. Như vậy ta có thể đưa bài toán về một bài toán

khác là từ những 'nhiễm sắc thế” đơn lẻ hãy tìm cách ghép nối chúng lại với nhau sao cho

tạo thàn một 'đoạn gen' duy nhất.

Ví dụ: Ta xem đáp án của bàn cờ 5x5 và “đoạn gen” hoàn chỉnh:

Thư viện tri thức trực tuyến