Thuật toán hoàn chỉnh cho bài toán mã đi tuần và một ứng dụng quan
trọng
Công Hiệp
Trong số báo tháng 6- 2003, có bài ″thuật toán hiệu quả giải bài toán mã đi tuần″ của tác
giả Nguyễn Văn Trung, đây là một cách giải rất hay bởi bài toán này từ trước đến nay chỉ
được xem xét dưới góc độ của một bài đệ quy quay lui bình thường và với kích thước quá
hạn chế. Hơn thế nữa thuật giải này còn cho thấy đệ quy quay lui có thể giải được những
bài toán với kích thước tương đối nếu cài đặt tốt. Về mặt ý nghĩa và hiệu quả là thế, tuy
nhiên cài đặt của thuật toán này tôi thấy còn hơi thô sơ, chưa có sự chau chuốt về thuật
toán và kỹ thuật lập trình. Như tác giả bài viết đó đã nhận xét, với bài toán đó thì chỉ có thể
giải được cho kích thước bàn cờ là không quá 30 (trong trường hợp có nghiệm), không
những thế còn rất chậm. Sau khi nghiên cứu thuật giải này (thực chất là quay lui kết hợp
với phương pháp duyệt ưu tiên Warnsdorff), tôi xin được trình bày những cải tiến có thể
của thuật toán đã được trình bày và một ứng dụng có thể nói khá hay vào việc giải một bài
toán đã được nhiều người biết đến: ″bài toán tìm đường đi Hamilton″ của một đồ thị. Việc
cải tiến dưới giúp chương trình chạy được với N = 100 !
I. Cải tiến chương trình
Vẫn dựa trên tư tưởng của thuật toán đó là coi bàn cờ kích thước n x n như một đồ thị n * n
đỉnh. Để hiểu một cách cặn kẽ bài viết này, các bạn nên tham khảo bài viết của tác giả đã
được đăng trên số báo tháng 6.
Cải tiến 1:
Trước hết, xét một đỉnh u của đồ thị, chúng ta có thể dễ thấy là đỉnh này là biểu diễn của ô
(x, y) trong đó:
x := (u- 1) div n + 1;
y := (u- 1) mod n + 1;
với x là dòng và y là cột và hoàn toàn không phải xét các trường hợp như trước, các bạn
nên kiểm tra tính đúng đắn của công thức này bằng việc vẽ hình bàn cờ để minh hoạ.
Cải tiến 2:
Để tránh cho chương trình của chúng ta chạy chậm (vì cài đặt của chúng ta là đệ quy quay
lui), phải hết sức tránh việc gọi các chương trình con nhiều lần trong các thủ tục chính,
điều này cài đặt của tác giả chưa đạt được. Do trong thủ tục Dat(u), vòng lặp ban đầu làm

Cải tiến 4:
Để ý kỹ hơn chút nữa, trong hàm Bacnhonhat(u), bậc của đỉnh v ở thế mã giao chân với
đỉnh u sẽ phải tính hai lần do đệ quy không có tính lưu lại, vậy ta có thể dùng một biến
trung gian để số lần gọi đệ quy hàm này giảm đi (về mặt thời gian, nếu bài toán ra với kích
thước nhỏ của bàn cờ thì cải thiện này không đáng kể, tuy nhiên với kích thước của bàn cờ
lớn thì lượng thời gian sử dụng được tiết kiệm quá nhiều). Cũng xin lưu ý các bạn khi lập
trình nên tránh gọi ít lần đệ quy nếu trong quá trình xử lý có một đối tượng nào đó được
gọi đệ quy nhiều lần thì nên dùng thêm biến trung để lưu lại. Có thể minh hoạ lại đoạn
chương trình đó như sau:
function Bacnhonhat(u : integer) : byte;
var
v : integer;
tg, C : byte;
begin
tg := 100;
for v := 1 to 8 do
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) then
begin
C := Dembac(a[u]^[v]);
if tg > C then tg := C;
end;
Bacnhonhat := tg;
end ;
(Xin các bạn xem kỹ cài đặt ở sau để hiểu rõ, ở đây chỉ minh họa đó là dùng biến C để lưu
kết quả của hàm Dembac(u) tránh gọi lại nó hai lần).
Cải tiến 5:
ở cuối bài viết, tác giả có nêu ra là trong trường hợp không có đường đi thì chưa xử lý
được thì trong bài này chúng ta sẽ sử dụng thêm một biến đó là biến thời gian, và ta dùng
cận này để đánh giá. Khi chương trình của chúng ta chạy quá cận thời gian cho phép thì ta
dừng ngay chương trình và thông báo là không có đường đi. Điều này cũng dể hiểu bởi

procedure init;
var
u, i, m1, m2 : integer;
j : byte;
begin
for i := 1 to n * n do
begin
new(a[i]);
fillchar(a[i]^, sizeof(a[i]^), 0);
end;
for u := 1 to n * n do
begin
if u - 2 * n - 1 < 0 then m1 := 0
else m1 := u - 2 * n - 1;
if u + 2 * n + 1 > n * n then m2 := n * n
else m2 := u + n * 2 + 1;
j := 0;
for i := m1 to m2 do
if kt(u, i) then
begin
inc(j);
a[u]^[j] := i;
end;
end;
end;
function Dembac(u : integer) : byte;
var
v : integer;
dem : byte;
begin

for i := 1 to n * n do
if i mod n = 0 then writeln(b[i] : 5)
else write(b[i] : 5);
writeln('Time : ', (MemL[0 : $46C] - L)/18.21 : 3 : 1);
close(output);
halt;
end;
procedure dat(u : integer);
var
v : byte;
begin
if (MemL[0 : $46C] - L)/18.21 > 3 then Error;
for v := 1 to 8 do {xet tat ca cac dinh den duoc tu dinh u}
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0)
and (Dembac(a[u]^[v]) = Bacnhonhat(u)) then
begin
inc(count); b[a[u]^[v]] := count;
if count = n * n then PrintResult
else
dat(a[u]^[v]);
dec(count); b[a[u]^[v]] := 0;
end;
end;
begin
assign(input, fi); reset(input);
assign(output, fo); rewrite(output);
readln(n, x, y);
L := MemL[0 : $46C];
Init;
x := (x - 1) * n + y;