Giáo trình Nhập môn trí tuệ nhân tạo: Phần 1 - GS.TSKH. Hoàng Kiếm, ThS. Đinh Nguyễn Anh Dũng

Chia sẻ: Hoa La Hoa | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

392
lượt xem 125
download

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

Giáo trình Nhập môn trí tuệ nhân tạo gồm 3 chương, được chia thành hai phần. Phần 1 giới thiệu đến bạn đọc nội dung chương 1 về thuật toán - thuật giải. Chương này cung cấp cho bạn đọc các nội dung như: Khái niệm thuật toán - thuật giải, thuật giải Heuristic, các phương pháp tìm kiếm Heuristic.

Chủ đề:

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

Lưu

Nội dung Text: Giáo trình Nhập môn trí tuệ nhân tạo: Phần 1 - GS.TSKH. Hoàng Kiếm, ThS. Đinh Nguyễn Anh Dũng

Chöông 1 – THUAÄT TOAÙN - THUAÄT GIAÛI I. KHAÙI NIEÄM THUAÄT TOAÙN – THUAÄT GIAÛI Trong quaù trình nghieân cöùu giaûi quyeát caùc vaán ñeà – baøi toaùn, ngöôøi ta ñaõ ñöa ra nhöõng nhaän xeùt nhö sau: o Coù nhieàu baøi toaùn cho ñeán nay vaãn chöa tìm ra moät caùch giaûi theo kieåu thuaät toaùn vaø cuõng khoâng bieát laø coù toàn taïi thuaät toaùn hay khoâng. o Coù nhieàu baøi toaùn ñaõ coù thuaät toaùn ñeå giaûi nhöng khoâng chaáp nhaän ñöôïc vì thôøi gian giaûi theo thuaät toaùn ñoù quaù lôùn hoaëc caùc ñieàu kieän cho thuaät toaùn khoù ñaùp öùng. o Coù nhöõng baøi toaùn ñöôïc giaûi theo nhöõng caùch giaûi vi phaïm thuaät toaùn nhöng vaãn chaáp nhaän ñöôïc. Töø nhöõng nhaän ñònh treân, ngöôøi ta thaáy raèng caàn phaûi coù nhöõng ñoåi môùi cho khaùi nieäm thuaät toaùn. Ngöôøi ta ñaõ môû roäng hai tieâu chuaån cuûa thuaät toaùn: tính xaùc ñònh vaø tính ñuùng ñaén. Vieäc môû roäng tính xaùc ñònh ñoái vôùi thuaät toaùn ñaõ ñöôïc theå hieän qua caùc giaûi thuaät ñeä quy vaø ngaãu nhieân. Tính ñuùng cuûa thuaät toaùn baây giôø khoâng coøn baét buoäc ñoái vôùi moät soá caùch giaûi baøi toaùn, nhaát laø caùc caùch giaûi gaàn ñuùng. Trong thöïc tieãn coù nhieàu tröôøng hôïp ngöôøi ta chaáp nhaän caùc caùch giaûi thöôøng cho keát quaû toát (nhöng
khoâng phaûi luùc naøo cuõng toát) nhöng ít phöùc taïp vaø hieäu quaû. Chaúng haïn neáu giaûi moät baøi toaùn baèng thuaät toaùn toái öu ñoøi hoûi maùy tính thöïc hieân nhieàu naêm thì chuùng ta coù theå saün loøng chaáp nhaän moät giaûi phaùp gaàn toái öu maø chæ caàn maùy tính chaïy trong vaøi ngaøy hoaëc vaøi giôø. Caùc caùch giaûi chaáp nhaän ñöôïc nhöng khoâng hoaøn toaøn ñaùp öùng ñaày ñuû caùc tieâu chuaån cuûa thuaät toaùn thöôøng ñöôïc goïi laø caùc thuaät giaûi. Khaùi nieäm môû roäng naøy cuûa thuaät toaùn ñaõ môû cöûa cho chuùng ta trong vieäc tìm kieám phöông phaùp ñeå giaûi quyeát caùc baøi toaùn ñöôïc ñaët ra. Moät trong nhöõng thuaät giaûi thöôøng ñöôïc ñeà caäp ñeán vaø söû duïng trong khoa hoïc trí tueä nhaân taïo laø caùc caùch giaûi theo kieåu heuristic. II. THUAÄT GIAÛI HEURISTIC Thuaät giaûi heuristic laø moät söï môû roäng khaùi nieäm thuaät toaùn. Noù theå hieän caùch giaûi baøi toaùn vôùi caùc ñaëc tính sau: o Thöôøng tìm ñöôïc lôøi giaûi toát (nhöng khoâng chaéc laø lôøi giaûi toát nhaát) o Giaûi baøi toaùn theo thuaät giaûi heuristic thöôøng deã daøng vaø nhanh choùng ñöa ra keát quaû hôn so vôùi giaûi thuaät toái öu, vì vaäy chi phí thaáp hôn. o Thuaät giaûi heuristic thöôøng theå hieän khaù töï nhieân, gaàn guõi vôùi caùch suy nghó vaø haønh ñoäng cuûa con ngöôøi. - - 3
Coù nhieàu phöông phaùp ñeå xaây döïng moät thuaät giaûi heuristic, trong ñoù ngöôøi ta thöôøng döïa vaøo moät soá nguyeân lyù cô baûn nhö sau. Nguyeân lyù veùt caïn thoâng minh: Trong moät baøi toaùn tìm kieám naøo ñoù, khi khoâng gian tìm kieám lôùn, ta thöôøng tìm caùch giôùi haïn laïi khoâng gian tìm kieám hoaëc thöïc hieän moät kieåu doø tìm ñaëc bieät döïa vaøo ñaëc thuø cuûa baøi toaùn ñeå nhanh choùng tìm ra muïc tieâu. Nguyeân lyù tham lam (Greedy): Laáy tieâu chuaån toái öu (treân phaïm vi toaøn cuïc) cuûa baøi toaùn ñeå laøm tieâu chuaån choïn löïa haønh ñoäng cho phaïm vi cuïc boä cuûa töøng böôùc (hay töøng giai ñoaïn) trong quaù trình tìm kieám lôøi giaûi. Nguyeân lyù thöù töï: Thöïc hieän haønh ñoäng döïa treân moät caáu truùc thöù töï hôïp lyù cuûa khoâng gian khaûo saùt nhaèm nhanh choùng ñaït ñöôïc moät lôøi giaûi toát. Haøm heuristic: Trong vieäc xaây döïng caùc thuaät giaûi heuristic, ngöôøi ta thöôøng duøng caùc haøm heuristic. Ñoù laø caùc haøm ñaùnh giaù thoâ, giaù trò cuûa haøm phuï thuoäc vaøo traïng thaùi hieän taïi cuûa baøi toaùn taïi moãi böôùc giaûi. Nhôø giaù trò naøy, ta coù theå choïn ñöôïc caùch haønh ñoäng töông ñoái hôïp lyù trong töøng böôùc cuûa thuaät giaûi. Baøi toaùn haønh trình ngaén nhaát – öùng duïng nguyeân lyù Greedy Baøi toaùn: Haõy tìm moät haønh trình cho moät ngöôøi giao haøng ñi qua n ñieåm khaùc nhau, moãi ñieåm ñi qua moät laàn vaø trôû veà ñieåm xuaát phaùt 4 - -
sao cho toång chieàu daøi ñoaïn ñöôøng caàn ñi laø ngaén nhaát. Giaû söû raèng coù con ñöôøng noái tröïc tieáp töø giöõa hai ñieåm baát kyø. Taát nhieân ta coù theå giaûi baøi toaùn naøy baèng caùch lieät keâ taát caû con ñöôøng coù theå ñi, tính chieàu daøi cuûa moãi con ñöôøng ñoù roài tìm con ñöôøng coù chieàu daøi ngaén nhaát. Tuy nhieân, caùch giaûi naøy laïi coù ñoä phöùc taïp 0(n!) (moät haønh trình laø moät hoaùn vò cuûa n ñieåm, do ñoù, toång soá haønh trình laø soá löôïng hoaùn vò cuûa moät taäp n phaàn töû laø n!). Do ñoù, khi soá ñaïi lyù taêng thì soá con ñöôøng phaûi xeùt seõ taêng leân raát nhanh. Moät caùch giaûi ñôn giaûn hôn nhieàu vaø thöôøng cho keát quaû töông ñoái toát laø duøng moät thuaät giaûi heuristic öùng duïng nguyeân lyù Greedy. Tö töôûng cuûa thuaät giaûi nhö sau: o Töø ñieåm khôûi ñaàu, ta lieät keâ taát caû quaõng ñöôøng töø ñieåm xuaát phaùt cho ñeán n ñaïi lyù roài choïn ñi theo con ñöôøng ngaén nhaát. o Khi ñaõ ñi ñeán moät ñaïi lyù, choïn ñi ñeán ñaïi lyù keá tieáp cuõng theo nguyeân taéc treân. Nghóa laø lieät keâ taát caû con ñöôøng töø ñaïi lyù ta ñang ñöùng ñeán nhöõng ñaïi lyù chöa ñi ñeán. Choïn con ñöôøng ngaén nhaát. Laëp laïi quaù trình naøy cho ñeán luùc khoâng coøn ñaïi lyù naøo ñeå ñi. Baïn coù theå quan saùt hình sau ñeå thaáy ñöôïc quaù trình choïn löïa. Theo nguyeân lyù Greedy, ta laáy tieâu chuaån haønh trình ngaén nhaát cuûa baøi toaùn laøm tieâu chuaån cho choïn löïa cuïc boä. Ta hy voïng raèng, khi ñi treân n ñoaïn ñöôøng ngaén nhaát thì cuoái cuøng ta seõ coù moät haønh trình ngaén nhaát. Ñieàu naøy khoâng phaûi luùc naøo cuõng ñuùng. Vôùi ñieàu kieän trong hình tieáp theo thì thuaät giaûi cho chuùng ta moät haønh trình coù chieàu daøi laø 14 trong khi haønh trình toái öu laø 13. - - 5
Keát quaû cuûa thuaät giaûi Heuristic trong tröôøng hôïp naøy chæ leäch 1 ñôn vò so vôùi keát quaû toái öu. Trong khi ñoù, ñoä phöùc taïp cuûa thuaät giaûi Heuristic naøy chæ laø 0(n2). 1 5 1 3 5 2 2 4 7 2 4 3 4 3 1 1 1 1 1 5 3 5 2 5 2 4 7 2 4 4 3 4 3 1 1 1 5 1 3 3 5 2 5 2 2 4 2 2 4 3 6 - -
4 3 4 3 1 Hình 1.1: Giaûi baøi toaùn söû duïng nguyeân lyù Greedy Taát nhieân, thuaät giaûi theo kieåu Heuristic ñoâi luùc laïi ñöa ra keát quaû khoâng toát, thaäm chí raát teä nhö tröôøng hôïp ôû hình sau. 1 5 1 3 5 2 2 100 2 4 4 3 4 3 1 Hình 1.2 - - 7
Baøi toaùn phaân vieäc – öùng duïng cuûa nguyeân lyù thöù töï Moät coâng ty nhaän ñöôïc hôïp ñoàng gia coâng m chi tieát maùy J1, J2, … Jm. Coâng ty coù n maùy gia coâng laàn löôït laø P1, P2, … Pn. Moïi chi tieát ñeàu coù theå ñöôïc gia coâng treân baát kyø maùy naøo. Moät khi ñaõ gia coâng moät chi tieát treân moät maùy, coâng vieäc seõ tieáp tuïc cho ñeán luùc hoaøn thaønh, khoâng theå bò caét ngang. Ñeå gia coâng moät vieäc J1 treân moät maùy baát kyø ta caàn duøng moät thôøi gian töông öùng laø t1. Nhieäm vuï cuûa coâng ty laø phaûi laøm sao gia coâng xong toaøn boä n chi tieát trong thôøi gian sôùm nhaát. Chuùng ta xeùt baøi toaùn trong tröôøng hôïp coù ba maùy P1, P2, P3 vaø saùu coâng vieäc vôùi thôøi gian laø t1 = 2, t2 = 5, t3 = 8, t4 = 1, t5 = 5, t6 = 1; ta coù moät phöông aùn phaân coâng (L) nhö hình sau: t2 = 5 M1 t5 = 5 M2 t1 = 2 t6 = 1 t3 = 8 M3 t4 = 1 Hình 1.3 8 - -
Theo hình 1.3, taïi thôøi ñieåm t = 0, ta tieán haønh gia coâng chi tieát J2 treân maùy P1, J5 treân P2 vaø J1 taïi P3. Taïi thôøi ñieåm t = 2, coâng vieäc J1 ñöôïc hoaøn thaønh, treân maùy P3 ta gia coâng tieáp chi tieát J4. Trong luùc ñoù, hai maùy P1 vaø P2 vaãn ñang thöïc hieän coâng vieäc ñaàu tieân mình … Sô ñoà phaân vieäc theo hình ôû treân ñöôïc goïi laø löôïc ñoà Gantt. Theo löôïc ñoà naøy, ta thaáy thôøi gian ñeå hoaøn thaønh toaøn boä 6 coâng vieäc laø 12. Nhaän xeùt moät caùch caûm tính ta thaáy raèng phöông aùn (L) vöøa thöïc hieän laø moät phöông aùn khoâng toát. Caùc maùy P1 vaø P2 coù quaù nhieàu thôøi gian raûõnh. Thuaät toaùn tìm phöông aùn toái öu L0 cho baøi toaùn naøy theo kieåu veùt caïn coù ñoä phöùc taïp côõ O(mn) (vôùi m laø soá maùy vaø n laø soá coâng vieäc). Baây giôø ta xeùt ñeán moät thuaät giaûi heuristic raát ñôn giaûn (ñoä phöùc taïp O(n)) ñeå giaûi baøi toaùn naøy. o Saép xeáp caùc coâng vieäc theo thöù töï giaûm daàn veà thôøi gian gia coâng. o Laàn löôït saép xeáp caùc vieäc theo thöù töï ñoù vaøo maùy coøn dö nhieàu thôøi gian nhaát. Vôùi tö töôûng nhö vaäy, ta seõ coù moät phöông aùn L* nhö sau: - - 9
t3 = 8 M1 t2 = 5 t1 = 2 M2 t5 = 5 t4 = 2 M3 t6 = 1 Hình 1.4 Roõ raøng phöông aùn L* vöøa thöïc hieän cuõng chính laø phöông aùn toái öu cuûa tröôøng hôïp naøy vì thôøi gian hoaøn thaønh laø 8, ñuùng baèng thôøi gian cuûa coâng vieäc J3. Ta hy voïng raèng moät thuaät giaûi heuristic ñôn giaûn nhö vaäy seõ laø moät thuaät giaûi toái öu. Nhöng tieác thay, ta deã daøng ñöa ra ñöôïc moät tröôøng hôïp maø thuaät giaûi heuristic khoâng ñöa ra ñöôïc keát quaû toái öu. t1 = 3 t3 = 2 t5 = 2 M1 t2 = 3 t4 = 2 M2 t1 = 3 t2 = 3 M1 t2 = 2 t4 = 2 t5 = 2 10 M2 - -
Neáu goïi T* laø thôøi gian ñeå gia coâng xong n chi tieát maùy do thuaät giaûi heuristic ñöa ra vaø T0 laø thôøi gian toái öu thì ngöôøi ta ñaõ chöùng minh ñöôïc raèng T* 4 1   (M laø soá maùy) T0 3 M Vôùi keát quaû naøy, ta coù theå xaùc laäp ñöôïc sai soá maø chuùng ta phaûi gaùnh chòu neáu duøng heuristic thay vì tìm moät lôøi giaûi toái öu. Chaúng haïn vôùi soá maùy laø 2 (M = 2) ta coù T* 7  , vaø ñoù chính laø sai soá cöïc ñaïi maø tröôøng hôïp ôû T0 6 treân ñaõ gaùnh chòu. Theo coâng thöùc naøy, soá maùy caøng lôùn thì sai soá caøng lôùn. Trong tröôøng hôïp M lôùn thì tyû soá 1/M xem nhö baèng 0. Nhö vaäy, sai soá toái ña maø ta phaûi chòu laø T* 4/3 T0, nghóa laø sai soá toái ña laø 33%. Tuy nhieân, khoù tìm ra ñöôïc nhöõng tröôøng hôïp maø sai soá ñuùng baèng giaù trò cöïc ñaïi, duø trong tröôøng hôïp xaáu nhaát. Thuaät giaûi heuristic trong tröôøng hôïp naøy roõ raøng ñaõ cho chuùng ta nhöõng lôøi giaûi töông ñoái toát. - - 11
III. CAÙC PHÖÔNG PHAÙP TÌM KIEÁM HEURISTIC Qua caùc phaàn tröôùc chuùng ta tìm hieåu toång quan veà yù töôûng cuûa thuaät giaûi heuristic (nguyeân lyù Greedy vaø saép thöù töï). Trong muïc naøy, chuùng ta seõ ñi saâu vaøo tìm hieåu moät soá kyõ thuaät tìm kieám heuristic – moät lôùp baøi toaùn raát quan troïng vaø coù nhieàu öùng duïng trong thöïc teá. III. Caáu truùc chung cuûa baøi toaùn tìm kieám Ñeå tieän lôïi cho vieäc trình baøy, ta haõy daønh chuùt thôøi gian ñeå laøm roõ hôn “ñoái töôïng” quan taâm cuûa chuùng ta trong muïc naøy. Moät caùch chung nhaát, nhieàu vaán ñeà-baøi toaùn phöùc taïp ñeàu coù daïng “tìm ñöôøng ñi trong ñoà thò” hay noùi moät caùch hình thöùc hôn laø “xuaát phaùt töø moät ñænh cuûa moät ñoà thò, tìm ñöôøng ñi hieäu quaû nhaát ñeán moät ñænh naøo ñoù”. Moät phaùt bieåu khaùc thöôøng gaëp cuûa daïng baøi toaùn naøy laø : Cho tröôùc hai traïng thaùi T0 vaø TG haõy xaây döïng chuoãi traïng thaùi T0, T1, T2, ..., Tn-1, Tn = TG sao cho :  cos t(T n 1 i 1 , Ti ) thoûa maõn moät ñieàu kieän cho tröôùc (thöôøng laø nhoû nhaát) trong ñoù, Ti thuoäc taäp hôïp S (goïi laø khoâng gian traïng thaùi – state space) bao goàm taát caû caùc traïng thaùi coù theå coù cuûa baøi toaùn vaø cost(Ti-1, Ti) laø chi phí ñeå bieán ñoåi töø traïng thaùi Ti-1 sang traïng thaùi Ti. Dó nhieân, töø moät traïng thaùi Ti 12 - -
ta coù nhieàu caùch ñeå bieán ñoåi sang traïng thaùi Ti+1. Khi noùi ñeán moät bieán ñoåi cuï theå töø Ti-1 sang Ti ta seõ duøng thuaät ngöõ höôùng ñi (vôùi nguï yù noùi veà söï löïa choïn). 7 1 5 9 5 6 3 1 1 5 1 6 1 7 2 0 4 1 2 2 0 3 8 Hình 1.6: Moâ hình chung cuûa caùc vaán ñeà-baøi toaùn phaûi giaûi quyeát baèng phöông phaùp tìm kieám lôøi giaûi. Khoâng gian tìm kieám laø moät taäp hôïp traïng thaùi - taäp caùc nuùt cuûa ñoà thò. Chi phí caàn thieát ñeå chuyeån töø traïng thaùi T naøy sang traïng thaùi Tk ñöôïc bieåu dieãn döôùi daïng caùc con soá naèm treân cung noái giöõa hai nuùt töôïng tröng cho hai traïng thaùi. Ña soá caùc baøi toaùn thuoäc daïng maø chuùng ta ñang moâ taû ñeàu coù theå ñöôïc bieåu dieãn döôùi daïng ñoà thò; trong ñoù, moät traïng thaùi laø moät ñænh cuûa ñoà thò; taäp hôïp S bao goàm taát caû caùc traïng thaùi chính laø taäp hôïp bao goàm taát caû ñænh cuûa ñoà thò. Vieäc bieán ñoåi töø traïng thaùi Ti-1 sang traïng thaùi Ti laø - - 13
vieäc ñi töø ñænh ñaïi dieän cho Ti-1 sang ñænh ñaïi dieän cho Ti theo cung noái giöõa hai ñænh naøy. Ñeå baïn ñoïc coù theå hình dung moät caùch cuï theå baûn chaát cuûa thuaät giaûi heuristic, chuùng ta nhaát thieát phaûi naém vöõng hai chieán löôïc tìm kieám cô baûn laø tìm kieám theo chieàu saâu (Depth First Search) vaø tìm kieám theo chieàu roäng (Breath First Search). Sôû dó chuùng ta duøng töø chieán löôïc maø khoâng phaûi laø phöông phaùp laø bôûi vì trong thöïc teá, ngöôøi ta haàu nhö chaúng bao giôø vaän duïng moät trong hai kieåu tìm kieám naøy moät caùch tröïc tieáp maø khoâng phaûi söûa ñoåi gì. III.2.1. Tìm kieám chieàu saâu (Depth-First Search) Trong tìm kieám theo chieàu saâu, taïi traïng thaùi (ñænh) hieän haønh, ta choïn moät traïng thaùi keá tieáp (trong taäp caùc traïng thaùi coù theå bieán ñoåi thaønh töø traïng thaùi hieän taïi) laøm traïng thaùi hieän haønh cho ñeán luùc traïng thaùi hieän haønh laø traïng thaùi ñích. Trong tröôøng hôïp taïi traïng thaùi hieän haønh, ta khoâng theå bieán ñoåi thaønh traïng thaùi keá tieáp thì ta seõ quay lui (back-tracking) laïi traïng thaùi tröôùc traïng thaùi hieän haønh (traïng thaùi bieán ñoåi thaønh traïng thaùi hieän haønh) ñeå choïn ñöôøng khaùc. Neáu ôû traïng thaùi tröôùc naøy maø cuõng khoâng theå bieán ñoåi ñöôïc nöõa thì ta quay lui laïi traïng thaùi tröôùc nöõa vaø cöù theá. Neáu ñaõ quay lui ñeán traïng thaùi khôûi ñaàu maø vaãn thaát baïi thì keát luaän laø khoâng coù lôøi giaûi. 14 - -
Hình aûnh sau minh hoïa hoaït ñoäng cuûa tìm kieám theo chieàu saâu. Hình 1.7: Hình aûnh cuûa tìm kieám chieàu saâu. Noù chæ löu yù “môû roäng” traïng thaùi ñöôïc choïn maø khoâng “môû roäng” caùc traïng thaùi khaùc (nuùt maøu traéng trong hình veõ). III.2.2. Tìm kieám chieàu roäng (Breath-First Search) Ngöôïc laïi vôùi tìm kieám theo kieåu chieàu saâu, tìm kieám chieàu roäng mang hình aûnh cuûa veát daàu loang. Töø traïng thaùi ban ñaàu, ta xaây döïng taäp hôïp S bao goàm caùc traïng - - 15
thaùi keá tieáp (maø töø traïng thaùi ban ñaàu coù theå bieán ñoåi thaønh). Sau ñoù, öùng vôùi moãi traïng thaùi Tk trong taäp S, ta xaây döïng taäp Sk bao goàm caùc traïng thaùi keá tieáp cuûa Tk roài laàn löôït boå sung caùc Sk vaøo S. Quaù trình naøy cöù laëp laïi cho ñeán luùc S coù chöùa traïng thaùi keát thuùc hoaëc S khoâng thay ñoåi sau khi ñaõ boå sung taát caû Sk. Hình 1.8: Hình aûnh cuûa tìm kieám chieàu roäng. Taïi moät böôùc, moïi traïng thaùi ñeàu ñöôïc môû roäng, khoâng boû soùt traïng thaùi naøo. 16 - -
Chieàu saâu Chieàu roäng Tính hieäu quaû Hieäu quaû khi lôøi giaûi naèm Hieäu quaû khi lôøi giaûi naèm saâu trong caây tìm kieám vaø gaàn goác cuûa caây tìm kieám. coù moät phöông aùn choïn Hieäu quaû cuûa chieán löôïc höôùng ñi chính xaùc. Hieäu phuï thuoäc vaøo ñoä saâu cuûa quaû cuûa chieán löôïc phuï lôøi giaûi. Lôøi giaûi caøng xa thuoäc vaøo phöông aùn choïn goác thì hieäu quaû cuûa chieán höôùng ñi. Phöông aùn caøng löôïc caøng giaûm. Thuaän lôïi keùm hieäu quaû thì hieäu quaû khi muoán tìm nhieàu lôøi giaûi. cuûa chieán löôïc caøng giaûm. Thuaän lôïi khi muoán tìm chæ moät lôøi giaûi. Löôïng boä nhôù Chæ löu laïi caùc traïng thaùi Phaûi löu toaøn boä caùc traïng söû duïng ñeå chöa xeùt ñeán. thaùi. löu tröõ caùc traïng thaùi Tröôøng hôïp Veùt caïn toaøn boä Veùt caïn toaøn boä. xaáu nhaát Tröôøng hôïp Phöông aùn choïn höôùng ñi Veùt caïn toaøn boä. toát nhaát tuyeät ñoái chính xaùc. Lôøi giaûi ñöôïc xaùc ñònh moät caùch tröïc tieáp. Tìm kieám chieàu saâu vaø tìm kieám chieàu roäng ñeàu laø caùc phöông phaùp tìm kieám coù heä thoáng vaø chaéc chaén tìm ra lôøi giaûi. Tuy nhieân, do baûn chaát laø veùt caïn neân vôùi nhöõng baøi toaùn coù khoâng gian lôùn thì ta khoâng theå duøng hai chieán löôïc naøy ñöôïc. Hôn nöõa, hai chieán löôïc naøy ñeàu coù tính chaát “muø quaùng” vì chuùng khoâng chuù yù ñeán nhöõng thoâng - - 17
tin (tri thöùc) ôû traïng thaùi hieän thôøi vaø thoâng tin veà ñích caàn ñaït tôùi cuøng moái quan heä giöõa chuùng. Caùc tri thöùc naøy voâ cuøng quan troïng vaø raát coù yù nghóa ñeå thieát keá caùc thuaät giaûi hieäu quaû hôn maø ta saép söûa baøn ñeán. III.3. Tìm kieám leo ñoài III. 3.1. Leo ñoài ñôn giaûn Tìm kieám leo ñoài theo ñuùng nghóa, noùi chung, thöïc chaát chæ laø moät tröôøng hôïp ñaëc bieät cuûa tìm kieám theo chieàu saâu nhöng khoâng theå quay lui. Trong tìm kieám leo ñoài, vieäc löïa choïn traïng thaùi tieáp theo ñöôïc quyeát ñònh döïa treân moät haøm heuristic. Haøm heuristic laø gì ? Thuaät ngöõ “haøm heuristic” muoán noùi leân ñieàu gì? Chaúng coù gì gheâ gôùm. Baïn ñaõ quen vôùi noù roài! Ñoù ñôn giaûn chæ laø moät öôùc löôïng veà khaû naêng daãn ñeán lôøi giaûi tính töø traïng thaùi ñoù (khoaûng caùch giöõa traïng thaùi hieän taïi vaø traïng thaùi ñích). Ta seõ quy öôùc goïi haøm naøy laø h trong suoát giaùo trình naøy. Ñoâi luùc ta cuõng ñeà caäp ñeán chi phí toái öu thöïc söï töø moät traïng thaùi daãn ñeán lôøi giaûi. Thoâng thöôøng, giaù trò naøy laø khoâng theå tính toaùn ñöôïc (vì tính ñöôïc ñoàng nghóa laø ñaõ bieát con ñöôøng ñeán lôøi giaûi !) maø ta chæ duøng noù nhö moät cô sôû ñeå suy luaän veà maët lyù thuyeát maø thoâi ! Haøm h, ta quy öôùc raèng, luoân traû ra keát quaû laø 18 - -
moät soá khoâng aâm. Ñeå baïn ñoïc thöïc söï naém ñöôïc yù nghóa cuûa hai haøm naøy, haõy quan saùt hình sau trong ñoù minh hoïa chi phí toái öu thöïc söï vaø chi phí öôùc löôïng. 7 1 5 6 4 3 8 1 5 h’ = 6 2 7 0 1 4 5 2 0 8 6 Hình 1.9: Chi phí öôùc löôïng h’ = 6 vaø chi phí toái öu thöïc söï h = 4 + 5 = 9 (ñi theo ñöôøng 1-3-7) Baïn ñang ôû trong moät thaønh phoá xa laï maø khoâng coù baûn ñoà trong tay vaø ta muoán ñi vaøo khu trung taâm? Moät caùch suy nghó ñôn giaûn, chuùng ta seõ nhaém vaøo höôùng nhöõng toøa cao oác cuûa khu trung taâm! - - 19
Tö töôûng 1) Neáu traïng thaùi baét ñaàu cuõng laø traïng thaùi ñích thì thoaùt vaø baùo laø ñaõ tìm ñöôïc lôøi giaûi. Ngöôïc laïi, ñaët traïng thaùi hieän haønh (Ti) laø traïng thaùi khôûi ñaàu (T0) 2) Laëp laïi cho ñeán khi ñaït ñeán traïng thaùi keát thuùc hoaëc cho ñeán khi khoâng toàn taïi moät traïng thaùi tieáp theo hôïp leä (Tk) cuûa traïng thaùi hieän haønh : a. Ñaët Tk laø moät traïng thaùi tieáp theo hôïp leä cuûa traïng thaùi hieän haønh Ti. b. Ñaùnh giaù traïng thaùi Tk môùi : b.1. Neáu laø traïng thaùi keát thuùc thì traû veà trò naøy vaø thoaùt. b.2. Neáu khoâng phaûi laø traïng thaùi keát thuùc nhöng toát hôn traïng thaùi hieän haønh thì caäp nhaät noù thaønh traïng thaùi hieän haønh. b.3. Neáu noù khoâng toát hôn traïng thaùi hieän haønh thì tieáp tuïc voøng laëp. Maõ giaû Ti := T0; Stop :=FALSE; WHILE Stop=FALSE DO BEGIN IF Ti  TG THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Better:=FALSE; WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN IF THEN BEGIN ; Stop:=TRUE; END; 20 - -