Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 6: Phương pháp quay lui

-----} 
fillchar(d,sizeof(d),0); 
k := 1; {k – dem so dinh da chon } 
v[k] := s; {dinh xuat phat } 
d[s] := 1; {da tham dinh s } 
repeat 
if v[k] = t then {den dich } 
begin 
ket(k); {ghi ket qua: giai trinh duong di } 
 exit; 
end; 
if k < 1 then {vo nghiem } 
begin 
 ket(0); 
 exit; 
end; 
 i := Tim; 
 {tu dinh v[k] tim 1 dinh chua tham i } 
if i > 0 then 
 {neu tim duoc, i > 0, di den dinh i } 
 NhaChi(i) 
else CuonChi; 
 {neu khong tim duoc, } 
 { i = 0: lui 1 buoc - bo dinh v[k] } 
until false; 
end; 
Thủ tục Doc - đọc dữ liệu từ tệp MECUNG.INP vào mảng hai chiều a. Đây chính 
là ma trận kề của đồ thị biểu diễn mê cung. Mảng a sẽ đối xứng vì mê cung là đồ thị vô 
hướng. Đây cũng chính là lí do giải thích dữ liệu vào chỉ cho dưới dạng nửa trên của ma 
trận kề. 
(*------------------------- 
 Doc du lieu 
------------------------*) 
procedure Doc; 
var i,j: byte; 
begin 
Sáng tạo trong Thuật toán và Lập trình Tập I 
185 
assign(f,fn); 
reset(f); 
read(f,n,s,t); 
fillchar(a,sizeof(a),0); 
if (n MN) then exit; 
for i := 1 to n-1 do 
 for j := i+1 to n do 
 begin 
 read(f,a[i,j]); 
 a[j,i] := a[i,j]; {lay doi xung } 
 end; 
close(f); 
end; 
Thủ tục Xem – hiển thị dữ liệu trên màn hình để kiểm tra việc đọc có đúng không. 
Với những người mới lập trình cần luôn luôn viết thủ tục Xem. Khi nộp bài thì có thể bỏ 
lời gọi thủ tục này. Các hằng kiểu string bl = #32 là mã ASCII của dấu cách, 
hằng nl = #13#10 là một xâu chứa hai kí tự điều khiển có mã ASCII là xuống dòng 
#13, tức là ứng với phím RETURN và đưa con trỏ màn hình về đầu dòng #10. Khi đó 
lệnh writeln sẽ tương đương với lệnh write(nl). 
(*------------------------ 
 Xem du lieu 
-------------------------*) 
procedure xem; 
var i,j: byte; 
begin 
write(nl,n,bl,s,bl,t,nl); 
for i := 1 to n do 
begin 
 for j := 1 to n do 
 write(a[i,j],bl); 
 write(nl); 
end; 
end; 
Thủ tục Ket(k) - ghi đường đi v[1..k] từ s đến t tìm được vào tệp output. 
Ket(0): thông báo vô nghiệm. 
(*------------------------------ 
 Ghi ket qua. 
 k = 0: vo nghiem 
 k > 0: co duong tu s den t 
 gom k canh 
------------------------------*) 
procedure Ket(k: byte); 
var i: byte; 
begin 
assign(g,gn); rewrite(g); 
write(g,k,nl); 
if k > 0 then 
begin 
 write(g,v[1]); 
 for i := 2 to k do 
 write(g,bl,v[i]); 
Sáng tạo trong Thuật toán và Lập trình Tập I 
186 
end; 
close(g); 
end; 
Hàm Tim - từ đỉnh v[k] tìm một bước đi đến đỉnh i. Điều kiện: i phải là đỉnh chưa 
thăm và đương nhiên có cạnh đi từ v[k] đến i, nghĩa là giá trị a[v[k], i] trong ma trận kề 
phải là 1. Ta dùng một mảng d đánh dấu đỉnh i đã thăm chưa. d[i] = 0 – đỉnh i chưa 
thăm, d[i] = 1 – đỉnh i đã thăm và đã từng được chọn để đưa vào mảng v là mảng giải 
trình đường đi. Nếu tìm kiếm thành công ta gán cho hàm Tim giá trị i, chính là đỉnh cần 
đến. Ngược lại, khi việc tìm kiếm thất bại, nghĩa là không tìm được đỉnh i để có thể đi 
từ đỉnh v[k] đến đó, ta gán cho hàm Tim giá trị 0. 
Ta lưu ý là mỗi đỉnh chỉ đi đến không quá một lần. Đương nhiên khi lùi thì ta buộc 
phải quay lại đỉnh đã đến, do đó, chính xác hơn ta phải gọi d[i]=1 là giá trị đánh dấu khi 
tiến đến đỉnh i. 
(*------------------------------------- 
Tu dinh v[k] tim duoc mot buoc di 
den dinh i. Dieu kien: 
 d[i] = 0 - dinh i chua xuat hien 
 trong lich trinh v 
 d[i] = 1 - dinh i da xuat hien 
 trong lich trinh v. 
--------------------------------------*) 
function Tim: byte; 
var i: byte; 
begin 
Tim := 0; 
for i := 1 to n do 
if d[i] = 0 then {dinh i chua tham } 
if a[v[k],i] = 1 {co duong tu v[k] den i } 
 then 
begin 
 Tim := i; 
 exit; 
end; 
end; 
Nếu tìm được đỉnh chưa thăm thoả các điều kiện nói trên ta tiến thêm một bước 
theo cạnh (v[k], i). Ta cũng đánh dấu đỉnh i là đã thăm bằng lệnh gán d[i]: = 1. Đó là 
nội dung của thủ tục NhaChi (nhả chỉ). 
(*--------------------------- 
 Di 1 buoc tu v[k] den i 
----------------------------*) 
procedure NhaChi(i: byte); 
begin 
inc(k); 
v[k] := i; {tien them 1 buoc } 
d[i] := 1; {danh dau dinh da qua } 
end; 
Nếu từ đỉnh v[k] ta không tìm được đỉnh nào để đi tiếp thì ta phải thực hiện thủ tục 
CuonChi (cuộn chỉ) như dưới đây. Thủ tục này chỉ đơn giản là lùi một bước từ đỉnh 
Te-dây hiện đang đứng trở về đỉnh trước đó, nếu có, tức là k  1, ta đánh dấu cạnh (v[k - 
1], v[k]) là đã đi hai lần. Ta nhận xét rằng, nếu không tính lần trở lại một đỉnh khi phải 
Sáng tạo trong Thuật toán và Lập trình Tập I 
187 
lùi một bước thì mỗi đỉnh trong mê cung chỉ cần thăm tối đa là một lần, do đó thay vì 
đánh dấu cạnh ([v[k - 1], v[k]) ta chỉ cần đánh dấu đỉnh v[k] là đủ. 
(*------------------------------------- 
 Lui 1 buoc vi tu dinh v[k] khong 
 co kha nang nao dan den ket qua 
-------------------------------------*) 
procedure CuonChi; 
begin 
dec(k); 
end; 
(* Pascal *) 
(*------------------------------------ 
 MECUNG.PAS Tim duong trong me cung 
-------------------------------------*) 
{$B-} 
uses crt; 
const 
 MN = 100; {So dinh toi da } 
 fn = 'MECUNG.INP'; {input file } 
 gn = 'MECUNG.OUT'; {output file } 
 nl = #13#10; {xuong dong moi } 
 bl = #32; {dau cach } 
type 
 MB1 = array[0..MN] of byte; 
 MB2 = array[0..MN] of MB1; 
var 
 a: MB2; {ma tran ke, doi xung } 
 v: MB1; {vet tim kiem } 
 d: MB1; {danh dau dinh da chon } 
 n: byte; {so dinh } 
 s: byte; {dinh xuat phat } 
 t: byte; {dinh ket thuc } 
 k: byte; {buoc duyet } 
 f,g: text; {f: input file; g: output file} 
(*----------------------- 
 Doc du lieu 
------------------------*) 
procedure Doc; tự viết 
(*------------------------ 
 Xem du lieu 
-------------------------*) 
procedure xem; tự viết 
(*--------------------------------------- 
 Ghi ket qua. 
 k = 0: vo nghiem 
 k > 0: co duong tu s den t gom k canh 
----------------------------------------*) 
procedure Ket(k: byte); tự viết 
(*-------------------------------------------- 
 Tu dinh v[k] tim duoc mot buoc di den dinh i. 
 Dieu kien: 
Sáng tạo trong Thuật toán và Lập trình Tập I 
188 
 d[i] = 0 - dinh i chua xuat hien 
 trong lich trinh v 
 d[i] = 1 - dinh i da xuat hien 
 trong lich trinh v, 
---------------------------------------------*) 
function Tim: byte; tự viết 
(*--------------------------- 
 Di 1 buoc tu v[k] den i 
----------------------------*) 
procedure NhaChi(i: byte); tự viết 
(*------------------------------------- 
Lui 1 buoc vi tu dinh v[k] khong co kha nang nao 
dan den ket qua 
-------------------------------------*) 
procedure CuonChi; tự viết 
(*------------------------------- 
 Tim duong trong me cung 
 (Thuat toan Soi chi Arian) 
 s: dinh xuat phat 
 t: dinh ket. 
-------------------------------*) 
procedure MC; tự viết 
BEGIN 
MC; write(nl,'fini'); 
END. 
Với thí dụ đã cho trong đề bài, bạn hãy chạy thử chương trình MECUNG.PAS với 
hai dữ liệu kiểm thử, một dữ liệu kiểm thử có nghiệm và một dữ liệu kiểm thử vô 
nghiệm. 
Chú ý 
Đường đi tìm được không phải là đường ngắn nhất. Trong chương 7 ta sẽ dùng 
thuật giải Dijkstra để tìm đường đi ngắn nhất. 
// C# 
using System; 
using System.IO; 
namespace SangTaoT1 
{ 
 /*------------------------------------ 
 * Tim duong trong me cung 
 * -----------------------------------*/ 
 class MeCung 
 { 
 static string fn = "MeCung.INP"; 
 static string gn = "MeCung.OUT"; 
 static int mn = 200; // So dinh toi da 
 static int[] v; // vet duong di 
 static int[] d;// dinh dang xet 
 static int[,] c; // ma tran ke 0/1 
 static int n = 0; // So dinh 
 static int s = 0; // Dinh xuat phat 
 static int t = 0; // Dinh ket 
 static int k = 0; // buoc duyet 
Sáng tạo trong Thuật toán và Lập trình Tập I 
189 
 static void Main() 
 { 
 Doc(); Show(); Ghi(MC()); 
 // Doc lai de kiem tra 
 Console.WriteLine("\n Kiem tra"); 
 Console.WriteLine("\n Input: \n"); 
 Console.WriteLine(File.ReadAllText(fn)); 
 Console.WriteLine("\n Output: "); 
 Console.WriteLine(File.ReadAllText(gn)); 
 Console.WriteLine("\n Fini "); 
 Console.ReadLine(); 
 } // Main 
 static void Doc() 
 { 
 int[] a = Array.ConvertAll( 
 ((File.ReadAllText(fn)).Trim()). 
 Split(new char[] { ' ', '\n', '\r', '\t', '\0' }, 
 StringSplitOptions.RemoveEmptyEntries), 
 new Converter(int.Parse)); 
 n = a[0]; // so dinh 
 s = a[1]; // dinh xuat phat 
 t = a[2]; // dinh ket 
 c = new int[n + 1, n + 1]; 
 // c ma tran ke 
 v = new int[n + 1]; // vet duong di 
 d = new int[n + 1]; 
 // d[i] = 1: da tham dinh i 
 k = 2; 
 for (int i = 1; i <= n; ++i) 
 { 
 c[i, i] = 0; 
 for (int j = i + 1; j <= n; ++j) 
 c[i, j] = c[j,i] = a[++k]; 
 } 
 } 
 // Hien thi de kiem tra 
 // thu tuc doc du lieu 
 static void Show() 
 { 
 Console.WriteLine("\n" + n + " " 
 + s + " " + t); 
 for (int i = 1; i <= n; ++i) 
 { 
 Console.WriteLine(); 
 for (int j = 1; j <= n; ++j) 
 Console.Write(c[i, j] + " "); 
 } 
 } 
 static void Ghi(bool Ket) 
 { 
 StreamWriter f = File.CreateText(gn); 
 if (Ket) // co nghiem 
Sáng tạo trong Thuật toán và Lập trình Tập I 
190 
 { 
 f.WriteLine(k); 
 for (int i = 1; i <= k; ++i) 
 f.Write(v[i] + " "); 
 } 
 else f.WriteLine(0);// vo nghiem 
 f.Close(); 
 } 
 static bool MC() 
 { 
 Array.Clear(v, 0, v.Length); 
 Array.Clear(v, 0, v.Length); 
 k = 1; // Buoc duyet 
 v[k] = s; d[s] = 1; 
 // danh dau phong da den 
 int phong = 0; 
 do 
 { 
 if (v[k] == t) 
 return true; // den dich 
 if (k < 1) 
 return false; // het cach 
 if ((phong = Tim()) > 0) 
 { // Tien them 1 buoc 
 // nha chi, danh dau 
 v[++k] = phong; d[phong] = 1; 
 } 
 else --k; // lui 
 } while (true); 
 } 
 // Tu phong v[k] tim duoc 
 //mot duong sang phong khac 
 static int Tim() 
 { 
 for (int j = 1; j <= n; ++j) 
 if (d[j] == 0)// phong j chua tham 
 if (c[v[k], j] > 0) 
 //co hanh lang toi j 
 return j; 
 return 0; 
 } 
 } // MeCung 
} // SangTao1