CTDL 2005 chuong 14

Chia sẻ: Hoang Nguyen | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

85
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Các ứng dụng của các lớp CTDL

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CTDL 2005 chuong 14

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 decNum sang moät soá nhò phaân. 1 loop (decNum > 0) 1 digit = decNum % 2 2 xuaát (digit) 3 decNum = decNum / 2 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 decNum seõ ñöôï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 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) 5 endloop } 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 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
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp if (!is_matched) cout
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 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 > command; command = tolower(command); if (command == '?' || command == '=' || command == '+' || command == '-' || command == '*' || command == '/' || command == 'q' ) waiting = false; else { cout
Chöông 14 – ÖÙng duïng cuûa ngaên xeáp numbers.pop(); if (numbers.push(q + p) == overflow) cout
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 6 7 7 end goal 6 end 11 16 B8 B8 8 10 15 4 5 8 Start node B9 B9 B9 9 14 5 5 5 5 B17 9 10 11 4 4 4 4 13 1 2 3 The goal B12 B12 B12 B12 B12 12 3 3 3 3 3 3 2 2 2 2 2 2 15 12 13 14 1 1 1 1 1 1 16 (a) (b) (c) (d) (e) (f) 17 18 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: graph chöùa ñoà thò khoâng coù chu trình, trong ñoù coù moät nuùt start vaø 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öø goal ngöôïc veà start */ { 1. Stack nodes. // node_type laø 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_node coù ‘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). 12345678 (3,2) 1 (4,3) (5,1) 2 (6,3) 3 4 (4,1) 5 (7,2) (5,3) (3,2) 6 (3,4) 7 8 (4,5) (8,4) (6,5) (7,4) (4,1) (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