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

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.
Nội dung trích xuất từ tài liệu:
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ũngChöông 1 –THUAÄT TOAÙN - THUAÄT GIAÛII. 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ù GreedyBaø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ùt4 - -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 ...