Giáo trình trí tuệ nhân tạo

–&— GIÁO TRÌNH TRÍ TUỆ NHÂN TẠO Khoa Tin học Trần Uyên Trang –&— MỤC LỤC LỜI NÓI ĐẦU CHƯƠNG I: TỔNG QUAN VỀ KHOA HỌC TRÍ TUỆ NHÂN TẠO LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TRÍ TUỆ NHÂN TẠO Năm 1950, Alan Turing – nhà toán học người Anh đã công bố công trình nghiên cứu khoa học của ông “Tính toán một cách máy móc và một cách thông minh” (Computing Machinery and Intelligence). Ông đã đưa ra trò chơi “Turing Test” như là một cách để nhận dạng máy tính thông minh. Trong trò chơi này một hoặc nhiều người có thể đặt các câu hỏi về bất kỳ lĩnh vực nào cho hai đối tượng dấu mặt: một người và một máy tính. Người đặt câu hỏi sẽ dựa vào câu trả lời để xác định đối tượng trả lời là người hay máy. Nếu có thể liên tục làm cho người phỏng vấn nghĩ rằng các câu trả lời là của con người thì máy tính đó được xem là thông minh. Đó là mốc lịch sử được công nhận là thời điểm bắt đầu phát triển của lĩnh vực khoa học Trí tuệ nhân tạo. Từ đó một loạt những chương trình ra đời, một trong những chương trình ứng dụng to lớn nhất của những năm 50 là chương trình trò chơi cờ vua (của Arthur Samuel). Hai ngôn ngữ lập trình thông minh trong lĩnh vực này cũng đươc phát triển vào những năm 50. Đầu tiên là IPL được Newell, Simon, và Shaw đưa ra trong quá trình thiết kế “Lý luận logic” (Logic Theorist). IPL là ngôn ngữ xử lý danh sách và sau này được thay thế bởi một ngôn ngữ được nhiều người biết đến là ngôn ngữ LISP. LISP được John McCarthy, một trong những người tiên phong của lĩnh vực trí tuệ nhân tạo đưa ra tại phòng thí nghiệm MIT vào cuối những năm 50 và được xem như là ngôn ngữ được chọn lựa cho những ứng dụng của trí tuệ nhân tạo. Thập niên 60 được xem như là thời kỳ thịnh vượng nhất của trí tuệ nhân tạo. Một loạt những chương trình thông minh được xây dựng: Năm 1961 chương trình tính tích phân bất định Năm 1963 các chương trình heuristics Năm 1964 chương trình giải phương trình đại số sơ cấp Năm 1966 chương trình phân tích và tổng hợp tiếng nói Năm 1968 chương trình điều khiển người máy (robot) theo đồ án “Mắt-Tay”, chương trình học nói. Năm 1972, Alain Calmerauer đưa ra ngôn ngữ lập trình Prolog Năm 1981, dự án của Nhật Bản xây dựng các máy tính thế hệ 5, lấy ngôn ngữ Prolog làm ngôn ngữ cơ sở. Trong những năm 1990, có nhiều sản phẩm dân dụng được chế tạo sử dụng kỹ thuật trí tuệ nhân tạo mà cụ thể là máy giặt, máy ảnh, các hệ thống nhận dạng, xử lý ảnh, xử lý tiếng nói… TRÍ TUỆ NHÂN TẠO LÀ GÌ ? Trí tuệ nhân tạo là lĩnh vực khoa học chuyên nghiên cứu các phương pháp để xây dựng trí tuệ cho máy giống như trí tuệ con người. Trí tuệ con người là gì ? Trí tuệ con người là khả năng giải quyết vấn đề của người đó, khả năng này thường bao gồm bốn thao tác cơ bản : Xác định các trạng thái đích của bài toán : Xét quá trình suy nghĩ giúp con người giải một bài toán. Quá trình này phải bắt đầu từ một điểm (trạng thái ban đầu) và kết thúc tại một điểm (trạng thái đích). Giữa hai trạng thái của quá trình suy nghĩ này có thể được phân ra nhiều mảnh nhỏ suy nghĩ trong đó mỗi mảnh nhỏ suy nghĩ này có thể giúp con người đạt đến một mục đích nào đó có liên quan đến lời giải của bài toán. Mỗi mảnh nhỏ như vậy được xem như một trạng thái đích từng phần hay còn gọi là lời giải từng phần của bài toán và tập các mảnh nhỏ suy nghĩ được xem như tập các trạng thái đích từng phần mà con người đã định hướng để đạt đến trạng thái đích cuối cùng hay còn gọi là lời giải của bài toán. Thu thập các sự kiện và các luật cho bài toán : Sự thông minh của mỗi con người tuỳ thuộc vào người đó có khả năng sử dụng khối tri thức có sẵn trong mỗi người để đối phó với bất kỳ tình huống nào và liên tục học từ những kinh nghiệm mới để có khả năng đáp ứng với các tình huống tương tự trong tương lai. Vấn đề thông minh được xem xét đó là thu thập các sự kiện và sử dụng các sự kiện này để đạt đến các mục đích của bài toán. Công việc này được làm xong bằng cách công thức hoá tập các luật có quan hệ đến tất cả các sự kiện được lưu trữ trong bộ óc. VD : Sự kiện và luật được thu thập để công thức hoá như sau : Sự kiện 1 : lò đang đốt thì rất nóng Luật 1 : nếu tôi đặt bàn tay lên lò đang đốt thì nó sẽ bị bỏng Sự kiện 2 : Mùa đông vào buổi tối nhiệt độ xuống rất thấp Luật 2 : nếu tôi đi ra phố vào buổi tối mùa đông khi nhiệt độ xuống thấp mà không mặc áo ấm thì sẽ bị cảm lạnh Cơ chế thu gọn của bài toán : Cơ chế thu gọn loại bỏ các đường suy nghĩ không có liên quan đến mục tiêu tức thời, chỉ tập trung đến đường suy nghĩ có khả năng đạt đến đích của bài toán. Cơ chế suy diễn của bài toán : là nơi cho phép ta giải quyết vấn đề tức thời của bài toán và đồng thời thu thập tri thức mới cho bài toán. VD : Sự kiện 1 : Ba mẹ của Nam là Lâm và Uyên Sự kiện 2 : Ba mẹ của Trân là Lâm và Uyên Hãy xác định quan hệ giữa Nam và Trân Luật được công thức hoá để giải quyết vấn đề tức thời đó là : Nếu một người nam và một người nữ có cùng ba mẹ thì họ là anh em hoặc chị em . Dựa vào luật này ta có thể đi đến kết luận : Quan hệ giữa Nam và Trân là quan hệ giữa anh em hoặc chị em Vậy, phần thông minh ở đây giúp ta giải quyết vấn đề tức thời và đồng thời cho ta một sự kiện mới về bài toán được gọi là cơ chế suy diễn. Cơ chế này giúp chúng ta có khả năng học từ kinh nghiệm vì nó có khả năng cho phép ta phát sinh ra các sự kiện mới từ các sự kiện sẵn có. Các sự kiện mới này lại được ứng dụng trong các tình huống mới để phát sinh ra các sự kiện mới hơn cho bài toán. Trí tuệ máy là gì? Trí tuệ máy là khả năng giải quyết vấn đề của máy. Người ta muốn xây dựng trí tuệ máy giống như trí tuệ con người sao cho nó có khả năng giải quyết các vấn đề như sau : Khả năng học Khả năng mô phỏng các hành vi sáng tạo của con người Khả năng trừu tượng hoá, tổng quát hoá và suy diễn Khả năng tự giải thích hành vi Khả năng thích nghi với tình huống mới (thu nạp tri thức và dữ liệu) Khả năng xử lý các biểu diễn hình thức (ký hiệu tượng trưng, danh sách) Khả năng sử dụng các tri thức và thông tin heuristics Khả năng xử lý các thông tin không đầy đủ NHỮNG ỨNG DỤNG TRONG LĨNH VỰC TRÍ TUỆ NHÂN TẠO VÀ PHẠM VI NGHIÊN CỨU Phạm vi nghiên cứu : Mục tiêu nghiên cứu để phát triển những kỹ thuật trí tuệ nhân tạo có thể nói trong phạm vi như sau : - Tìm kiếm không gian lời giải của bài toán - Thu thập tri thức từ con người - Biểu diễn tri thức bằng các quy luật và các quan hệ - Suy diễn ra những quy luật mới và những quan hệ mới - Thích nghi với tri thức mới (là vấn đề học) - Nhận dạng mẫu - Mô hình định tính - Các hệ cơ sở tri thức (dành cho các hệ chuyên gia) - Lô gích mờ (xử lý thông tin không chắc chắn) - Mạng neuron nhân tạo (cung cấp các phương pháp mới về việc suy diễn các mối quan hệ, việc học và việc nhận dạng mẫu) - Giải thuật lan truyền (genetic algorithms) cung cấp các phương pháp mới và nhanh của việc tìm kiếm không gian lời giải của bài toán. Ứng dụng trong lĩnh vực trí tuệ nhân tạo : Những ứng dụng sớm nhất của lĩnh vực trí tuệ nhân tạo gồm : Trò chơi Chứng minh định lý Giải quyết các vấn đề tổng quát Cảm nhận : nhìn và nói Hiểu được ngôn ngữ tự nhiên Giải quyết các vấn đề chuyên gia gồm : + Phân tích hoá chất + Thiết kế kỹ thuật + Các ký hiệu toán học + Chẩn đoán y khoa Một số ứng dụng trí tuệ nhân tạo được thể hiện cụ thể hoá trong các ngành kỹ thuật như lĩnh vực điều khiển và hệ thống điện gồm các ứng dụng sau : Phân tích và bảo vệ hệ thống năng lượng điện dựa trên việc xây dựng các quy luật điều khiển và cập nhật thu thập dữ liệu Các hệ điều khiển xử lý thông tin không chắc chắn và môi trường có nhiễu ứng dụng logic mờ Điều khiển không lưu để phát hiện sự cố và tránh sự va chạm sử dụng hệ cơ sở tri thức Trong điều khiển đường sắt để điều khiển tàu dừng tự động sử dụng hệ cơ sở tri thức mờ Lĩnh vực giao thông đường thuỷ : điều khiển tàu, cung cấp thông tin cho các bến cảng và tàu tránh sự va chạm Lĩnh vực giao thông đường bộ : thiết kế và bảo quản xe cộ nhờ hệ chuyên gia, vận hành xe cộ, phân tích và kiểm soát tai nạn giao thông, quản lý an toàn ra quyết định nhờ các hệ cơ sở tri thức, phương án phục vụ vận chuyển hành khách nhờ các hệ cơ sở tri thức sắp xếp, dự báo các cuộc hành trình, lý thuyết lô gích mờ được sử dụng để xử lý thông tin không chắc chắn Mạng neuron nhân tạo sử dụng các hệ thống điều khiển để nhận dạng, dự báo và điều khiển. CHƯƠNG II: CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ CƠ BẢN I. VAI TRÒ CỦA TÌM KIẾM TRONG CÁC LĨNH VỰC CỦA TRÍ TUỆ NHÂN TẠO Giới thiệu : Tìm kiếm đóng vai trò chủ đạo trong phần lớn các khái niệm liên quan đến trí tuệ nhân tạo. Giải thuật này cung cấp một bộ khung có tính chất khái niệm của hầu hết mọi phương pháp tiếp cận đến sự khám phá có tính hệ thống của những sự chọn lựa. Chúng ta sẽ bắt đầu với một vài yếu tố nền tảng, thuật ngữ, và các chiến lược thực thi cơ bản sau đó sẽ tìm hiểu bốn nhóm giải thuật tìm kiếm khác nhau về hai khía cạnh: Sự khác nhau giữa tìm kiếm thông tin không đầy đủ (uninformed search hay blind search) và tìm kiếm thông tin đầy đủ (informed search hay heuristic search). Trong đó informed search sẽ truy xuất đến những thông tin mang tính chất tác vụ chuyên biệt mà có thể được sử dụng nhằm mục đích làm cho tiến trình tìm kiếm hữu hiệu hơn. Sự khác nhau giữa phương pháp tìm kiếm theo một đường bất kỳ (any-path search) và tìm kiếm tối ưu (optimal search). Optimal search tìm kiếm một đường tốt nhất có thể trong khi any-path search chỉ giải quyết cho việc tìm kiếm đối với một vài trường hợp. Những thuật ngữ thông dụng trên cây và đồ thị tìm kiếm Những phương pháp tìm kiếm mà chúng ta sẽ gặp được định nghĩa trên cây (tree) và đồ thị (graph), nên chúng ta phải nhắc lại một số thuật ngữ cần cho những cấu trúc này. Cây được tạo từ những hình tròn và đường thẳng gọi là nút (node) và đường nối (link) được kết nối với nhau sao cho không tạo thành vòng khép kín. Nút thình thoảng được hiểu như là những đỉnh và đường nối là đường biên. (Điều này thường gặp phổ biến khi xét một đồ thị) Một cây có nút gốc (root node) tại vị trí khởi đầu của cây. Mỗi nút ngoại trừ nút gốc có một nút cha (parent) (nút ngay trước nó, ở mức cao hơn nó) leaf A B C root link node Mỗi nút ngoại trừ nút cuối cùng (ở xa nút gốc nhất) đối với mỗi nhánh,đều có một nút được nối tiếp sau nó (ở mức thấp hơn nó) gọi là nút con (children). Nút không có con như ở trên gọi là nút lá (leaf). Tree Hình 2.1 B là cha (parent) của C C là con (child) của B A là ông (ancestor) của C C là cháu (descendant) của A Đồ thị cũng là tập những nút được nối với nhau bằng các đường nối (link) và cho phép tạo thành vòng. Bên cạnh đó, một nút (node) có thể có nhiều cha (parent). Chúng ta có hai loại đồ thị: + Đồ thị có hướng (directed graph): các đường nối có hướng (gần giống như những đường một chiều) Directed graph Hình 2.2 + Đồ thị vô hướng (undirected graph): các đường nối không xác định hướng (có thể đi theo cả hai hướng) Undirected graph Hình 2.3 Vd 6.1: Xét mạng lưới đường giao thông hoặc lộ trình chuyến bay hoặc mạng máy tính. Điều chúng ta quan tâm ở đây trong tất cả mọi trường hợp là tìm kiếm một đường đi trên đồ thị thoả mãn một vài yêu cầu nào đó. Chẳng hạn như chúng ta có thể tìm kiếm một đường bất kỳ nào đó mà có số chặng là ít nhất A B C E D Lộ trình chuyến bay Hình 2.4 Tuy nhiên đồ thị còn có thể trừu tượng hơn. Xét một đồ thị được định nghĩa như sau: A B C A C B A C B A C B B C A đặt C lên A đặt C lên B đặt B lên C đặt A lên C đặt C lên A Kế hoạch hành động (planning actions) Hình 2.5 : Đồ thị biểu thị những trạng thái có thể của thế giới khối Các nút biểu thị sự mô tả trạng thái của thế giới khối, chẳng hạn một khối có thể ở trên đỉnh của một khối khác. Và ở đây các đường nối sẽ đại diện cho những hành động thay đổi từ trạng thái này sang trạng thái khác Một đường xuyên suốt đồ thị (từ nút khởi đầu đến nút đích) được gọi là “một kế hoạch hành động (plan of action)” để đạt được được một vài trạng thái đích mong đợi từ một vài trạng thái khởi đầu đã biết Đồ thị dạng này thường gặp rất nhiều trong AI. Tìm kiếm trên cây và tìm kiếm trên đồ thị Cây là một lớp con của đồ thị có hướng mặc dù đường kết nối giữa các nút trong cây không có mũi tên định hướng. Các kết nối trong cây không tạo thành vòng và mỗi nút (ngoại trừ gốc) có một cha. Khi được yêu cầu tìm kiếm trên một đồ thị chúng ta có thể chuyển đổi sang tìm kiếm tương đương trên cây thông qua 2 bước sau: Chuyển kết nối vô hướng thành hai kết nối có hướng Tránh tạo thành vòng, hay tốt hơn là không được thăm một nút hai lần. Chúng ta có thể xem xét một ví dụ chuyển đổi một đồ thị thành một cây. Giả sử ở đây, S là khởi đầu của quá trình tìm kiếm và từ đó chúng ta cố gắng để tìm ra một đường đến G thì chúng ta sẽ đi xuyên suốt đồ thị và tạo ra những kết nối từ mỗi nút đến mỗi nút được kết nối sao cho không tạo thành vòng và ngừng bất cứ khi nào chúng ta tìm được G. Lưu ý rằng mỗi cây như vậy có một nút lá cho mỗi đường không có vòng lặp trên đồ thị khởi đầu từ S. Hình 2.6 Tuy nhiên, cũng cần lưu ý rằng, mặc dù chúng ta tránh được những vòng lặp nhưng một vài nút (được minh hoạ có cùng màu trong hình) lại được gặp lại hai lần trên cây. Nói rõ hơn, những nút trùng nhau này nằm ở những đường không tạo thành vòng lặp khác nhau. Điều này có nghĩa là một tiến trình tìm kiếm hoàn chỉnh trên cây này có thể sẽ có một số công đoạn thừa. Vấn đề của việc phải nỗ lực như thế nào để tránh được vòng lặp và tránh được thăm viếng thừa đến một số nút là một vấn đề quan trọng mà chúng ta sẽ xem xét lại sau này khi chúng ta thảo luận đến những thuật toán tìm kiếm khác nhau. Phân loại các giải thuật tìm kiếm Có nhiều loại thuật toán tìm kiếm. Chúng ta sẽ gặp một loạt các thuật toán tìm kiếm từ đơn giản nhưng ít hiệu quả cho đến thuật toán tối ưu nhất nhưng lại phức tạp theo bảng sau: Loại Tên giải thuật Phương thức hoạt động Any Path Uninformed Depth-First Breadth-First Tìm kiếm một cách hệ thống trên toàn bộ cây cho đến khi nút đích được tìm thấy Any Path Informed Best-First Sử dụng phương pháp đo lường (heuristic) cụ thể phần tốt nhất của một trạng thái để đạt đến đích nhanh nhất hoặc tìm thấy trạng thái đích mong đợi Optimal Uninformed Uniform-Cost Sử dụng phương pháp đo chiều dài của đường (path length), đảm bảo tìm ra đường ngắn nhất Optimal Informed A* Sử dụng phương pháp đo chiều dài đường và khai thác thông tin heuristic đảm bảo tìm ra đường ngắn nhất nhưng nhanh hơn so với phương pháp uninformed II. ĐỊNH NGHĨA KHÔNG GIAN CỦA BÀI TOÁN Hai thành phần cơ bản của lĩnh vực trí tuệ nhân tạo đó là biểu diễn tri thức và tìm kiếm tri thức trong miền đã được biểu diễn. Tri thức của một bài toán có thể được phân ra làm 3 loại: tri thức mô tả, tri thức thủ tục và tri thức điều khiển. - Tri thức mô tả: để mô tả các sự kiện, các quan hệ giữa các sự kiện, đối tượng, các tính chất của bài toán. - Tri thức thủ tục: là các thủ tục để giải bài toán được thể hiện bằng các luật dưới dạng if-then - Tri thức điều khiển: là loại tri thức heuristics có khả năng thực hiện hai chức năng đó là chọn luật thích hợp để đưa ra ứng dụng và thu gọn không gian tìm kiếm của bài toán. Tập các luật sẽ giúp định nghĩa không gian của bài toán hay còn gọi là không gian trạng thái tìm kiếm của bài toán. Không gian của bài toán được biểu diễn bằng đồ thị sẽ là công cụ giúp người lập trình có khả năng phân tích và dự báo các đặc thù của bài toán cụ thể như khả năng phân rã bài toán mẹ ra nhiều bài toán con, chọn chiến lược và giải thuật thích hợp với các đặc thù của bài toán, đường dẫn đến lời giải của bài toán phải được đảm bảo tối ưu… Không gian trạng thái tìm kiếm của bài toán được định nghĩa sử dụng lý thuyết đồ thị như sau: không gian trạng thái tìm kiếm của bài toán được biểu diễn bằng đồ thị gồm tập bốn thành phần [N, A, S, G] trong đó: N: tập các đỉnh hay các trạng thái của đồ thị A: tập các cung hay các liên kết giữa các đỉnh. Liên kết này tương ứng với các bước trong quá trình giải quyết bài toán S: tập con của N chứa các trạng thái ban đầu của bài toán G: tập con của N chứa các trạng thái đích của bài toán Đường đi đến lời giải của bài toán đó là đường thông qua đồ thị bắt đầu từ một đỉnh trong S đến một đỉnh trong G. Vd 2.1: Cho hai bình đựng chất lỏng, một bình có dung tích 4 lít và một bình có dung tích 3 lít. Cả hai bình không có dấu dung tích. Có thể dùng một đường ống để làm đầy nước ở hai bình. Làm thế nào để có chính xác 2 lít nước trong bình 4 lít. Hãy biểu diễn không gian của bài toán bằng đồ thị? Không gian của bài toán có thể được mô tả bằng các cặp số nguyên (x, y), trong đó x = 0, 1, 2, 3, 4 biểu diễn số lít nước trong bình 4 lít và y = 0, 1, 2, 3 biểu diễn số lít nước trong bình 3 lít. Trạng thái ban đầu của bài toán là hai bình đều rỗng, do đó ta có cặp số nguyên (0, 0). Trạng thái đích của bài toán là có 2 lít nước trong bình 4 lít, do đó ta sẽ có (2, n), với n là giá trị bấtkỳ từ 0->3. Không gian của bài toán được định nghĩa bằng tri thức thủ tục của bài toán đó chính là các luật để giải bài toán được thiết kế như sau: - Luật 1: Nếu x < 4 thì làm đầy bình 4 lít: (x, y / x < 4) à (4, y) - Luật 2: Nếu y < 3 thì làm đầy bình 3 lít: (x, y / y < 3) à (x, 3) - Luật 3: Nếu x > 0 thì làm rỗng bình 4 lít: (x, y / x > 0) à (0, y) - Luật 4: Nếu y > 0 thì làm rỗng bình 3 lít: (x, y / y > 0) à (x, 0) - Luật 5: Nếu x + y >=4 và y > 0 thì đưa nước từ bình 3 lít sang bình 4 lít cho đến khi bình 4 lít đầy: (x, y / x + y >=4 ^ y > 0) à (4, y – (4 – x)) - Luật 6: Nếu x + y >=3 và x > 0 thì đưa nước từ bình 4 lít sang bình 3 lít cho đến khi bình 3 lít đầy: (x, y / x + y >=3 ^ x > 0) à (x – (3 – y), 3) - Luật 7: Nếu x + y 0 thì đưa tất cả nước từ bình 3 lít sang bình 4 lít: (x, y / x + y 0) à (x + y, 0) - Luật 8: Nếu x + y 0 thì đưa tất cả nước từ bình 4 lít sang bình 3 lít: (x, y / x + y 0) à (0, x + y) Từ trạng thái ban đầu của bài toán là (0, 0) thoả mãn hai luật 1 và 2 phát sinh 2 trạng thái mới (4, 0) và (0, 3). Tại trạng thái mới (4, 0) thoả mãn ba luật 2, 3, 6 phát sinh ra 3 trạng thái mới hơn là (4, 3), (0, 0) và (1, 3). Tại trạng thái mới (0, 3) cũng thoả mãn ba luật 1, 4, 7 phát sinh ra 3 trạng thái mới hơn là (4, 3), (0, 0) và (3, 0). Quá trình phát sinh như thế cứ tiếp diễn cho đến khi có một trạng thái bất kỳ (2, n) xuất hiện thì dừng. Số trạng thái được phát sinh kể cả trạng thái ban đầu và trạng thái đích được gọi là không gian của bài toán. (0, 0) (3, 0) (0, 0) (4, 3) (1, 3) (0, 0) (4, 3) (0, 3) (4, 0) 1 2 2 3 6 1 4 7 Hình 2.7 Một phần không gian trạng thái của bài toán bình đựng nước được biểu diễn bằng đồ thị Vd 2.2: Xét bài toán hành trình người bán hàng.Giả sử người bán hàng có năm thành phố cần đến giao hàng và sau đó phải trở về nhà. Mục đích của bài toán là tìm đường đi ngắn nhất cho cuộc hành trình người bán hàng để đi đến tất cả các thành phố, mỗi thành phố ông ta chỉ đến một lần và sau đó trở về lại thành phố bắt đầu cuộc hành trình A B C D E 100 50 100 125 75 50 125 125 75 100 Hình 2.8 A C D E D E D B E D C E C B C E D A A E A E Hình 2.9 Hình 2.8 là một ví dụ cụ thể của bài toán trên. Hãy biểu diễn không gian trạng thái của bài toán Giả sử cuộc hành trình của người bán hàng bắt đầu từ thành phố A và trở về lại A. Không gian của bài toán này là số đường đi khác nhau, trong đó sẽ có một đường đi ngắn nhất cho cuộc hành trình. Nếu cuộc hành trình đi qua n thành phố, ta sẽ có số (n-1)! đường đi khác nhau. Hình 2.9 mô tả một phần không gian trạng thái của bài toán. III. CÁC CHIẾN LƯỢC CHO KHÔNG GIAN TRẠNG THÁI TÌM KIẾM Tìm kiếm hướng dữ liệu và hướng đích Một không gian trạng thái có thể được tìm kiếm trong hai hướng : từ dữ liệu được cho của bài toán tiến đến đích hoặc từ đích lùi về dữ liệu. Trong hướng tìm kiếm từ dữ liệu còn được gọi là chuỗi suy diễn tiến, người giải bài toán bắt đầu với các sự kiện được cho của bài toán và tập các luật để thay đổi trạng thái. Diễn biến tìm kiếm bằng cách ứng dụng các luật với các vế bên trái của chúng thoả mãn các sự kiện để sản xuất ra các sự kiện mới, cách như vậy được sử dụng cho các luật để phát sinh ra các sự kiện mới hơn. Quá trình này tiếp tục cho đến khi ta hy vọng nó phát sinh ra một đường mà đường đó thoả mãn điều kiện đích. Trong hướng tìm kiếm từ đích lùi về dữ liệu còn được gọi là chuỗi suy diễn lùi, người giải bài toán bắt đầu từ sự kiện đích được cho của bài toán và tập các luật để thay đổi trạng thái. Diễn biến tìm kiếm bằng cách chọn tất cả các luật mà các vế bên phải của chúng đã phát sinh ra sự kiện đích và xác định các sự kiện ở các vế bên trái của các luật cho phép phát sinh ra các đỉnh đích này. Các sự kiện này trở thành các đích mới cho công việc tìm kiếm. Tìm kiếm tiếp tục cho đến khi các sự kiện ban đầu của bài toán được tìm thấy. Vd 2.3: Xét bài toán bình đựng nước. Có hai cách để giải bài toán : Tìm kiếm từ dữ liệu đến đích, minh hoạ ở hình 2.10 Tìm kiếm từ đích lùi về dữ liệu, minh hoạ ở hình 2.11 (0, 0) (3, 0) (0, 0) (4, 3) (1, 3) (0, 0) (4, 3) (0, 3) (4, 0) 1 2 2 3 6 1 4 7 Hình 2.10 Hình 2.10 hướng tìm kiếm bắt đầu từ dữ liệu ban đầu (0, 0). Ứng dụng các luật 1, 2 đến trạng thái này để sản xuất ra các trạng thái mới (4, 0) và (0, 3). Tìm kiếm tiếp tục để phát sinh ra các trạng thái mới hơn cho đến khi có một đỉnh đích (2, n) được tìm thấy thì dừng. (2, 0) (0, 2) (2, 3) Hình 2.11 Hình 2.11, hướng tìm kiếm bắt đầu từ đích (2, 0). Chọn tất cả các luật mà vế bên phải của chúng có khả năng phát sinh ra đỉnh đích này, đó là luật 4, 7 và xác định các điều kiện thoả mãn các luật để phát sinh ra đỉnh đích này đó là (0, 2) và (2, 3). Các điều kiện này trở thành các đích mới cho công việc tìm kiếm. Tìm kiếm tiếp tục cho đến khi tìm thấy sự kiện ban đầu (0, 0) của bài toán xuất hiện thì dừng. Giải thuật truyền lùi (back tracking) Trong cách giải bài toán sử dụng hướng tìm kiếm đích hoặc dữ liệu, thông qua đồ thị không gian trạng thái chúng ta phải tìm được một đường từ trạng thái ban đầu đến trạng thái đích. Sự nối tiếp của các cung trong đường này tương ứng với thứ tự các bước của lời giải. Chúng ta phải xem xét nhiều đường khác nhau cho đến khi đích mong muốn được tìm thấy. Giải thuật truyền lùi là một công cụ cần thiết cho việc tìm kiếm này. Tìm kiếm truyền lùi bắt đầu tại trạng thái ban đầu và diễn tiếp một đường cho đến khi nó đạt đến đích hay đường cụt. - Nếu tìm thấy đích, dừng và thiết lập một đường đi đến lời giải. - Nếu đến đường cụt, nó truyền lùi về đỉnh gần nhất trên đường chưa được duyệt qua và tiếp tục nhìn xuống một trong các nhánh của đỉnh này. Giải thuật truyền lùi sử dụng 3 danh sách: SL, NSL và DE: SL: danh sách trạng thái, liệt kê các trạng thái trên đường đi hiện hành đang được duyệt qua. Nếu đích được tìm thấy, SL sẽ là danh sách chứa thứ tự của các trạng thái trên đường đi đến lời giải của bài toán. NSL: danh sách trạng thái mới, chứa các đỉnh đang chờ được duyệt qua, chẳng hạn các đỉnh chưa được phát sinh và chưa được tìm kiếm. DE: danh sách chứa các đỉnh của các đường cụt Giải thuật được mô tả như sau: function backtrack; begin SL:= [Start]; NSL:= [Start]; DE = [ ]; CS:= Start; while NSL ≠ [ ] do begin if CS = goal then return (SL); if CS không có kế thừa (ngoại trừ các đỉnh đã có sẵn trên DE, SL, NSL) then begin while SL ≠ [ ] và CS = phần tử đầu tiên của SL do begin cộng CS vào DE; // ghi nhận trạng thái như đỉnh cụt loại // bỏ phần tử đầu tiên từ SL // truyền lùi loại bỏ phần tử đầu tiên từ NSL CS:= phần tử đầu tiên của NSL; end; cộng CS vào SL; end; else begin đặt các con của CS vào NSL (trừ các đỉnh đã có sẵn trên DE, SL, NSL); CS:= phần tử đầu tiên của NSL; cộng CS vào SL end end; return FAIL; end. Vd 2.4 Cho không gian trạng thái của bài toán như hình 2.12 dưới đây. Hãy sử dụng giải thuật truyền lùi để xây dựng đường đi đến lời giải của bài toán đích là G bắt đầu từ trạng thái ban đầu A? A1 C8 B2 G9 J7 F6 E3 I5 H4 D10 Hình 2.12 Với A, B, C, D, E, F, G, H, I, và J là tên các đỉnh, các chữ số 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 đánh dấu số thứ tự của các đỉnh được duyệt qua và các mũi tên có đường không liên tục chỉ hướng tìm kiếm trong không gian trạng thái của bài toán. Sử dụng giải thuật truyền lùi với đồ thị biểu diễn không gian trạng thái trên, ta có kết quả theo bảng sau: Đầu tiên: Gán SL = [A]; NSL = [A]; DE = [ ]; CS = A; Vòng lặp CS SL NSL DE 0 A [A] [A] [ ] 1 B [BA] [BCDA] [ ] 2 E [EBA] [EFBCDA] [ ] 3 H [HEBA] [HIEFBCDA] [ ] 4 I [IEBA] [IEFBCDA] [H] 5 F [FBA] [FBCDA] [EIH] 6 J [JFBA] [JFBCDA] [EIH] 7 C [CA] [CDA] [BFJEIH] 8 G [GCA] [GCDA] [BFJEIH] Kết quả được biểu diễn trên đây sử dụng giải thuật truyền lùi với chiến lược suy diễn tiến, lấy đỉnh gốc của đồ thị làm trạng thái ban đầu và đánh giá con của nó để tìm kiếm đường đến đích. Giải thuật cũng có thể sử dụng với chiến lược suy diễn lùi, lấy đỉnh gốc của đồ thị l