Giáo trình về môn Trí tuệ nhân tạo

Có nhiều quan điểm khác nhau về TTNT. Mỗi quan điểm đứng trên một góc độ tiếp cận và cách ứng dụng TTNT vào cuộc sống. Cho lên việc xây dựng định nghĩa về TTNT là khác nhau. Khi đó có nhiều định nghĩa khác nhau về TTNT. Theo M.Misky: TTNT là một ngành khoa học nhằm mô phỏng bằng máy tính về hành vi thông minh của con người. Đối với những người xây dựng và khai thác tri thức thì TTNT là một chuyên ngành thuộc công nghệ thông tin, khi nghiên cứu dựa trên 2 khía cạnh:...
Nội dung trích xuất từ tài liệu:
Giáo trình về môn Trí tuệ nhân tạo Chương 1. GIỚI THIỆU CHUNG VỀ TTNT 1 Trí tuệ nhân tạo Có nhiều quan điểm khác nhau về TTNT. Mỗi quan điểm đứng trên một góc độ tiếp cận và cách ứng dụng TTNT vào cuộc sống. Cho lên việc xây dựng định nghĩa về TTNT là khác nhau. Khi đó có nhiều định nghĩa khác nhau về TTNT. Theo M.Misky: TTNT là một ngành khoa học nhằm mô phỏng bằng máy tính về hành vi thông minh của con người. Đối với những người xây dựng và khai thác tri thức thì TTNT là một chuyên ngành thuộc công nghệ thông tin, khi nghiên cứu dựa trên 2 khía cạnh: + Nghiên cứu bản chất hoạt động trí tuệ của bộ não con người. + Mô phỏng những hoạt động trí tuệ của bộ não con người trên các thiết bị máy. Để giải quyết các tình huống thông thường con người thường phải trải qua một loạt những giai đoạn sau: + Thu nhận thông tin về tình huống + Khả năng nhớ + Tổ chức thành những tình huống + Xử lý tình huống + Đưa ra những lời giải cho hành động 2 Vai trò của TTNT trong ngành CNTT - Theo 1 nghĩa nào đó TTNT tạo nên 1 cách đơn giản để xây dựng lên cấu trúc các chương trình ra quyết định phức tạp đòi hỏi phải dựa trên những tri thức nhất định. - Các chương trình TTNT hoạt động giống như bộ não của con người tức là nó có thể tích hợp những tri thức mới mà không cần thay đổi lại cách làm việc. Vì vậy những chương trình TTNT có thể dễ dàng cải tiến hơn so với các chương trình truyền thống. - Khi máy tính được trang bị những phần mềm TTNT kết hợp với môi trường làm việc thí có thể cho phép giải quyết được các bài toán cỡ lớn và phân tán. - Một số phần mềm TTNT thể hiện tính thích nghi và mềm dẻo đối với các l ớp bài toán thuộc nhiều lĩnh vực khác nhau. 3 Các ứng dụng - Tìm kiếm - Biểu diễn tri thức và lập luận - Lập kế hoạch - Robotisc - Learning - Nhận dạng…. 4 Lịch sử phát triển của TTNT 2 - Vào những năm 30 Allen Turing có đưa ra lý thuyết về một loại chương trình có thể lưu trữ trong bộ nhớ sau đó thực hiện trên cơ sở các phép toán thao tác với đại lượng “0” và “1” - Năm 1956: những chương trình dẫn xuất kết luận trong hệ hình thức được công bố - Năm 1960: McCathy đưa ra ngôn ngữ lập trình đầu tiên cho TTNT là LISP - Năm 1964: ELIZA được xây dựng thành công ở MỸ có khả năng hoạt động như một chuyên gia phân tích tâm lý. - Năm 1970: Có 1 số nghiên cứu cơ bản về xử lý ngôn ngữ t ự nhiên biểu di ễn tri thức, lý thuyết giải quyết vấn đề. - Năm 1972: Ngôn ngữ Prolog ra đời - Năm 1981: Các nghiên cứu về trí tuệ được triển khai vào thực tế khá nhiều. - Đầu những năm 90 thị trường đã có những sản phẩm dân dụng của trí tuệ. - Trong những năm gần đây việc xây dựng các hệ thống máy thông minh là một trong những hướng đi chính của nhiều công ty. Càng ngày các hệ thống càng trợ giúp con người trong nhiều lĩnh vực thực hiên và có sự mềm dẻo trong qua trình xử lý. 3 Giải quyết vấn đề bằng tìm kiếm ----------------------------------- VÊn ®Ò t×m kiÕm, mét c¸ch tæng qu¸t, cã thÓ hiÓu lµ t×m mét ®èi tîng tháa m·n mét sè ®ßi hái nµo ®ã, trong mét tËp hîp réng lín c¸c ®èi tîng. Chóng ta cã thÓ kÓ ra rÊt nhiÒu vÊn ®Ò mµ viÖc gi¶i quyÕt nã ®îc quy vÒ vÊn ®Ò t×m kiÕm. C¸c trß ch¬i, ch¼ng h¹n cê vua, cê car« cã thÓ xem nh vÊn ®Ò t×m kiÕm. Trong sè rÊt nhiÒu níc ®i ®îc phÐp thùc hiÖn, ta ph¶i t×m ra c¸c níc ®i dÉn tíi t×nh thÕ kÕt cuéc mµ ta lµ ngêi th¾ng. Chøng minh ®Þnh lý còng cã thÓ xem nh vÊn ®Ò t×m kiÕm. Cho mét tËp c¸c tiªn ®Ò vµ c¸c luËt suy diÔn, trong trêng hîp nµy môc tiªu cña ta lµ t×m ra mét chøng minh (mét d·y c¸c luËt suy diÔn ®îc ¸p dông) ®Ó ®îc ®a ®Õn c«ng thøc mµ ta cÇn chøng minh. Trong c¸c lÜnh vùc nghiªn cøu cña TrÝ TuÖ Nh©n T¹o, chóng ta thêng xuyªn ph¶i ®èi ®Çu víi vÊn ®Ò t×m kiÕm. §Æc biÖt trong lËp kÕ ho¹ch vµ häc m¸y, t×m kiÕm ®ãng vai trß quan träng. Trong phÇn nµy chóng ta sÏ nghiªn cøu c¸c kü thuËt t×m kiÕm c¬ b¶n ®îc ¸p dông ®Ó gi¶i quyÕt c¸c vÊn ®Ò vµ ®îc ¸p dông réng r·i trong c¸c lÜnh vùc nghiªn cøu kh¸c cña TrÝ TuÖ Nh©n T¹o. Chóng ta lÇn lît nghiªn cøu c¸c kü thuËt sau: • C¸c kü thuËt t×m kiÕm mï, trong ®ã chóng ta kh«ng cã hiÓu biÕt g× vÒ c¸c ®èi tîng ®Ó híng dÉn t×m kiÕm mµ chØ ®¬n thuÇn lµ xem xÐt theo mét hÖ thèng nµo ®ã tÊt c¶ c¸c ®èi tîng ®Ó ph¸t hiÖn ra ®èi tîng cÇn t×m. • C¸c kü thuËt t×m kiÕm kinh nghiÖm (t×m kiÕm heuristic) trong ®ã chóng ta dùa vµo kinh nghiÖm vµ sù hiÓu biÕt cña chóng ta vÒ vÊn ®Ò cÇn gi¶i quyÕt ®Ó x©y dùng nªn hµm ®¸nh gi¸ híng dÉn sù t×m kiÕm. • C¸c kü thuËt t×m kiÕm tèi u. • C¸c ph¬ng ph¸p t×m kiÕm cã ®èi thñ, tøc lµ c¸c chiÕn lîc t×m kiÕm níc ®i trong c¸c trß ch¬i hai ngêi, ch¼ng h¹n cê vua, cê tíng, cê car«. 4 Chương 2. CÁC CHIẾN LƯỢC TÌM KIẾM MÙ Trong chương này, chúng tôi sẽ nghiên cứu các chiến lược tìm kiếm mù (blind search): tìm kiếm theo bề rộng (breadth-first search) và tìm kiếm theo độ sâu (depth- first search). Hiệu quả của các phương pháp tìm kiếm này cũng sẽ được đánh giá. 2.1 Biểu diễn vấn đề trong không gian trạng thái Một khi chúng ta muốn giải quyết một vấn đề nào đó bằng tìm kiếm, đ ầu tiên ta phải xác định không gian tìm kiếm. Không gian tìm kiếm bao gồm tất cả các đối tượng mà ta cần quan tâm tìm kiếm. Nó có thể là không gian liên tục, chẳng hạn không gian các véctơ thực n chiều; nó cũng có thể là không gian các đ ối tượng r ời rạc. Trong mục này ta sẽ xét việc biểu diễn một vấn đề trong không gian trạng thái sao cho việc giải quyết vấn đề được quy về việc tìm kiếm trong không gian trạng thái. Một phạm vi rộng lớn các vấn đề, đặc biệt các câu đố, các trò chơi, có thể mô t ả bằng cách sử dụng khái niệm trạng thái và toán tử (phép biến đổi trạng thái). Chẳng hạn, một khách du lịch có trong tay bản đồ mạng lưới giao thông nối các thành phố trong một vùng lãnh thổ (hình 1.1), du khách đang ở thành phố A và anh ta muốn tìm đường đi tới thăm thành phố B. Trong bài toán này, các th ...