Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 3: Các ứng dụng của các lớp cấu trúc dữ liệu - Chương 14: Ứng dụng của ngăn xếp
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
Phaàn 3 – CAÙC ÖÙNG DUÏNG CUÛA CAÙC LÔÙP CTDL
Chöông 14 – ÖÙNG DUÏNG CUÛA NGAÊN XEÁP
Döïa treân tính chaát cuûa caùc giaûi thuaät, caùc öùng duïng cuûa ngaên xeáp coù theå ñöôïc
chia laøm boán nhoùm nhö sau: ñaûo ngöôïc döõ lieäu, phaân tích bieân dòch döõ lieäu, trì
hoaõn coâng vieäc vaø caùc giaûi thuaät quay lui. Moät ñieàu ñaùng chuù yù ôû ñaây laø khi xem
xeùt caùc öùng duïng, chuùng ta khoâng bao giôø quan taâm ñeán caáu truùc chi tieát cuûa ngaên
xeáp. Chuùng ta luoân söû duïng ngaên xeáp nhö moät caáu truùc döõ lieäu tröøu töôïng vôùi caùc
chöùc naêng maø chuùng ta ñaõ ñònh nghóa cho noù.
14.1. Ñaûo ngöôïc döõ lieäu
Trong phaàn trình baøy veà ngaên xeáp chuùng ta ñaõ ñöôïc laøm quen vôùi moät ví duï
xuaát caùc phaàn töû theo thöù töï ngöôïc vôùi thöù töï nhaäp vaøo. ÔÛ ñaây chuùng ta tieáp tuïc
tham khaûo theâm öùng duïng ñoåi moät soá thaäp phaân sang moät soá nhò phaân.
ÖÙng duïng ñoåi soá thaäp phaân sang soá nhò phaân
Giaûi thuaät döôùi ñaây chuyeån ñoåi soá thaäp phaân decNumsang moät soá nhò phaân.
1
2
loop (decNum > 0)
1
digit = decNum % 2
2
3
xuaát (digit)
decNum = decNum / 2
endloop
Tuy nhieân caùc kyù soá ñöôïc xuaát ra seõ laø thöù töï ngöôïc cuûa keát quaû maø chuùng ta
mong muoán. Chaúng haïn soá 19 leõ ra phaûi ñöôïc ñoåi thaønh 10011 chöù khoâng phaûi laø
11001. Thöïc laø deã daøng neáu chuùng ta söû duïng ngaên xeáp ñeå khaéc phuïc ñieàu naøy.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
365
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
void DecimalToBinary(val int decNum)
post: soá nhò phaân töông ñöông vôùi soá thaäp phaân decNumseõ ñöôïc xuaát ra.
uses: söû duïng lôùp Stackñeå ñaûo ngöôïc thöù töï caùc soá 1 vaø soá 0.
{
1. Stack<int> reverse; // Khôûi taïo ngaên xeáp ñeå chöùa caùc kyù soá 0 vaø 1.
2. loop (decNum > 0)
1. digit = decNum % 2
2. reverse.push(digit)
3. decNum = decNum / 2
3. endloop
4. loop (!reverse.empty())
1. reverse.top(digit)
2. reverse.pop()
3. xuaát(digit)
endloop
5
}
Moät ñieàu deã nhaän thaáy laø neáu chuùng ta duøng moät maûng lieân tuïc (array trong
C++) ñeå chöùa caùc soá digit roài tìm caùch in theo thöù töï ñaûo laïi, chuùng ta seõ phaûi
tieâu toán söùc löïc vaøo vieäc quaûn lyù caùc bieán chæ soá chaïy treân maûng. Ñoù laø ñieàu neân
traùnh. Vieäc tuaân thuû lôøi khuyeân naøy giuùp chuùng ta coù thoùi quen toát khi ñuïng phaûi
nhöõng baøi toaùn lôùn hôn: chuùng ta coù theå taäp trung vaøo giaûi quyeát nhöõng vaán ñeà
chính cuûa baøi toaùn.
14.2. Phaân tích bieân dòch (parsing) döõ lieäu
Vieäc phaân tích döõ lieäu thöôøng bao goàm phaân tích töø vöïng vaø phaân tích cuù
phaùp. Chaúng haïn, ñeå chuyeån ñoåi moät chöông trình nguoàn ñöôïc vieát bôûi moät ngoân
ngöõ naøo ñoù thaønh ngoân ngöõ maùy, trình bieân dòch caàn taùch chöông trình aáy ra
thaønh caùc töø khoùa, caùc danh hieäu, caùc kyù hieäu, sau ñoù tieán haønh kieåm tra tính
hôïp leä veà töø vöïng, veà cuù phaùp. Trong vieäc kieåm tra cuù phaùp thì vieäc kieåm tra caáu
truùc khoái loàng nhau moät caùch hôïp leä laø moät trong nhöõng ñieàu coù theå ñöôïc thöïc
hieän deã daøng nhôø ngaên xeáp.
ÖÙng duïng kieåm tra tính hôïp leä cuûa caùc caáu truùc khoái loàng nhau
Ñeå kieåm tra tính hôïp leä cuûa caùc caáu truùc khoái loàng nhau, chuùng ta caàn kieåm
tra caùc caëp daáu ngoaëc nhö [], {}, () phaûi tuaân theo moät thöù töï ñoùng môû hôïp leä, coù
nghóa laø moãi khoái caàn phaûi naèm goïn trong moät khoái khaùc, neáu coù.
Lyù do söû duïng ngaên xeáp ñöôïc giaûi thích nhö sau: theo thöù töï xuaát hieän, moät
daáu ngoaëc môû xuaát hieän sau caàn phaûi coù daáu ngoaëc ñoùng töông öùng xuaát hieän
tröôùc. Ví duï […(…)…] laø hôïp leä, […(…]…) laø khoâng hôïp leä. Ñieàu naøy roõ raøng lieân quan
ñeán nguyeân taéc FILO cuûa ngaên xeáp. Moãi caáu truùc khoái seõ ñöôïc chuùng ta bieát ñeán
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
366
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
khi baét ñaàu gaëp daáu ngoaëc môû cuûa noù, vaø chuùng ta seõ chôø cho ñeán khi naøo gaëp daáu
ngoaëc ñoùng töông öùng cuûa noù thì xem nhö chuùng ta ñaõ duyeät qua caáu truùc ñoù. Caùc
daáu ngoaëc môû maø chuùng ta gaëp, chuùng ta seõ laàn löôït löu vaøo ngaên xeáp, neáu ñoaïn
chöông trình hôïp leä, thì chuùng ta cöù yeân taâm raèng caùc daáu ngoaëc ñoùng töông öùng
cuûa chuùng seõ xuaát hieän theo ñuùng thöù töï ngöôïc laïi. Nhö vaäy, moãi khi gaëp moät daáu
ngoaëc ñoùng, vieäc caàn laøm laø laáy töø ngaên xeáp ra moät daáu ngoaëc môû vaø so truøng.
Vaên baûn caàn kieåm tra thöôøng laø moät bieåu thöùc tính toaùn hay moät ñoaïn chöông
trình.
Giaûi thuaät: Ñoïc ñoaïn vaên baûn töøng kyù töï moät. Moãi daáu ngoaëc môû (, [, { ñöôïc
xem nhö moät daáu ngoaëc chöa so truøng vaø ñöôïc löu vaøo ngaên xeáp cho ñeán khi gaëp
moät daáu ngoaëc ñoùng ), ], } so truøng töông öùng. Moãi daáu ngoaëc ñoùng caàn phaûi so
truøng ñöôïc vôùi daáu ngoaëc môû vöøa ñöôïc löu cuoái cuøng, vaø nhö vaäy daáu ngoaëc môû
naøy seõ ñöôïc laáy ra khoûi ngaên xeáp vaø boû ñi. Nhö vaäy vieäc kieåm tra seõ ñöôïc laëp cho
ñeán khi gaëp moät daáu ngoaëc ñoùng maø khoâng so truøng ñöôïc vôùi daáu ngoaëc môû vöøa
löu tröõ (loãi caùc khoái khoâng loàng nhau) hoaëc ñeán khi heát vaên baûn caàn kieåm tra.
Tröôøng hôïp daáu ngoaëc ñoùng xuaát hieän maø ngaên xeáp roãng laø tröôøng hôïp vaên baûn bò
loãi thöøa daáu ngoaëc ñoùng (tính ñeán vò trí ñang xeùt); ngöôïc laïi, khi ñoïc heát ñoaïn vaên
baûn, neáu ngaên xeáp khoâng roãng thì do loãi thöøa daáu ngoaëc môû.
Chöông trình coù theå môû roäng hôn ñoái vôùi nhieàu caëp daáu ngoaëc khaùc nhau, hoaëc
cho caû tröôøng hôïp ñaëc bieät veà ñoaïn chuù thích trong moät chöông trình C (/* ...phaàn
trong naøy dó nhieân khoâng caàn kieåm tra tính hôïp leä cuûa caùc caëp daáu ngoaëc ...*/)
int main()
/*
post: Chöông trình seõ baùo cho ngöôøi söû duïng khi ñoaïn vaên baûn caàn phaân tích gaëp loãi.
uses: lôùp Stack.
*/
{
Stack<char> openings;
char symbol;
bool is_matched = true;
while (is_matched && (symbol = cin.get()) != '\n') {
if (symbol == '{' || symbol == '(' || symbol == '[')
openings.push(symbol);
if (symbol == '}' || symbol == ')' || symbol == ']') {
if (openings.empty()) {
cout << "Unmatched closing bracket " << symbol
<< " detected." << endl;
is_matched = false;
}
else {
char match;
openings.top(match);
openings.pop();
is_matched = (symbol == '}' && match == '{')
|| (symbol == ')' && match == '(')
|| (symbol == ']' && match == '[');
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
367
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
if (!is_matched)
cout << "Bad match " << match << symbol << endl;
}
}
}
if (!openings.empty())
cout << "Unmatched opening bracket(s) detected." << endl;
}
14.3. Trì hoaõn coâng vieäc
Khi söû duïng ngaên xeáp ñeå ñaûo ngöôïc döõ lieäu, toaøn boä döõ lieäu caàn ñöôïc duyeät
xong, chuùng ta môùi baét ñaàu laáy döõ lieäu töø ngaên xeáp. Nhoùm öùng duïng lieân quan
ñeán vieäc trì hoaõn coâng vieäc thöôøng chæ caàn trì hoaõn vieäc xöû lyù döõ lieäu trong moät
thôøi gian nhaát ñònh naøo ñoù maø thoâi.
Coù nhieàu giaûi thuaät maø döõ lieäu caàn xöû lyù coù theå xuaát hieän baát cöù luùc naøo, chuùng
seõ ñöôïc löu giöõ laïi ñeå chöông trình laàn löôït giaûi quyeát. Trong tröôøng hôïp döõ lieäu
caàn ñöôïc xöû lyù theo ñuùng thöù töï maø chuùng xuaát hieän, chuùng ta seõ duøng haøng ñôïi
laøm nôi löu tröõ döõ lieäu. Ngöôïc laïi, neáu thöù töï xöû lyù döõ lieäu ngöôïc vôùi thöù töï maø
chuùng xuaát hieän, chuùng ta seõ duøng ngaên xeáp do nguyeân taéc FILO cuûa noù.
14.3.1.ÖÙng duïng tính trò cuûa bieåu thöùc postfix
Chuùng ta seõ xem xeùt ví duï veà caùch tính trò cuûa moät bieåu thöùc ôû daïng Balan
ngöôïc (reverse Polish calculator- coøn goïi laø postfix). Trong bieåu thöùc naøy toaùn töû
luoân ñöùng sau toaùn haïng cuûa noù. Trong quaù trình duyeät bieåu thöùc, khi gaëp caùc
toaùn haïng chuùng ta phaûi hoaõn vieäc tính toaùn cho ñeán khi gaëp toaùn töû töông öùng
cuûa chuùng, do ñoù chuùng seõ ñöôïc ñaåy vaøo ngaên xeáp. Khi gaëp toaùn töû, caùc toaùn haïng
ñöôïc laáy ra khoûi ngaên xeáp, pheùp tính ñöôïc thöïc hieän vaø keát quaû laïi ñöôïc ñaåy vaøo
ngaên xeáp (do keát quaû naøy coù theå laïi laø toaùn haïng cuûa moät pheùp tính khaùc maø toaùn
töû cuûa noù chöa xuaát hieän). Thöù töï FILO ñöôïc nhìn thaáy ôû choã: toaùn töû cuûa nhöõng
toaùn haïng xuaát hieän tröôùc luoân ñöùng sau toaùn töû cuûa nhöõng toaùn haïng xuaát hieän
sau. Chaúng haïn, vôùi 8 5 2 - + (töông ñöông 8 + (5-2) ), soá 8 xuaát hieän tröôùc soá 2,
nhöng pheùp tröø cuûa (5 - 2) laïi coù tröôùc pheùp coäng.
Vieäc phaân tích moät bieåu thöùc lieân quan ñeán vieäc xöû lyù chuoãi ñeå taùch ra caùc
toaùn haïng cuõng nhö caùc toaùn töû. Do phaàn tieáp theo ñaây chæ chuù troïng ñeán yù töôûng
söû duïng ngaên xeáp trong giaûi thuaät, neân chöông trình seõ nhaän bieát caùc thaønh phaàn
cuûa bieåu thöùc moät caùch deã daøng thoâng qua vieäc cho pheùp ngöôøi söû duïng laàn löôït
nhaäp chuùng. Vieäc phaân tích bieåu thöùc coù theå ñöôïc xem nhö baøi taäp khi sinh vieân
keát hôïp vôùi caùc kieán thöùc khaùc coù lieân quan ñeán vieäc xöû lyù chuoãi kyù töï.
Trong chöông trình, ngöôøi söû duïng nhaäp daáu ? ñeå baùo tröôùc seõ nhaäp moät toaùn
haïng, toaùn haïng naøy seõ ñöôïc chöông trình löu vaøo ngaên xeáp. Khi caùc daáu +, -, *, /
ñöôïc nhaäp, chöông trình seõ laáy caùc toaùn haïng töø ngaên xeáp, tính vaø ñöa keát quaû
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
368
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
vaøo ngaên xeáp; daáu = yeâu caàu hieån thò phaàn töû taïi ñænh ngaên xeáp (nhöng khoâng laáy
ra khoûi ngaên xeáp), ñoù laø keát quaû cuûa moät pheùp tính môùi nhaát vöøa ñöôïc thöïc hieän.
Giaû söû a, b, c, d bieåu dieãn caùc giaù trò soá. Doøng nhaäp ? a ? b ? c - = * ? d + =
ñöôïc thöïc hieän nhö sau:
? a: ñaåy a vaøo ngaên xeáp;
? b: ñaåy b vaøo ngaên xeáp
? c: ñaåy c vaøo ngaên xeáp
- : laáy c vaø b ra khoûi ngaên xeáp, ñaåy b-c vaøo ngaên xeáp
= : in giaù trò b-c
* : laáy 2 toaùn haïng töø ngaên xeáp laø trò (b-c) vaø a, tính a * (b-c), ñöa keát quaû vaøo
ngaên xeáp.
? d: ñaåy d vaøo ngaên xeáp.
+ : laáy 2 toaùn haïng töø ngaên xeáp laø d vaø trò (a * (b-c)), tính (a * (b-c)) + d, ñöa keát
quaû vaøo ngaên xeáp.
= : in keát quaû (a * (b-c)) + d
Öu ñieåm cuûa caùch tính Balan ngöôïc laø moïi bieåu thöùc phöùc taïp ñeàu coù theå ñöôïc
bieåu dieãn khoâng caàn caëp daáu ngoaëc ().
Caùch bieåu dieãn Balan ngöôïc raát tieän lôïi trong caùc trình bieân dòch cuõng nhö caùc
pheùp tính toaùn.
Haøm phuï trôï get_command nhaän leänh töø ngöôøi söû duïng, kieåm tra hôïp leä vaø
chuyeån thaønh chöõ thöôøng bôûi tolower()trong thö vieän cctype.
int main()
/*
post: chöông trình thöïc hieän tính toaùn trò cuûa bieåu thöùc soá hoïc daïng postfix do ngöôøi söû duïng
nhaäp vaøo.
uses: lôùp Stack vaø caùc haøm introduction, instructions, do_command, get_command.
*/
{
Stack<double> stored_numbers;
introduction(); // Giôùi thieäu veà chöông trình.
instructions(); // Xuaát caùc höôùng daãn söû duïng chöông trình.
while (do_command(get_command(), stored_numbers));
}
char get_command()
/*
post: traû veà moät trong nhöõng kyù töï hôïp leä do ngöôøi söû duïng goõ vaøo (?, =, +, -, *, /, q).
*/
{
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
369
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
char command;
bool waiting = true;
cout << "Select command and press <Enter>:";
while (waiting) {
cin >> command;
command = tolower(command);
if (command == '?' || command == '=' || command == '+' ||
command == '-' || command == '*' || command == '/' ||
command == 'q' ) waiting = false;
else {
cout << "Please enter a valid command:"
<< endl
<< "[?]push to stack
<< "[+] [-] [*] [/]
<< "[Q]uit." << endl;
[=]print top" << endl
are arithmetic operations" << endl
}
}
return command;
}
Ngaên xeáp stored_numbers laøm thoâng soá cho haøm do_command ñöôïc khai baùo laø tham chieáu
do noù caàn phaûi thay ñoåi khi haøm ñöôïc goïi.
bool do_command(char command, Stack<double> &numbers)
/*
pre: command chöùa kyù hieäu cuûa pheùp tính soá hoïc (+, - *, /) hoaëc caùc kyù töï ñaõ quy ñònh (q, =, ?).
post: Vieäc xöû lyù tuøy thuoäc thoâng soá command. Haøm traû veà true, ngoaïi tröø tröôøng hôïp keát thuùc
vieâc tính toaùn khi commandlaø ‘q’.
uses: lôùp Stack.
*/
{
double p, q;
switch (command) {
case '?':
cout << "Enter a real number: " << flush;
cin >> p;
if (numbers.push(p) == overflow)
cout << "Warning: Stack full, lost number" << endl;
break;
case '=':
if (numbers.top(p) == underflow)
cout << "Stack empty" << endl;
else
cout << p << endl;
break;
case '+':
if (numbers.top(p) == underflow)
cout << "Stack empty" << endl;
else {
numbers.pop();
if (numbers.top(q) == underflow) {
cout << "Stack has just one entry" << endl;
numbers.push(p);
}
else {
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
370
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
numbers.pop();
if (numbers.push(q + p) == overflow)
cout << "Warning: Stack full, lost result" << endl;
}
}
break;
//
}
Add options for further user commands.
case 'q':
cout << "Calculation finished.\n";
return false;
return true;
}
14.3.2.ÖÙng duïng chuyeån ñoåi bieåu thöùc daïng infix thaønh daïng postfix
Ngöôïc vôùi bieåu thöùc daïng postfix, bieåu thöùc daïng infix cho pheùp coù caùc daáu
ngoaëc ñoùng môû quy öôùc veà ñoä öu tieân cuûa caùc pheùp tính. Chuùng ta coù ñoä öu tieân töø
cao xuoáng thaáp theo thöù töï sau ñaây:
Ñoä öu tieân 2 (cao nhaát): caùc pheùp tính * vaø /
Ñoä öu tieân 1
Ñoä öu tieân 0
: caùc pheùp tính + vaø -
: daáu (, )
Khi duyeät bieåu thöùc infix töø traùi sang phaûi, caùc toaùn haïng trong bieåu thöùc infix
ñeàu ñöôïc ñöa ngay vaøo bieåu thöùc postfix, caùc toaùn töû caàn ñöôïc hoaõn laïi neân ñöôïc
ñöa vaøo ngaên xeáp. Trong bieåu thöùc postfix, toaùn töû naøo gaëp tröôùc seõ ñöôïc tính
toaùn tröôùc. Do ñoù, töø bieåu thöùc infix, tröôùc khi moät toaùn töû naøo ñoù caàn ñöôïc ñöa
vaøo ngaên xeáp thì phaûi laáy töø ñænh ngaên xeáp taát caû caùc toaùn töû coù ñoä öu tieân cao
hôn noù ñeå ñaët vaøo bieåu thöùc postfix tröôùc. Rieâng tröôøng hôïp ñoä öu tieân cuûa toaùn
töû ñang caàn ñöa vaøo ngaên xeáp baèng vôùi ñoä öu tieân cuûa toaùn töû ñang ôû ñænh ngaên
xeáp, thì toaùn töû ôû ñænh ngaên xeáp cuõng ñöôïc laáy ra tröôùc neáu caùc toaùn töû naøy laø caùc
toaùn töû keát hôïp traùi (Vieäc tính toaùn xöû lyù töø traùi sang phaûi).
Chuùng ta quan saùt ba ví duï sau ñaây:
a + b * c ñöôïc chuyeån thaønh a b c * +
a * b + c ñöôïc chuyeån thaønh a b * c +
a + b - c ñöôïc chuyeån thaønh a b + c -
(1)
(2)
(3)
Ví duï 1, daáu + vaãn ôû trong ngaên xeáp, vaø daáu * ñöôïc ñaåy vaøo ngaên xeáp.
Ví duï 2, daáu * ñöôïc laáy ra khoûi ngaên xeáp tröôùc khi ñöa daáu + vaøo.
Ví duï 3, daáu + ñöôïc laáy ra khoûi ngaên xeáp tröôùc khi ñöa daáu - vaøo.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
371
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
Trong tröôøng hôïp coù daáu ngoaëc, daáu môû ‘(‘ caàn ñöôïc löu trong ngaên xeáp cho
ñeán khi gaëp daáu ñoùng ‘)’ töông öùng. Chuùng ta quy öôùc ñoä öu tieân cuûa daáu ngoaëc môû
thaáp nhaát laø hôïp lyù. Moïi toaùn töû xuaát hieän sau daáu ngoaëc môû ñeàu khoâng theå laøm
cho daáu naøy ñöôïc laáy ra khoûi ngaên xeáp, tröø khi daáu ngoaëc ñoùng töông öùng ñöôïc
duyeät ñeán. Khi gaëp daáu ñoùng ‘)’, xem nhö keát thuùc moïi vieäc tính toaùn trongcaëp
daáu (), moïi toaùn töû coøn naèm treân daáu môû ‘(‘ trong ngaên xeáp ñeàu ñöôïc laáy ra ñeå ñöa
vaøo bieåu thöùc daïng postfix. Do caùc daáu ngoaëc khoâng bao giôø xuaát hieän trong bieåu
thöùc postfix, daáu ‘(‘ ñöôïc ñaët vaøo ngaên xeáp ñeå chôø daáu ‘)’ töông öùng, khi noù ñöôïc
laáy ra thì seõ bò vaát boû. Daáu ‘)’ ñeå giaûi quyeát cho daáu ‘(‘, vaø cuõng seõ bò vaát ñi.
Caùc toaùn töû +, -, *, / ñeàu laø caùc toaùn töû keát hôïp töø traùi sang phaûi. Bieåu thöùc
a - b - c ( ñöôïc hieåu laø (a-b)-c ) ñöôïc chuyeån ñoåi thaønh a b - c - (khoâng phaûi a b
c - - ). Vôùi moät soá toaùn töû keát hôïp töø phaûi sang traùi, chaúng haïn pheùp tính luõy thöøa
thì 2^2^3 = 2^(2^3)= 2^8=256, khoâng phaûi (2^2)^3= 4^3=64, thì caùc xöû lyù treân
caàn ñöôïc söûa ñoåi cho hôïp lyù. Chöông trình hoaøn chænh chuyeån ñoåi bieåu thöùc dang
infix sang bieåu thöùc daïng postfix, cuõng nhö vieäc xöû lyù ñaëc bieät cho tröôøng hôïp
toaùn töû keát hôïp phaûi ñöôïc xem nhö baøi taäp.
14.4. Giaûi thuaät quay lui (backtracking)
Ngaên xeáp coøn ñöôïc söû duïng trong caùc giaûi thuaät quay lui nhaèm löu laïi caùc
thoâng tin ñaõ töøng duyeät qua ñeå coù theå quay ngöôïc trôû laïi. Chuùng ta seõ xem xeùt caùc
ví duï sau ñaây.
14.4.1.ÖÙng duïng trong baøi toaùn tìm ñích (goal seeking).
Hình 14.1 minh hoïa cho baøi toaùn tìm ñích. Chuùng ta coù moät nuùt baét ñaàu vaø
moät nuùt goïi laø ñích ñeán. Ñeå ñôn giaûn, chuùng ta xeùt ñoà thò khoâng coù chu trình vaø
chæ coù duy nhaát moät ñöôøng ñi töø nôi baét ñaàu ñeán ñích. Nhìn hình veõ chuùng ta coù
theå nhaän ra ngay ñöôøng ñi naøy. Tuy nhieân maùy tính caàn moät giaûi thuaät thích
hôïp ñeå tìm ra ñöôïc con ñöôøng naøy.
Chuùng ta baét ñaàu töø nuùt 1, sang nuùt 2 vaø nuùt 3. Taïi nuùt 3 coù 2 ngaõ reõ, giaû söû
chuùng ta ñi theo ñöôøng treân, ñeán nuùt 4 vaø nuùt 5. Taïi nuùt 5 chuùng ta laïi ñi theo
ñöôøng treân ñeán nuùt 6 vaø nuùt 7. Ñeán ñaây chuùng ta khoâng coøn ñöôøng ñi tieáp vaø cuõng
chöa tìm ñöôïc ñích caàn ñeán, chuùng ta phaûi quay trôû laïi nuùt 5 ñeå choïn loái ñi khaùc.
Taïi nuùt 8 chuùng ta laïi phaûi quay laïi nuùt 5 ñeå ñi sang nuùt 9,…. Baèng caùch naøy, töø
nuùt 13, khi chuùng ta tìm ñöôïc nuùt 16 thì chuùng ta khoâng caàn phaûi quay lui ñeå thöû
vôùi nuùt 17, 18 nöõa. Giaûi thuaät keát thuùc khi tìm thaáy ñích ñeán.
Giaûi thuaät cuûa chuùng ta caàn löu caùc nuùt ñeå quay laïi. So saùnh nuùt 3 vaø nuùt 5,
chuùng ta thaáy raèng treân ñöôøng ñi chuùng ta gaëp nuùt 3 tröôùc, nhöng dieåm quay veà
ñeå thöû tröôùc laïi laø nuùt 5. Do ñoù caáu truùc döõ lieäu thích hôïp chính laø ngaên xeáp vôùi
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
372
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
nguyeân taéc FILO cuûa noù. Ngoaøi ra neáu chuùng ta löu nuùt 3 vaø nuùt 5 thì coù söï baát
tieän ôû choã laø khi quay veà, thoâng tin laáy töø ngaên xeáp khoâng cho chuùng ta bieát caùc
nhaùnh naøo ñaõ ñöôïc duyeät qua vaø caùc nhaùnh naøo caàn tieáp tuïc duyeät. Do ñoù, taïi nuùt
3, tröôùc khi ñi sang 4, chuùng ta löu nuùt 12, taïi nuùt 5, tröôùc khi ñi sang 6 chuùng ta
löu nuùt 8 vaø nuùt 9,…
Vôùi giaûi thuaät treân chuùng ta coù theå tìm ñeán ñích moät caùch deã daøng. Tuy nhieân,
neáu baøi toaùn yeâu caàu in ra caùc nuùt treân ñöôøng ñi töø nuùt baét ñaàu ñeán ñích thì
chuùng ta chöa laøm ñöôïc. Nhö vaäy chuùng ta cuõng caàn phaûi löu caû caùc nuùt treân
ñöôøng maø chuùng ta ñaõ ñi qua. Nhöõng nuùt naèm treân nhöõng ñoaïn ñöôøng khoâng daãn
ñeán ñích seõ ñöôïc dôõ boû khoûi ngaên xeáp khi chuùng ta quay lui. ÔÛ ñaây chuùng ta gaëp
phaûi moät vaán ñeà cuõng töông ñoái phoå bieán trong moät soá baøi toaùn khaùc, ñoù laø nhöõng
gì chuùng ta boû vaøo ngaên xeáp khoâng coù cuøng muïc ñích. Coù hai nhoùm thoâng tin khaùc
nhau: moät laø caùc nuùt naèm treân ñöôøng ñang ñi qua, hai laø caùc nuùt naèm treân caùc
nhaùnh reõ khaùc maø chuùng ta seõ laàn löôït thöû tieáp khi gaëp thaát baïi treân con ñöôøng
ñang ñi. Trong nhöõng tröôøng hôïp nhö vaäy, vieäc giaûi quyeát raát laø deã daøng: chuùng
ta duøng caùch ñaùnh daáu ñeå phaân bieät töøng tröôøng hôïp, khi laáy ra khoûi ngaên xeáp,
caên cöù vaøo caùch ñaùnh daáu naøy chuùng ta seõ bieát phaûi xöû lyù nhö theá naøo cho thích
hôïp (Vieäc duyeät caây theo thöù töï LRN trong chöông 10 neáu duøng ngaên xeáp cuõng laø
moät ví duï). Trong hình 14.1, kyù töï B trong ngaên xeáp cho bieát ñoù laø nhöõng nuùt
daønh cho vieäc quay lui (Backtracking) ñeå thöû vôùi nhaùnh khaùc. Vaäy khi gaëp ñieåm
cuoái cuûa moät con ñöôøng khoâng daãn ñeán ñích, chuùng ta dôõ boû khoûi ngaên xeáp caùc
nuùt cho ñeán khi gaëp moät nuùt coù kyù töï ‘B’, boû laïi nuùt naøy vaøo ngaên xeáp (khoâng coøn
kyù töï ‘B’), vaø ñi tieáp caùc nuùt keá tieáp theo nuùt naøy. Cuoái cuøng khi gaëp ñích, con
ñöôøng ñöôïc tìm thaáy chính laø caùc nuùt ñang löu trong ngaên xeáp maø khoâng coù kyù töï
‘B’ ôû ñaàu.
end
7
6
B8
B9
5
4
B12
3
6
7
end
11
10
9
5
4
goal
16
15
14
B17
13
12
3
end
8
B9
5
4
B12
3
B8
B9
5
4
B12
3
4
5
8
9
Start node
10
11
1
2
3
The goal
B12
3
B12
3
2
1
(a)
2
1
(b)
2
1
(c)
2
1
(d)
2
1
(e)
2
1
(f)
15
18
12
13
14
17
16
Hình 14.1- Ví duï vaø ngaên xeáp minh hoïa quaù trình backtracking.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
373
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
Algorithm seek_goal(val graph_type graph, val node_type start,
val node_type goal)
/*
pre: graphchöùa ñoà thò khoâng coù chu trình, trong ñoù coù moät nuùt startvaø moät nuùt goal.
post: neáu ñöôøng ñi töø startñeán goalñöôïc tìm thaáy seõ ñöôïc in ra theo thöù töï töø goalngöôïc
veà start
*/
{
1. Stack<node_type> nodes. // node_typelaø kieåu döõ lieäu thích hôïp.
2. node_type current_node = start
3. boolean fail = FALSE
4. loop ((current_node chöa laø goal) AND (!fail))
1. nodes.push(current_node)
2. if (current_node laø ñieåm reõ nhaùnh)
1. next_node = nuùt reõ vaøo 1 nhaùnh
2. loop (coøn nhaùnh chöa ñöa vaøo ngaên xeáp) // ñöa caùc nhaùnh
// coøn laïi vaøo ngaên xeáp.
1. nodes.push(nuùt reõ vaøo 1 nhaùnh, coù keøm ‘B’)
3. endloop
3. else
1. if (toàn taïi nuùt keá)
1. next_node = nuùt keá
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_nodecoù ‘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 laø goal
3. loop (!nodes.empty())
1. nodes.top(current_node)
2. nodes.pop()
3. if (current_node khoâng coù kyù töï ‘B’)
1. print(current_node)
4. endif
4. endloop
7. else
1. print(“Path not found!”)
8. endif
}
Treân ñaây laø maõ giaû cho baøi toaùn tìm ñích, caáu truùc döõ lieäu ñeå chöùa ñoà thò
chuùng ta seõ ñöôïc tìm hieåu sau trong chöông 13.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
374
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
14.4.2.Baøi toaùn maõ ñi tuaàn vaø baøi toaùn taùm con haäu
Ví duï tieáp theo lieân quan ñeán baøi toaùn maõ ñi tuaàn. Thöïc ra baøi toaùn taùm con
haäu ñöôïc trình baøy trong chöông 6 cuõng hoaøn toaøn töông töï. Sinh vieân coù theå
tham khaûo yù töôûng ñöôïc trình baøy döôùi ñaây ñeå giaûi baøi toaùn taùm con haäu söû duïng
ngaên xeáp thay vì ñeä quy.
Vôùi baøn côø 64 oâ, baøi toaùn maõ ñi tuaàn yeâu caàu chuùng ta chæ ra ñöôøng ñi cho con
maõ baét ñaàu töø moät oâ naøo ñoù, laàn löôït ñi qua taát caû caùc oâ, maø khoâng coù oâ naøo laäp
laïi hôn moät laàn.
Töø moät vò trí, con maõ coù toái ña laø 8 vò trí chung quanh coù theå ñi ñöôïc. Giaûi
thuaät quay lui raát gaàn vôùi höôùng suy nghó töï nhieân cuûa chuùng ta. Trong caùc khaû
naêng coù theå, chuùng ta thöôøng choïn ngaãu nhieân moät khaû naêng ñeå ñi. Vaø vôùi vò trí
môùi chuùng ta cuõng laøm ñieàu töông töï. Moãi oâ ñi qua chuùng ta ñaùnh daáu laïi. Trong
quaù trình thöû naøy, neáu coù luùc khoâng coøn khaû naêng löïa choïn naøo khaùc vì caùc oâ naèm
trong khaû naêng ñi tieáp ñeàu ñaõ ñöôïc ñaùnh daáu, chuùng ta caàn phaûi luøi laïi ñeå thöû
nhöõng khaû naêng khaùc. Thay vì bieåu dieãn ñöôøng ñi cho con maõ treân baøn côø (hình
14.2a), chuùng ta veõ laïi caùc khaû naêng ñi vaø thaáy chuùng khoâng khaùc gì so vôùi baøi
toaùn tìm ñích (hình 14.2b). Vaø nhö vaäy, chuùng ta thaáy caùch söû duïng ngaên xeáp
trong nhöõng baøi toaùn daïng naøy hoaøn toaøn ñôn giaûn vaø töông töï. Phöông phaùp
quay lui trong tröôøng hôïp naøy ñoâi khi coøn ñöôïc goïi laø phöông phaùp thöû sai (trial
and error method).
1 2 3 4 5 6 7 8
(3,2)
1
(4,3)
(6,3)
(4,1)
(3,2)
(3,4)
(5,1)
(5,3)
2
3
4
5
6
7
8
(7,2)
(4,5)
(6,5)
(7,4)
(4,1)
(8,4)
(a)
(b)
Hình 14.2- Baøi toaùn maõ ñi tuaàn.
Hình treân ñaây minh hoïa baøi toaùn maõ ñi tuaàn vôùi ñieåm baét ñaàu laø (7,2). Ñích
ñeán khoâng cuï theå nhö baøi toaùn treân, maø ñöôøng ñi caàn tìm chính laø ñöôøng ñi naøo
trong ñoà thò naøy coù ñuû 64 nuùt. Baøi toaùn naøy phuï thuoäc vaøo soá oâ cuûa baøn côø vaø vò
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
375
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp
trí baét ñaàu cuûa con maõ, khaû naêng coù lôøi giaûi vaø coù bao nhieâu lôøi giaûi chuùng ta
khoâng xem xeùt ôû ñaây. Chuùng ta chæ quan taâm ñeán caùch söû duïng ngaên xeáp trong
nhöõng baøi toaùn töông töï. Baûn chaát nhöõng baøi naøy ñeàu coù cuøng moät ñaëc tröng cuûa
baøi toaùn tìm ñích treân moät ñoà thò khoâng coù chu trình. Ñích ñeán coù theå laø nhieàu
hôn moät (töông öùng vôùi nhieàu lôøi giaûi ñöôïc tìm thaáy) nhö trong baøi toaùn taùm con
haäu maø caùch giaûi ñeä quy đöôïc trình baøy trong chöông 6. Söï khaùc nhau cô baûn giöõa
chuùng chæ laø moät vaøi kyõ thuaät nho nhoû duøng ñeå chuyeån töø döõ lieäu ban ñaàu cuûa baøi
toaùn sang daïng ñoà thò bieåu dieãn caùc khaû naêng di chuyeån trong quaù trình tìm ñeán
ñích maø thoâi.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
376
12 trang
19180
Free
Bạn đang xem tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 3: Các ứng dụng của các lớp cấu trúc dữ liệu - Chương 14: Ứng dụng của ngăn xếp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_3_cac_ung_dun.pdf
