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

cho chúng ta phải xét tất cả N
2
đỉnh của đồ thị tương đương với hàm kt(u, v) được gọi tới
N
2
lần, hơn nữa chương trình lại là đệ quy quay lui nên sẽ có rất nhiều lần gọi đến hàm này
khiến chương trình tốn rất nhiều thời gian và bộ nhớ. Đây là yếu tố chính khiến chương
trình trên tuy có nhanh hơn chương trình duyệt bình thường nhưng chưa đạt được tốc độ
đáng kể. Vậy nên chăng chúng ta hãy dùng một mảng để lưu xem từ đỉnh u có đến được
đỉnh v không? Vấn đề đặt ra là trong trường hợp bàn cờ có kích thước lớn (chẳng hạn 100
x 100) thì đồ thị sẽ có n x n đỉnh, dù có dùng mảng động cũng không thể biểu diễn nổi. Để
ý thấy rằng với một ô bất kỳ chỉ có thể tới nhiều nhất là 8 ô khác, điều này gợi ý ta nên
dùng mảng 2 chiều, một mảng là số đỉnh của đồ thị, mảng kia là mảng 8 phần tử lưu lại 8 ô
có thể tới được từ một đỉnh bất kì.
Khai báo như sau:
Type
Tarr = array [1..8] of integer;
Var
A : array [1..100 * 100] of ^Tarr;
Như vậy trong thủ tục Dat(u), ta sẽ xét tất cả các đỉnh có thể đến từ đỉnh u (nhiều nhất là 8
đỉnh) và các đỉnh này đã được lưu lại trong mảng A.
Caỉ tiến 3:
Với cài đặt trước đây, để kiểm tra những đỉnh nào có thể đến được từ đỉnh u, ta phải xét tất
cả n x n đỉnh. Tuy nhiên chúng ta có thể hạn chế điều này dựa vào nhận xét sau:
Giả sử hai đỉnh u, v của đồ thị ở thế mã giao chân, dễ thấy |u - v| ≤ 2 x n + 1
(*)
, vậy ta chỉ
xét những đỉnh thoả mãn
(*)
.

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

chương trình cài đặt của chúng ta có thể chạy khá nhanh trong trường hợp có nghiệm và
kích thước bàn cờ lên tới 100 x 100. Tôi cũng xin lưu ý khi các bạn đặt cận thời gian nên
để hợp lý (khoảng 6s, tuỳ theo cấu hình máy của bạn. Với cấu hình của máy tôi: PIV,
1.70Ghz thì chỉ cần đặt cận là 3.5s là đủ) để đảm bảo tính chính xác, tốt nhất là xét với
trường hợp kích thước bàn cờ là 100 x 100, ô xuất phát là ô (1, 1) và lấy đó là cận.
Dưới đây là toàn bộ phần cài đặt chương trình:
{$S-}
{$M 65520,0,655360}
program Bai_toan_ma_di_tuan;
const
fi = ′ma.inp ′;
fo = ′ma.out ′;
max = 100;
type
TArr = array [1..8] of integer;
var
b : array [1..max * max] of integer;
a : array [1..max * max] of ^TArr;
n, x, y, count : integer;
L : longint;
function kt(u, v : integer) : boolean;
var
x1, y1, x2, y2 : integer;
begin
x1 := (u - 1) div n + 1;
y1 := (u - 1) mod n + 1;
x2 := (v - 1) div n + 1;
y2 := (v - 1) mod n + 1;
kt := (abs(x1 - x2) * abs(y1 - y2) = 2);
end;

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

dem := 0;
for v := 1 to 8 do
if (a[u]^[v] <> 0) and (b[a[u]^[v]] = 0) then inc(dem);
Dembac := dem;
end;
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;
{thu tuc nay dung chuong trinh khi thoi gian cho phep chay chuong trinh de
tim ra nghiem bi vuot qua}
procedure Error;
begin
writeln('No solution');
halt;
end;
procedure PrintResult;
var
i, j : integer;
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;

b[x] := 1; count := 1;
dat(x);
close(input); close(output);
end .
II. ứng dụng của thuật giải này vào bài toán tìm đường đi Hamilton
Bài toán phát biểu một cách đơn giản như sau:
Cho đồ thị G với n đỉnh và có một số cạnh nối hai đỉnh. Xuất phát từ 1 đỉnh, hãy tìm một
đường đi đi qua tất cả các đỉnh của đồ thị. Đường đi tìm được chính là đường đi Hamilton.