Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 14: Ứng dụng của ngăn xếp

iệc tính toán trongcặp 
dấu (), mọi toán tử còn nằm trên dấu mở ‘(‘ trong ngăn xếp đều được lấy ra để đưa 
vào biểu thức dạng postfix. Do các dấu ngoặc không bao giờ xuất hiện trong biểu 
thức postfix, dấu ‘(‘ được đặt vào ngăn xếp để chờ dấu ‘)’ tương ứng, khi nó được 
lấy ra thì sẽ bị vất bỏ. Dấu ‘)’ để giải quyết cho dấu ‘(‘, và cũng sẽ bị vất đi. 
Các toán tử +, -, *, / đều là các toán tử kết hợp từ trái sang phải. Biểu thức 
a - b - c ( được hiểu là (a-b)-c ) được chuyển đổi thành a b - c - (không phải a b 
c - - ). Với một số toán tử kết hợp từ phải sang trái, chẳng hạn phép tính lũy thừa 
thì 2^2^3 = 2^(2^3)= 2^8=256, không phải (2^2)^3= 4^3=64, thì các xử lý trên 
cần được sửa đổi cho hợp lý. Chương trình hoàn chỉnh chuyển đổi biểu thức dang 
infix sang biểu thức dạng postfix, cũng như việc xử lý đặc biệt cho trường hợp 
toán tử kết hợp phải được xem như bài tập. 
14.4. Giải thuật quay lui (backtracking) 
Ngăn xếp còn được sử dụng trong các giải thuật quay lui nhằm lưu lại các 
thông tin đã từng duyệt qua để có thể quay ngược trở lại. Chúng ta sẽ xem xét các 
ví dụ sau đây. 
14.4.1. Ứng dụng trong bài toán tìm đích (goal seeking). 
Hình 14.1 minh họa cho bài toán tìm đích. Chúng ta có một nút bắt đầu và 
một nút gọi là đích đến. Để đơn giản, chúng ta xét đồ thị không có chu trình và 
chỉ có duy nhất một đường đi từ nơi bắt đầu đến đích. Nhìn hình vẽ chúng ta có 
thể nhận ra ngay đường đi này. Tuy nhiên máy tính cần một giải thuật thích 
hợp để tìm ra được con đường này. 
Chúng ta bắt đầu từ nút 1, sang nút 2 và nút 3. Tại nút 3 có 2 ngã rẽ, giả sử 
chúng ta đi theo đường trên, đến nút 4 và nút 5. Tại nút 5 chúng ta lại đi theo 
đường trên đến nút 6 và nút 7. Đến đây chúng ta không còn đường đi tiếp và cũng 
chưa tìm được đích cần đến, chúng ta phải quay trở lại nút 5 để chọn lối đi khác. 
Tại nút 8 chúng ta lại phải quay lại nút 5 để đi sang nút 9,. Bằng cách này, từ 
nút 13, khi chúng ta tìm được nút 16 thì chúng ta không cần phải quay lui để thử 
với nút 17, 18 nữa. Giải thuật kết thúc khi tìm thấy đích đến. 
Giải thuật của chúng ta cần lưu các nút để quay lại. So sánh nút 3 và nút 5, 
chúng ta thấy rằng trên đường đi chúng ta gặp nút 3 trước, nhưng diểm quay về 
để thử trước lại là nút 5. Do đó cấu trúc dữ liệu thích hợp chính là ngăn xếp với 
Chương 14 – Ứng dụng của ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 373
nguyên tắc FILO của nó. Ngoài ra nếu chúng ta lưu nút 3 và nút 5 thì có sự bất 
tiện ở chỗ là khi quay về, thông tin lấy từ ngăn xếp không cho chúng ta biết các 
nhánh nào đã được duyệt qua và các nhánh nào cần tiếp tục duyệt. Do đó, tại nút 
3, trước khi đi sang 4, chúng ta lưu nút 12, tại nút 5, trước khi đi sang 6 chúng ta 
lưu nút 8 và nút 9, 
Với giải thuật trên chúng ta có thể tìm đến đích một cách dễ dàng. Tuy nhiên, 
nếu bài toán yêu cầu in ra các nút trên đường đi từ nút bắt đầu đến đích thì 
chúng ta chưa làm được. Như vậy chúng ta cũng cần phải lưu cả các nút trên 
đường mà chúng ta đã đi qua. Những nút nằm trên những đoạn đường không dẫn 
đến đích sẽ được dỡ bỏ khỏi ngăn xếp khi chúng ta quay lui. Ở đây chúng ta gặp 
phải một vấn đề cũng tương đối phổ biến trong một số bài toán khác, đó là những 
gì chúng ta bỏ vào ngăn xếp không có cùng mục đích. Có hai nhóm thông tin khác 
nhau: một là các nút nằm trên đường đang đi qua, hai là các nút nằm trên các 
nhánh rẽ khác mà chúng ta sẽ lần lượt thử tiếp khi gặp thất bại trên con đường 
đang đi. Trong những trường hợp như vậy, việc giải quyết rất là dễ dàng: chúng 
ta dùng cách đánh dấu để phân biệt từng trường hợp, khi lấy ra khỏi ngăn xếp, 
căn cứ vào cách đánh dấu này chúng ta sẽ biết phải xử lý như thế nào cho thích 
hợp (Việc duyệt cây theo thứ tự LRN trong chương 10 nếu dùng ngăn xếp cũng là 
một ví dụ). Trong hình 14.1, ký tự B trong ngăn xếp cho biết đó là những nút 
dành cho việc quay lui (Backtracking) để thử với nhánh khác. Vậy khi gặp điểm 
cuối của một con đường không dẫn đến đích, chúng ta dỡ bỏ khỏi ngăn xếp các 
nút cho đến khi gặp một nút có ký tự ‘B’, bỏ lại nút này vào ngăn xếp (không còn 
ký tự ‘B’), và đi tiếp các nút kế tiếp theo nút này. Cuối cùng khi gặp đích, con 
đường được tìm thấy chính là các nút đang lưu trong ngăn xếp mà không có ký tự 
‘B’ ở đầu. 
Hình 14.1- Ví dụ và ngăn xếp minh họa quá trình backtracking. 
 Start node 
The goal2 3 1 
4 5 
6
8
9 10 11
16 1514 13 12 
17 18
7
 end 
 7 end goal
 6 end 11 16 
 B8 B8 8 10 15 
 B9 B9 B9 9 14 
 5 5 5 5 B17
 4 4 4 4 13 
B12 B12 B12 B12 B12 12 
3 3 3 3 3 3 
2 2 2 2 2 2 
1 1 1 1 1 1 
(a) (b) (c) (d) (e) (f)
Chương 14 – Ứng dụng của ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 374
Trên đây là mã giả cho bài toán tìm đích, cấu trúc dữ liệu để chứa đồ thị 
chúng ta sẽ được tìm hiểu sau trong chương 13. 
Algorithm seek_goal(val graph_type graph, val node_type start, 
val node_type goal) 
/* 
pre: graph chứa đồ thị không có chu trình, trong đó có một nút start và một nút goal. 
post: nếu đường đi từ start đến goal được tìm thấy sẽ được in ra theo thứ tự từ goal ngược 
về start 
*/ 
{ 
1. Stack nodes. // node_type là kiểu dữ liệu thích hợp. 
2. node_type current_node = start 
3. boolean fail = FALSE 
4. loop ((current_node chưa là goal) AND (!fail)) 
1. nodes.push(current_node) 
2. if (current_node là điểm rẽ nhánh) 
1. next_node = nút rẽ vào 1 nhánh 
2. loop (còn nhánh chưa đưa vào ngăn xếp) // đưa các nhánh 
// còn lại vào ngăn xếp. 
1. nodes.push(nút rẽ vào 1 nhánh, có kèm ‘B’) 
3. endloop 
3. else 
1. if (tồn tại nút kế) 
1. next_node = nút kế 
2. else 
1. repeat 
1. if (nodes.empty()) 
1. fail = TRUE 
2. else 
1. nodes.top(next_node) 
2. nodes.pop() 
3. endif 
2. until ((fail) OR (next_node có ‘B’)) 
3. endif 
4. endif 
5. current_node = next_node 
5. endloop 
6. if (!fail) 
1. print(“The path to your goal is:”) 
2. print(current_node) // chính là goal 
3. loop (!nodes.empty()) 
1. nodes.top(current_node) 
2. nodes.pop() 
3. if (current_node không có ký tự ‘B’) 
1. print(current_node) 
4. endif 
4. endloop 
7. else 
1. print(“Path not found!”) 
8. endif 
} 
Chương 14 – Ứng dụng của ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 375
14.4.2. Bài toán mã đi tuần và bài toán tám con hậu 
Ví dụ tiếp theo liên quan đến bài toán mã đi tuần. Thực ra bài toán tám con 
hậu được trình bày trong chương 6 cũng hoàn toàn tương tự. Sinh viên có thể 
tham khảo ý tưởng được trình bày dưới đây để giải bài toán tám con hậu sử dụng 
ngăn xếp thay vì đệ quy. 
Với bàn cờ 64 ô, bài toán mã đi tuần yêu cầu chúng ta chỉ ra đường đi cho con 
mã bắt đầu từ một ô nào đó, lần lượt đi qua tất cả các ô, mà không có ô nào lập 
lại hơn một lần. 
Từ một vị trí, con mã có tối đa là 8 vị trí chung quanh có thể đi được. Giải 
thuật quay lui rất gần với hướng suy nghĩ tự nhiên của chúng ta. Trong các khả 
năng có thể, chúng ta thường chọn ngẫu nhiên một khả năng để đi. Và với vị trí 
mới chúng ta cũng làm điều tương tự. Mỗi ô đi qua chúng ta đánh dấu lại. Trong 
quá trình thử này, nếu có lúc không còn khả năng lựa chọn nào khác vì các ô nằm 
trong khả năng đi tiếp đều đã được đánh dấu, chúng ta cần phải lùi lại để thử 
những khả năng khác. Thay vì biểu diễn đường đi cho con mã trên bàn cờ (hình 
14.2a), chúng ta vẽ lại các khả năng đi và thấy chúng không khác gì so với bài 
toán tìm đích (hình 14.2b). Và như vậy, chúng ta thấy cách sử dụng ngăn xếp 
trong những bài toán dạng này hoàn toàn đơn giản và tương tự. Phương pháp 
quay lui trong trường hợp này đôi khi còn được gọi là phương pháp thử sai (trial 
and error method). 
 1 2 3 4 5 6 7 8
1 
2 
3 
4 
5 
6 
7 
8 
 (a) (b) 
Hình 14.2- Bài toán mã đi tuần. 
Hình trên đây minh họa bài toán mã đi tuần với điểm bắt đầu là (7,2). Đích 
đến không cụ thể như bài toán trên, mà đường đi cần tìm chính là đường đi nào 
trong đồ thị này có đủ 64 nút. Bài toán này phụ thuộc vào số ô của bàn cờ và vị 
(7,2)
(5,1)
(8,4)
(5,3)
(4,3) 
(3,2) 
(6,3) 
(3,2) 
(4,1) 
(3,4) 
(4,5) 
(6,5) 
(4,1) 
(7,4) 
Chương 14 – Ứng dụng của ngăn xếp 
Giáo trình Cấu trúc dữ liệu và Giải thuật 376
trí bắt đầu của con mã, khả năng có lời giải và có bao nhiêu lời giải chúng ta 
không xem xét ở đây. Chúng ta chỉ quan tâm đến cách sử dụng ngăn xếp trong 
những bài toán tương tự. Bản chất những bài này đều có cùng một đặc trưng của 
bài toán tìm đích trên một đồ thị không có chu trình. Đích đến có thể là nhiều 
hơn một (tương ứng với nhiều lời giải được tìm thấy) như trong bài toán tám con 
hậu mà cách giải đệ quy được trình bày trong chương 6. Sự khác nhau cơ bản giữa 
chúng chỉ là một vài kỹ thuật nho nhỏ dùng để chuyển từ dữ liệu ban đầu của bài 
toán sang dạng đồ thị biểu diễn các khả năng di chuyển trong quá trình tìm đến 
đích mà thôi.