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

176 trang hapham 1720

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Trí tuệ nhân tạo", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_tri_tue_nhan_tao.pdf

Nội dung text: Giáo trình Trí tuệ nhân tạo

Giáo trình Trí tuệ nhân tạo 2
Chương 0 MỞ ĐẦU 1. Tổng quan về khoa học Trớ tuệ nhõn tạo. Trong Công Nghệ Thông Tin, Trí Tuệ Nhân Tạo (Artificial Intelligence) là một ngành mới, nhưng phát triển rất mạnh mẽ và đem lại nhiều kết quả to lớn. Con người thường tự cho mỡnh là sinh vật thụng minh vỡ khả năng trí tuệ đóng vai trũ quan trong trong cuộc sống. Trong văn học cũng đó từng cú những cõu chuyện đề cao về trí thông minh của con người. Trớ Tuệ Nhõn Tạo chỉ mới hỡnh thành từ năm 1956. Tuy nhiên, việc nghiên cứu trí tuệ đó cú từ lõu. Trờn 2000 năm trước, các nhà triết học đó tỡm hiểu về cỏch thức nhỡn nhận, học tập, nhớ và suy lý. Việc ra đời của máy tính điện tử vào những năm 50 của thế kỷ 20 đó sinh ra khuynh hướng đưa các lĩnh vực nghiên cứu trí tuệ về các vấn đề lý thuyết và thực nghiệm trờn mỏy. 1.1. Đối tượng và mục tiêu nghiên cứu của trí tuệ nhân tạo. Trớ tuệ nhõn tạo nghiờn cứu về cỏch hành xử thụng minh (intelligent behaviour) với mục tiờu là xõy dựng lý thuyết đầy đủ về thông minh để có thể giải thích được hoạt động thông minh của sinh vật và áp dụng được các hiểu biết vào các máy móc nói chung, nhằm phục vụ cho con người. - Về mặt kỹ thuật: Tạo ra các máy thông minh để giải quyết vấn đề thực tế dùng các kỹ thuật AI. - Khoa học: Phát triển các khái niệm và thuật ngữ để hiểu được cỏc hành xử thụng minh của sinh vật. 1.2. Vai trũ của Trớ Tuệ Nhõn Tạo. 3
Trí tuệ nhân tạo bao quát rất nhiều lĩnh vực nghiên cứu hẹp. Nó nghiên cứu từ các lĩnh vực tổng quát như máy nhận biết, suy luận logic, đến các bài toán như chơi cờ, chứng minh định lý. Thường thỡ cỏc nhà khoa học ở cỏc lĩnh vực khỏc tỡm đến với trí tuệ nhân tạo ở các kỹ thuật hệ thống hoá và tự động hoá các xử lý tri thức cũng như các phương pháp thuộc lĩnh vực mang tính người. Trớ tuệ nhõn tạo nghiờn cứu kỹ thuật làm cho mỏy tớnh cú thể “suy nghĩ một cỏch thụng minh” và mụ phỏng quỏ trỡnh suy nghĩ của con người khi đưa ra những quyết định, lời giải. Trên cơ sở đó, thiết kế các chương trỡnh cho mỏy tớnh để giải quyết bài toán. Sự ra đời và phát triển của Trí tuệ nhân tạo đó tạo ra một bước nhảy vọt về chất trong kỹ thuật và kỹ nghệ xử lý thụng tin. Trớ tuệ nhõn tạo chớnh là cơ sở của công nghệ xử lý thông tin mới, độc lập với công nghệ xử lý thông tin truyền thống dựa trên văn bản giấy tờ. Điều này được thể hiện qua các mặt sau: - Nhờ những cụng cụ hỡnh thức hoỏ (cỏc mụ hinh logic ngụn ngữ, logic mờ, ), cỏc tri thức thủ tục và tri thức mụ tả cú thể biểu diễn được trong máy. Do vậy quá trỡnh giải bài toỏn được tiến hành hữu hiệu hơn. - Mụ hỡnh logic ngụn ngữ đó mở rộng khả năng ứng dụng của máy tính trong lĩnh vực đũi hỏi tri thức chuyờn gia ở trỡnh độ cao, rất khó như: y học, sinh học, địa lý, tự động hóa. - Một số phần mềm trí tuệ nhân tạo thể hiện tính thích nghi và tính 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. - Khi mỏy tính được trang bị các phần mềm trí tuệ nhân tạo ghép mạng sẽ cho phép giải quyết những bài toán cỡ lớn và phân tán. 1.3. Cỏc kỹ thuật Trớ tuệ nhõn tạo. Cú nhiều kỹ thuật nghiờn cứu, phỏt triển ngành khoa học Trớ tuệ nhõn tạo. Tuy vậy, cỏc kỹ thuật Trớ tuệ nhõn tạo thường khá phức tạp khi cài đặt cụ thể, lý do là cỏc kỹ thuật này thiờn về xử lý cỏc ký hiệu tượng trưng và đũi hỏi phải sử dụng những tri thức chuyờn mụn thuộc nhiều lĩnh vực khỏc nhau. 4
Do vậy, các kỹ thuật Trí tuệ nhân tạo hướng tới khai thác những tri thức về lĩnh vực đang quan tâm được mó hoỏ trong mỏy sao cho đạt được mức độ tổng quát; dễ hiểu, dễ diễn đạt thông qua ngôn ngữ chuyên môn gần gũi với ngôn ngữ tự nhiên; dễ sửa đổi, hiệu chỉnh, dễ sử dụng, khai thác nhằm thu hẹp các khả năng cần xét để đi tới lời giải cuối cùng. Các kỹ thuật Trí tuệ nhân tạo cơ bản bao gồm : - Lý thuyết giải bài toỏn và suy diễn thụng minh: Lý thuyết giải bài toỏn cho phộp viết cỏc chương trỡnh giải cõu đố, chơi các trũ chơi thông qua các suy luận mang tính người; các hệ thống chứng minh định lý. Ngoài ra các hệ thống hỏi đáp thông minh cũn cho phộp lưu trữ và xử lý khối lượng lớn các thông tin. - Lý thuyết tỡm kiếm may rủi: Lý thuyết này bao gồm cỏc phương pháp và kỹ thuật tỡm kiếm với sự hỗ trợ của thụng tin phụ để giải bài toỏn một cỏch cú hiệu quả. - Cỏc ngụn ngữ về Trớ tuệ nhõn tạo: Để xử lý các tri thức người ta không chỉ sử dụng các ngôn ngữ lập trỡnh dựng cho cỏc xử lý dữ liệu số, mà cần cú ngụn ngữ khỏc. Cỏc ngụn ngữ chuyờn dụng này cho phộp lưu trữ và xử lý thụng tin ký hiệu. Một số ngôn ngữ được nhiều người biết đến là IPL.V,LISP, PROLOG. - Lý thuyết thể hiện tri thức và hệ chuyờn gia: Trí tuệ nhân tạo là khoa học về thể hiện và sử dụng tri thức. Mạng ngữ nghĩa, lược đồ, logic vị từ, khung là các phương pháp thể hiện tri thức thông dụng. Việc gắn liền cách thể hiện và sử dụng tri thức là cơ sở hỡnh thành hệ chuyờn gia. - Lý thuyết nhận dạng và xử lý tiếng núi: Giai đoạn phát triển đầu của Trí tuệ nhân tạo gắn với lý thuyết nhận dạng. Các phương pháp nhận dạng chính gồm: nhận dạng hỡnh học, nhận dạng dựng tõm lý học, nhận dạng theo phương pháp hàm thế, dùng máy nhận dạng. ứng dụng của phương pháp này trong việc nhận dạng chữ viết, âm thanh. 5
- Người máy: Cuối những năm 70, người máy trong công nghiệp đó đạt được nhiều tiến bộ. Người máy có bộ phận cảm nhận và các cơ chế hoạt động được nối ghép theo sự điều khiển thông minh. Khoa học về cơ học và Trí tuệ nhân tạo được tích hợp trong khoa học người máy. - Tõm lý học xử lý thụng tin : Cỏc kết quả nghiờn cứu của tõm lý học giỳp Trớ tuệ nhân tạo xây dựng các cơ chế trả lời theo hành vi, có ý thức; nú giỳp cho việc thực hiện cỏc suy diễn mang tớnh người. - Ngoài ra, xử lý danh sách, kỹ thuật đệ quy, kỹ thuật quay lui và xử lý cỳ phỏp hỡnh thức là những kỹ thuật cơ bản của tin học truyền thống có liên quan trực tiếp đến Trí tuệ nhân tạo. 2. Lịch sử phỏt triển của Trớ Tuệ Nhõn Tạo. Lịch sử của Trí tuệ nhân tạo cho thấy ngành khoa học này có nhiều kết quả đáng ghi nhận. Theo các mốc phát triển, người ta thấy Trí tuệ nhân tạo được sinh ra từ những năm 50 với các sự kiện sau: Turing được coi là người khai sinh ngành Trí tuệ nhân tạo bởi phát hiện của ông về máy tính có thể lưu trữ chương trỡnh và dữ liệu. Tháng 8/1956 J.Mc Carthy, M. Minsky, A. Newell, Shannon. Simon , đưa ra khái niêm “trí tuệ nhõn tạo”. Vào khoảng năm 1960 tại Đại học MIT (Massachussets Institure of Technology) ngôn ngữ LISP ra đời, phù hợp với các nhu cầu xử lý đặc trưng của trí tuệ nhân tạo - đó là ngôn ngữ lập trỡnh đầu tiên dùng cho trí tuệ nhân tạo. Thuật ngữ Trớ tuệ nhân tạo được dùng đầu tiên vào năm 1961 cũng tại MIT. Những năm 60 là giai đoạn lạc quan cao độ về khả năng làm cho máy tính biết suy nghĩ. Trong giai đoạn này người ta đó được chứng kiến máy chơi cờ đầu tiên và các chương trỡnh chứng minh định lý tự động. 6
Cụ thể: 1961: Chương trỡnh tớnh tớch phõn bất định 1963: Các chương trỡnh Heuristics: Chương trỡnh chứng minh cỏc định lý hỡnh học khụng gian cú tờn là “tương tự”, chương trỡnh chơi cờ của Samuel. 1964: Chương trỡnh giải phương trỡnh đại số sơ cấp, chương trỡnh trợ giỳp ELIZA (cú khả năng làm việc giống như một chuyên gia phân tich tâm lý). 1966: Chương trỡnh phõn tớch và tổng hợp tiếng núi 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. Vào những năm 60, do giới hạn khả năng của các thiết bị, bộ nhớ và đặc biệt là yếu tố thời gian thực hiện nên có sự khó khăn trong việc tổng quát hoá các kết quả cụ thể vào trong một chương trỡnh mềm dẻo thụng minh. Vào những năm 70, máy tính với bộ nhớ lớn và tốc độ tính toán nhanh nhưng các phương pháp tiếp cận Trí tuệ nhân tạo cũ vẫn thất bại (do sự bùng nổ tổ hợp trong quá trỡnh tỡm kiếm lời giải cỏc bài toỏn đặt ra). Vào cuối những năm 70 một vài kết quả như xử lý ngụn ngữ tự nhiờn, biểu diễn tri thức và giải quyết vấn đề. Những kết quả đó đó tạo điều kiện cho sản phẩm thương mại đầu tiên của Trí tuệ nhân tạo ra đời đó là Hệ chuyên gia, được đem áp dụng trong các lĩnh vực khác nhau (Hệ chuyên gia là một phần mềm máy tính chứa các thông tin và tri thức về một lĩnh vực cụ thể nào đó, có khả năng giải quyết những yêu cầu của người sử dụng trong một mức độ nào đó, ở một trỡnh độ như một chuyên gia con người có kinh nghiệm khá lâu năm). Một sự kiện quan trọng vào những năm 70 là sự ra đời ngôn ngữ Prolog, tương tự LISP nhưng nó có cơ sở dữ liệu đi kèm. 7
Vào những năm 80, thị trường các sản phẩm dân dụng đó cú khỏ nhiều sản phẩm ở trỡnh đô cao như: máy giặt, máy ảnh, sử dụng Trí tuệ nhân tạo. Các hệ thống nhận dạng và xử lý ảnh, tiếng núi. Những năm 90, các nghiên cứu nhằm vào cài đặt thành phần thông minh trong các hệ thống thông tin, gọi chung là cài đặt trí tuệ nhân tạo, làm rừ hơn các ngành của khoa học Trí tuệ nhân tạo và tiến hành các nghiên cứu mới, đặc biệt là nghiên cứu về cơ chế suy lý, về Trớ tuệ nhõn tạo phõn tạo, về cỏc mụ hỡnh tương tác. Những đặc trưng của Trí tuệ nhân tạo Trí tuệ nhân tạo xử lý thông tin theo trật tự ký hiệu. Các thông tin gồm: khái niệm, luật, các đối tượng ? dùng cho suy lý. Khỏi niệm cơ bản trong Trí tuệ nhân tạo là sự thể hiện, suy lý, nhận biết, việc học và hệ thống cơ sở tri thức. Phương pháp may rủi hay được dùng trong Trí tuệ nhân tạo. Phương pháp này cho phép giải hai lớp bài toán khó. Thứ nhất là những bài toán chưa có thuật giải ( bài toán nhận biết, ra quyết định). Thứ hai là các bài toán đó cú thuật giải nhưng độ phức tạp lớn ( chẳng hạn bài toán chơi cờ). Trí tuệ nhân tạo xét đến những thông tin không đầy đủ, không chính xác, có vẻ mâu thuẫn. Tuy vậy, các kết quả của Trí tuệ nhân tạo là cụ thể. Việc tương tác người- máy đi đôi với nhận biết tự động là cần thiết trong Trí tuệ nhân tạo. Các bài toán nhận dạng là ví dụ về yêu cầu này. Trí tuệ nhân tạo liên quan đến nhiều lĩnh vực, như các kỹ thuật mới, logic học, khoa học nhận biết, ngôn ngữ học, khoa học về tổ chức, thần kinh học. Trớ tuệ nhõn tạo cũn nằm trong cỏc lĩnh vực nghiờn cứu nõng cao, cỏc đề án nghiên cứu quan trọng. 8
3. Một số vấn đề Trí tuệ Nhân tạo quan tâm. Những vấn đề chung Khoa học Trí tuệ nhân tạo liên quan đến cảm giác, tri giác và cả quá trỡnh tư duy thông qua các hành vi, giao tiếp. Nó có các định hướng nghiên cứu, ứng dụng sau: 1- Tỡm và nghiờn cứu cỏc thủ tục giỳp con người tiến hành các hoạt động sáng tạo. Công việc sáng tạo được thực hiện trên mô hỡnh theo cấu trỳc, chức năng và sử dụng công nghệ thông tin. 2- Dùng ngôn ngữ tự nhiên. Trước hết là ngôn ngữ được dùng để thể hiện tri thức, tiếp thu và chuyển hoá sang dạng có thể xử lý được. 3- Hỡnh thức hoỏ cỏc khớa cạnh, cỏc hành vi liờn quan đến Trí tuệ nhân tạo. Do vậy có thể xây dựng các bài toán mang tính người và thông minh. Các hoạt động lớn trong Trí tuệ nhân tạo bao gồm: chứng minh định lý, xử lý ngôn ngữ tự nhiờn, hiểu tiếng núi, phõn tớch ảnh và hỡnh, người máy và hệ chuyên gia. Về cài đặt hệ thống, khuynh hướng hiện tại của Trí tuệ nhân tạo là cài đặt các hệ Trí tuệ nhân tạo trong các hệ thống khác, đặc biệt là trong các hệ thống tin học. Những vấn đề chưa được giải quyết trong Trí tuệ nhân tạo Những thành tựu nghiên cứu và ứng dụng các kỹ thuật Trí tuệ nhân tạo đó khẳng định tính thực tiễn của các dự án xây dựng máy tính có khả năng suy nghĩ. Tuy vậy trong một số phạm vi, mỏy tớnh cũn thua xa so với hoạt động của hệ thần kinh con người: Sự khác nhau trong hoạt động giữa máy tính và bộ nóo con người, điều này thể hiện ưu thế của máy tính so với bộ nóo người vỡ khả năng tính toán rất lớn (nhất là trong các chương trỡnh xử lý dữ liệu lớn). Xử lý song song: mặc dù công nghệ điện tử hiện đại cho phép xây dựng các bộ đa xử lý, song máy tính không thể hoạt động song song như bộ nóo con người được. 9
Khả năng diễn giải: con người có thể xem xét cùng một vấn đề theo những phương pháp khác nhau, từ đó diễn giải theo cách dễ hiểu nhất. Ngược lại, sự linh hoạt này không thể mô phỏng được trong các hệ thống Trí tuệ nhân tạo. Lụgic rời rạc và tớnh liờn tục: một thách đố lớn với các hệ thống Trí tuệ nhân tạo là khả năng kết hợp các phương pháp xử lý thụng tin trong mụi trường liên tục với các thao tác xử lý thụng tin rời rạc. Khả năng học: mặc dù hiện nay máy tính có nhiều tính năng cao nhưng cũng không thể mô phỏng được hoàn toàn khả năng học giống bộ nóo con người. Khả năng tự tổ chức: cho tới nay, người ta chưa thể tạo lập được các hệ thống Trí tuệ nhân tạo có khả năng tự tổ chức, tự điều khiển hoạt động của nó để thích nghi với môi trường. Những vấn đề đặt ra trong tương lai của Trí tuệ nhân tạo. Trong tương lai, những nghiên cứu và ứng dụng của Trí tuệ nhân tạo tập trung vào các vấn đề lớn sau: Nghiên cứu và thử nghiệm các mạng Neuron, các hệ thống Trí tuệ nhân tạo mô phỏng chức năng hoạt động của bộ nóo với các khả năng học, tự tổ chức, tự thích nghi, tổng quát hoá, xử lý song song, có khả năng diễn giải, xử lý thông tin liờn tục và rời rạc. Nghiên cứu và tạo lập các hệ thống có giao tiếp thân thiện giữa người và máy trên cơ sở nghiên cứu nhận thức máy, thu thập và xử lý tri thức, xử lý thụng tin hỡnh ảnh, tiếng núi. Nghiên cứu các phương pháp biểu diễn tri thức và các phương pháp suy diễn thông minh, các phương pháp giải quyết vấn đề đối với những bài toán phụ thuộc không gian, thời gian. Ngày nay, thế giới đang chuyển mỡnh trong những nghiờn cứu về Trớ tuệ nhõn tạo. Chắc chắn rằng mỏy tớnh với trớ tuệ như con người sẽ tác động mạnh đến cuộc sống xó hội. 10
4. Các khái niệm cơ bản: Trí tuệ con người (Human Intelligence): Cho đến nay có hai khái niệm về trí tuệ con người được chấp nhận và sử dụng nhiều nhất, đó là: Khái niệm trí tuệ theo quan điểm của Turing “Trớ tuệ là những gỡ cú thể đánh giá được thông qua các trắc nghiệm thông minh” Khái niệm trí tuệ đưa ra trong tụ điển bách khoa toàn thư: “Trí tuệ là khả năng: Phản ứng một cỏch thớch hợp những tỡnh huống mới thụng qua hiệu chỉnh hành vi một cỏch thớch đáng. Hiểu rừ những mối liờn hệ qua lại của cỏc sự kiện của thế giới bờn ngoài nhằm đưa ra những hành động phù hợp đạt tới một mục đích nào đó. Những nghiờn cứu cỏc chuyờn gia tõm lý học nhận thức chỉ ra rằng quỏ trỡnh hoạt động trí tuệ của con người bao gồm 4 thao tác cơ bản: 1- Xác định tập đích (goals). 2- Thu thập các sự kiện (facts) và các luật suy diễn (inference rules) để đạt được đích đặt ra. 3- Thu gọn (pruning) quỏ trỡnh suy luận nhằm xỏc định tập các suy diễn có thể sử dụng được. 4- Áp dụng các cơ chế suy diễn cụ thể (inference mechanisms) để đưa các sự kiện ban đầu đi đến đích. Trớ tuệ mỏy: cũng không có một định nghĩa tổng quat, nhưng cũng có thể nêu các đặc trưng chính: 1- Khả năng học. 2- Khả năng mô phỏng hành vi của con người. 3- Khả năng trừu tượng hoá, tổng quát hoá và suy diễn . 4- Khả năng tự giải thích hành vi. 5- Khả năng thích nghi tỡnh huống mới kể cả thu nạp tri thức và dữ liệu. 11
6- Khả năng xử lý các biểu diễn hỡnh thức như các ký hiệu tượng trưng. 7- Khả năng sử dụng tri thức heuristic. 8- Khả năng xử lý các thông tin không đầy đủ, không chính xác 5. Một số chuyờn ngành của Trớ tuệ nhõn tạo: 1. Các phương pháp tỡm kiếm lời giải. 2. Hệ chuyờn gia 3. Mỏy nhỡn và ngụn ngữ. 4. Lý thuyết nhận dạng. 5. Cỏc mụ hỡnh thần kinh. 6. Người máy. . . . Chương 1 BIỂU DIỄN BÀI TOÁN TRONG KHễNG GIAN TRẠNG THÁI 1. Đặt vấn đề. Khi giải quyết bài toán bằng phương pháp tỡm kiếm, trước hết ta phải xác định khụng gian tỡm kiếm bao gồm tất cả các đối tượng trên đó thực hiện việc tỡm kiếm. Một phương pháp biểu diễn vấn đề phù hợp là sử dụng các khái niệm trạng thỏi (state) và toỏn tử (operator). Phương pháp giải quyết vấn đề dựa trên khái niệm trạng thái và toán tử được gọi là cách tiếp cận giải quyết vấn đề nhờ không gian trạng thái. 2. Mụ tả trạng thỏi Giải bài toán trong không gian trạng thái, trước hết phải xác định dạng mô tả trạng thái bài toán sao cho bài toán trở nên đơn giản hơn, phù hợp bản chất vật lý của bài toỏn (Cú thể sử dụng cỏc xõu ký hiệu, vộctơ, mảng hai chiều, cây, danh sách). 12
Mỗi trạng thỏi chớnh là mỗi hỡnh trạng của bài toỏn, cỏc tỡnh trạng ban đầu và tỡnh trạng cuối của bài toỏn gọi là trạng thỏi đầu và trạng thái cuối. Vớ dụ 1. Bài toán đong nước Cho 2 bỡnh cú dung tớch lần lượt là m và n (lit). Với nguồn nước không hạn chế, dùng 2 bỡnh trờn để đong k lit nước. Không mất tính tổng quát có thể giả thiết k <= min(m,n). Tại mỗi thời điểm xác định, lượng nước hiện có trong mỗi bỡnh phản ỏnh bản chất hỡnh trạng của bài toỏn ở thời điểm đó. - Gọi x là lượng nước hiện có trong bỡnh dung tớch m và y là lượng nước hiện có trong bỡnh dung tớch n. Như vậy bộ có thứ tự (x,y) có thể xem là trạng thái của bài toán. Với cách mô tả như vậy, các trạng thái đặc biệt của bài toán sẽ là: - Trạng thái đầu: (0,0) - Trạng thỏi cuối: (x,k) hoặc (k,y), 0 x m , 0 y n Vớ dụ 2. Bài toỏn trũ chơi 8 số Trong bảng ô vuông 3 hàng, 3 cột , mỗi ô chứa một số nằm trong phạm vi từ 1 đến 8 sao cho không có 2 ô có cùng giá trị, có một ô trong bảng bị trống (không chứa giá trị nào cả. Xuất phát từ một sắp xếp nào đó các số trong bảng, hóy dịch chuyển ụ trống sang phải, sang trỏi, lờn trờn hoặc xuống dưới (nếu có thể được) để đưa về bảng ban đầu về bảng qui ước trước. Chẳng hạn Hỡnh 1. dưới đây là bảng xuất phát và Hỡnh 2. là bảng mà ta phải thực hiện cỏc bước di chuyển ô trống để đạt được. 2 8 3 1 6 4 7 5 Hỡnh 1. 1 2 3 8 4 13
7 6 5 Hỡnh 2. Giá trị các phần tử trong bảng xác định trạng thái bài toán. Vỡ vậy cú thể mụ tả trạng thỏi của bài toỏn bằng một ma trận A3*3= (aij) , aij {0 8}, aij akl, i l - Trạng thái đầu của bài toán là ma trận 2 8 3 1 6 4 7 0 5 - Trạng thỏi cuối là ma trận 1 2 3 8 0 4 7 6 5 Cú thể phỏt biểu dạng tổng quỏt của bài toỏn này (Trũ chơi n2-1 số) Vớ dụ 3. Bài toỏn thỏp Hà Nội Cho ba cọc 1, 2, 3. Ở cọc 1 ban đầu có n đĩa sắp xếp theo thứ tự to dần từ dưới lên trên. Hóy dịch chuyển n đĩa đó sang cọc thứ 3 sao cho: - Mỗi lần chỉ chuyển một đĩa. - Trong mỗi cọc không cho phép đĩa to nằm trên đĩa nhỏ hơn. Bài toán xác định khi biết được từng đĩa đang nằm ở cọc nào. Hay nói cách khác, có hai cách xác định: 1- Cọc 1 hiện đang chứa những đĩa nào? Cọc 2 hiện đang chứa những đĩa nào? Và cọc 3 đang chứa những đĩa nào. 2- Đĩa lớn thứ i hiện đang nàm ở cọc nào? ( i = 1 n ) Như vậy cách mô tả trạng thái bài toán không duy nhất, vấn đề là chọn cách mô tả nào để đạt được mục đích dễ dàng nhất. 14
Theo trên, với cách thứ nhất ta phải dùng 3 danh sách động vỡ số đĩa trên mỗi cọc là khác nhau trong từng thời điểm khác nhau. Cỏch thứ hai, nhỡn qua thỡ khú mụ tả nhưng dựa vào khái niệm về bộ có thứ tự trong toán học, cách này mô tả bài toán hiệu quả hơn. Thật vậy, nếu gọi xi là cọc chứa đĩa lớn thứ i, trong đó xi {1, 2, 3}, i {1 n}. Khi đó bộ có thứ tự (x1, x2, . . ,xn) có thể dùng làm dạng mô tả trạng thái đang xét của bài toán. Với cỏch mụ tả này, Trạng thái đầu là (1,1,. . .,1) Trạng thỏi cuối là (3,3,. . .,3) 3. Toỏn tử chuyển trạng thỏi. Toán tử chuyển trạng thái thực chất là các phép biến đổi đưa từ trạng thái này sang trạng thái khác. Có hai cách dùng để biểu diễn các toán tử: - Biểu diễn như một hàm xác định trên tập các trạng thỏi và nhận giỏ trị cũng trong tập này. - Biểu diễn dưới dạng các quy tắc sản xuất S? A cú nghĩa là nếu cú trạng thỏi S thỡ cú thể đưa đến trạng thái A. 15
Vớ dụ 1. Bài toán đong nước Các thao tác sử dụng để chuyển trạng thái này sang trạng thái khác gồm: Đổ đầy một bỡnh, đổ hết nước trong một bỡnh ra ngoài, đổ nước từ bỡnh này sang bỡnh khỏc. Như vậy, nếu trạng thái đang xét là (x,y) thỡ cỏc trạng thỏi kế tiếp cú thể chuyển đến sẽ là: (m,y) (x,n) (0,y) (x,0) (x,y) (0, x+ y) nếu x+y n (x+ y,0) nếu x+y m Vớ dụ 2. Trũ chơi 8 số Các thao tác để chuyển trạng thái tương ứng với việc chuyển ô trống sang phải, sang trái, lên, xuống nếu có thể được. - Biểu diễn theo quy tắc sản xuất: 1 3 2 5 4 1 3 4 8 7 6 1 3 4 2 5 2 5 8 7 6 8 7 6 1 3 4 2 5 6 8 7 - Biểu diễn theo một hàm Gọi hàm fu là hàm biểu diễn cho toỏn tử chuyển ụ trống lờn trờn; gọi B (B= (bij)) là trạng thỏi sau khi di chuyển ụ trống ở trạng thỏi A (A= (aij)) lờn trờn, 16
nghĩa là: B= fu(A), giả sử ô trống đang ở vị trí (i0, j0) (hay núi cỏch khỏc ai0 j0 = 0) thỡ hàm f được xác định như sau: aij  (i, j) nếu i0 = 1 fu(aij) = aij nếu (i, j) (i0-1, j0) và (i, j) (i0, j0) và i0 >1 ai0-1, j0 nếu (i, j) = (i0, j0), i0 >1 ai0, j0 nếu (i, j) = (i0-1, j0), i0 >1 Tương tự, có thể xác định các phép chuyển ô trống xuống dưới fd, qua trỏi fl, qua phải fr như sau: aij  (i, j) nếu i0 = 3 fd(aij) = aij nếu (i, j) (i0+1, j0) và (i, j) (i0, j0) và i0 1 ai0-1, j0 nếu (i, j) = (i0, j0), j0 > 1 ai0, j0 nếu (i, j) = (i0, j0-1), j0 > 1 aij  (i, j) nếu j0 = 3 fr(aij) = aij nếu (i, j) (i0, j0+1) và (i, j) (i0, j0) và j0 < 3 ai0-1, j0 nếu (i, j) = (i0, j0), j0 < 3 ai0, j0 nếu (i, j) = (i0, j0+1), j0 < 3 Vớ dụ 3. Bài toỏn Thỏp Hà Nội với n=3. Mỗi trạng thỏi là một bộ ba (i, j, k). Có các trường hợp như sau: - Ba đĩa cùng nằm trên một cọc: (i, i, i) - Hai đĩa cùng nằm trên một cọc: (i, i, j), (i, j, i), (j, i, i) 17
- Ba đĩa nằm trên ba cọc phân biệt: (i, j, k) 18
(i, i, i) (i, i, j) (i, i, k) (i, i, j) (i, i, k) (i, k, j) (i, i, i) (i, j, i) (i, j, k) (i, j, j) (i, k, i) (j, i, i) (j, i, j) (j, i, k) (k, i, i) (i, j, k) (i, i, k) (i, j, j) (i, j, i) 4. Khụng gian trạng thỏi của bài toỏn. Kkhụng gian trạng thỏi là tập tất cả cỏc trạng thỏi cú thể cú và tập cỏc toỏn tử của bài toỏn. Khụng gian trạng thỏi là một bộ bốn, Ký hiệu: K= (T, S, G, F). Trong đó, T: tập tất cả cỏc trạng thỏi cú thể cú của bài toỏn S: trạng thái đầu G: tập các trạng thái đích F: tập cỏc toỏn tử Vớ dụ 1. Không gian trạng thái của bài toán đong nước là bộ bốn T, S, G, F xác đinh như sau: T = { (x,y) / 0 <= x <= m; 0 <= y <= n } S = (0,0) G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <= y <= n} 19
F = Tập các thao tác đong đầy, đổ ra hoặc đổ sang bỡnh khỏc thực hiện trờn một bỡnh. Vớ dụ 2. Khụng gian trạng thỏi của bài toỏn Thỏp Hà nội với n = 3: T = { (x1, x2, x3)/ xi {1, 2, 3} } S = (1, 1, 1) G = {(3, 3, 3)} F = Tập các khả năng có thể chuyển đĩa đó xỏc định trong phần trước. Vớ dụ 3. Khụng gian trạng thỏi của bài toỏn trũ chơi 8 số: T = { (aij)3x3 / 0 akl với i l} S = Ma trận xuất phỏt của bài toỏn, G = Ma trận cuối cựng của bài toỏn (cỏc số nằm theo vị trớ yờu cầu) F = {fl, fr, fu, fd} Tỡm kiếm lời giải trong khụng gian trạng thỏi là quỏ trỡnh tỡm kiếm xuất phát từ trạng thái ban đầu, dựa vào toán tử chuyển trạng thái để xác định các trạng thái tiếp theo cho đến khi gặp được trạng thái đích. 5. Biểu diễn không gian trạng thái dưới dạng đồ thị 5.1. Cỏc khỏi niệm Đồ thị G = (V,E) trong đó V:tập đỉnh, E: tập cung (EV*V) Chỳ ý - G là đồ thị vô hướng thỡ (i, j) là một cạnh cũng như là (j, i) (tức là:(i, j) E thỡ (j,i) E) - Nếu G là đồ thị có hướng thỡ cung (i, j) hoàn toàn khỏc với cung (j, i). Vớ dụ xét dồ thị vô hướng G1 và đồ thị có hướng G2 1 1 2 4 2 4 3 3 20
G1 G2 Tập đỉnh kề: n V, T(n)={m V/ (n,m) E}được gọi là tập các đỉnh kề của n Đường đi: p = (n1, ,nk) được gọi là đường đi từ đỉnh n1 nk nếu ni V, i=1,k ; (ni, ni+1) E i=1, k -1 Cây là đồ thị có đỉnh gốc n0 V thoả: Một đồ thị G=(V, E) gọi là cây nếu tồn tại một đỉnh n0 V cú những tớnh chất sau:   - n V, n T(n0), trong đó T(n0): tập các đỉnh thuộc dũng dừi của n0 (n0 là tổ tiờn của n) - n V, m V sao cho n T(m); m được gọi là cha của n. 5.2. Biểu diễn không gian trạng thái bằng đồ thị Theo ngôn ngữ đồ thị, không gian trạng thái tương ứng với một đồ thị định hướng trong đó: Các trạng thái tương ứng với các đỉnh trong đồ thị, nếu tồn tại toán tử chuyển trạng thái thỡ cú cung (s, t) Để thấy rừ mối tương quan, ta có bảng sau KGTT Đồ thị Trạng thỏi Đỉnh Toỏn tử Cung Dóy cỏc trạng thỏi liờn Đường đi tiếp 5.3. Biểu diễn đồ thị 21
Cho đồ thị G = (V,E) , giả sử V={1, 2, ,n}. Có hai cách thường dùng để biểu diễn đồ thị G lưu trữ trong máy tính. i) Biểu diễn bằng ma trận kề Đồ thị G được biểu diễn bởi ma trận kề A=(aij)nxn, với n là số đỉnh của đồ thị, trong đó: aij= 1 nếu (i, j) E 0 trong trường hợp ngược lại Nếu G là đồ thị vô hướng thỡ ma trận kề A là ma trận đối xứng. Vớ dụ Với đồ thị vô hướng G1 và đồ thị có hướng G2 ở trờn ta cú cỏc ma trận kề sau: 0 1 1 1 0 1 0 1 G : G : 1 1 0 1 1 2 1 0 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 ii) Biểu diễn bằng danh sỏch kề. Với mỗi đỉnh i của đồ thị, ta có một danh sách tất cả các đỉnh kề với i, ta ký hiệu là List(i). Để thể hiện List(i) ta có thể dùng mảng, kiểu tập hợp hay kiểu con trỏ. Ví dụ với đồ thị G1, ta có List(1)= [2, 3, 4] Vớ dụ 1. Bài toán đong nước m=3, n=2, k=1 (0,0) (3,0) (0,2) (1,2) (3,2) (2,0) (1,0) (0,1) (2,2) (3,1) Vớ dụ 2. Thỏp Hà Nội với n = 3 22
(111) (112) (113) (132) (123) (133) (131) (121) (122) (233) (322) (231) (232) (323) (321) (221) (212) (313) (331) (222) (223) (213) (211) (311) (312) (332) (333) 23
6. BÀI TẬP Xây dựng không gian trạng thái đối với các bài toán sau: 6.1. Cho n thành phố đánh số từ 1 đến n. Giao thông đường bộ giữa hai thành phố i và j được cho bởi giá trị aij như sau: aij = -1 có nghĩa là không có đường bộ đi từ thành phố i sang thành phố j và aij = 1 nếu có đường đi trực tiếp từ thành phố i sang thành phố j. Tỡm đường đi từ thành phố i0 sang thành phố j0. 6.2. Cho k và n là 2 số nguyên dương. Có 2k viên sỏi, được phân bố trong n đống, đống thứ nhất có a1 viên, đống thứ 2 có a2 viên, , đống thứ n có an viờn k và tất nhiờn a1+ a2 + + an = 2 . Người ta cần san sẻ lượng sỏi từ các đống để dồn sỏi trở về 1 đống. Quy tắc san sỏi như sau: mỗi lần san áp dụng cho 2 đống sỏi, giả sử 1 đống có a viên và đống kia có b viên (không giảm tổng quát, có thể giả thiết a b) thỡ san sỏi từ đống có a viên sang đống có b viên để thành một đống có a-b viên và đống kia 2*b viên. Hướng dẫn: Trạng thái của bài toán phải xác định được số sỏi hiện có trong mỗi đống. 6.3. Một dóy cỏc số nguyờn dương a1, a2, , an được gọi là hợp lý nếu thoả món hai điều kiện: - an là số nguyờn tố. - ai+1 = ai +1 hoặc 2*ai Cho trước số a1, hóy tỡm dóy hợp lý a1, a2, , an. 6.4 Bài toán người đưa hàng. Người đưa hàng cần phải xác định được hành trỡnh ngắn nhất sao cho mỗi thành phố đi đến đúng một lần và quay trở lại thành phố xuất phát. Giả sử thành phố xuất phát là thành phố 1, có tất cả n thành phố đánh số từ 1 đến n. 24
Hướng dẫn: - Mỗi trạng thái cho bởi danh sách các thành phố đó đi qua cho đến thời điểm hiện tại, trong đó không cho phép một thành phố nào được xuất hiện nhiều hơn một lần trừ thành phố 1 sau khi đó liệt kờ tất cả cỏc thành phố cũn lại. - Các toán tử tương ứng với các hành động 1- đi tới thành phố 1 2- đi tới thành phố 2 3- đi tới thành phố 3. . . . 6.5. Bài toỏn phõn tớch cỳ phỏp. Văn phạm G là bộ bốn G = (N, T, P, S), N là tập ký hiệu khụng kết thỳc, T là tập ký hiệu kết thỳc, S N là ký hiệu đầu và P là tập sản xuất cú dạng , ở đây ,  (NUT). Ngôn ngữ sinh ra bởi văn phạm G được định nghĩa bởi:\ L(G) = {  T | S  }, S  cú nghĩa là  1, , n (NUT) sao cho i i+1, 1 = S và n = . Bài toán phân tích cú pháp được phát biểu : ch trước văn phạm G với xõu  T đó cho hóy xỏc định xem  L(G) hay khụng ? Chương 2 CÁC PHƯƠNG PHÁP TèM KIẾM LỜI GIẢI TRONG KHễNG GIAN TRẠNG THÁI Quỏ trỡnh tỡm kiếm lời giải của bài toỏn được biểu diễn trong không gian trạng thái được xem như quá trỡnh dũ tỡm trờn đồ thị, xuất phát từ trạng thái ban đầu, thông qua các toán tử chuyển trạng thái, lần lượt đến các trạng thái tiếp theo cho đến khi gặp được trạng thái đích hoặc không cũn trạng thỏi nào cú thể tiếp tục được nữa. Khi áp dụng các phương pháp tỡm kiếm trong khụng gian trạng thỏi , người ta thường quan tâm đến các vấn đề sau: 25
Kỹ thuật tỡm kiếm lời giải Phương pháp luận của việc tỡm kiếm Cỏch thể hiờn cỏc nỳt trong quỏ trỡnh tỡm kiếm (mụ tả trạng thỏi bài toỏn) Việc chọn các toán tử chuyển trạng thái nào để áp dung và có khả năng sử dụng .phương pháp may rủi trong quá trỡnh tỡm kiếm. Tuy nhiên, không phải các phương pháp này có thể áp dụng cho tất cả các bài toán phức tạp mà cho từng lớp bài toán. Việc chọn chiến lược tỡm kiếm cho bài toỏn cụ thể phụ thuộc nhiều vào cỏc đặc trưng của bài toán. Cỏc thủ tục tỡm kiếm điển hỡnh bao gồm: - Tỡm kiếm theo chiều rộng (Breadth – First Search) - Tỡm kiếm theo chiều sõu (Depth – First Search) - Tỡm kiếm sõu dần (Depthwise Search) - Tỡm kiếm cực tiểu hoỏ giỏ thành (Cost minimization Search). - Tỡm kiếm với tri thức bổ sung (Heuristic Search). 1. Phương pháp tỡm kiếm theo chiều rộng. 1.1. Kỹ thuật tỡm kiếm rộng. Kỹ thuật tỡm kiếm rụng là tỡm kiếm trờn tất cả cỏc nỳt của một mức trong khụng gian bài toỏn trước khi chuyển sang các nút của mức tiếp theo. Kỹ thuật tỡm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục đến khi định vị được lời giải nếu có. 1.2. Giải thuật. Input: Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu) Tập đích Goals 26
Output: Một đường đi p từ n0 đến một đỉnh n* Goals Method: Sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue) MO và DONG Procedure BrFS; (Breadth First Search) Begin Append(MO,no) DONG=null; While MO <> null do begin n:= Take(MO); if n DICH then exit; Append(DONG, n); For m T(n) and m DONG+MO do Append(MO, m); end; Write (‘Khụng cú lời giải’); End; Chỳ ý: Thủ tục Append(MO,n0) bổ sung một phần tử vào queue MO. Hàm Take(MO) lấy một phần tử trong queue MO. Nếu G là cõy thỡ khụng cần dựng danh sỏch DONG. 1.3. Đánh giá độ phức tạp của giải thuật tỡm kiếm rộng. Giả sử rằng, mỗi trạng thái khi được xét sẽ sinh ra k trạng thái kế tiếp. Khi đó ta gọi k là nhân tố nhánh. Nếu bài toỏn tỡm được nghiệm theo phương pháp 27
tỡm kiếm rộng cú độ dài d. Như vậy, đỉnh đích sẽ nằm ở mức d+1, do đó số đỉnh cần xét lớn nhất là: 1 + k + k2 + . . . + kd. Như vậy độ phức tạp thời gian của giải thuật là O(kd). Độ phức tạp không gian cũng là O(kd), vỡ tất cả cỏc đỉnh của cây tỡm kiếm ở mức d+1 đêu phải lưu vào danh sách. 1.4. Ưu và nhược điểm của phương pháp tỡm kiếm rộng. 1.4.1. Ưu điểm. Kỹ thuật tỡm kiếm rộng là kỹ thuật vột cạn khụng gian trạng thỏi bài toỏn vỡ vậy sẽ tỡm được lời giải nếu có. Đường đi tỡm được đi qua ít đỉnh nhất. 1.4.2. Nhược điểm. Tỡm kiếm lời giải theo thuật toỏn đó định trước, do vậy tỡm kiếm một cỏch mỏy múc; khi khụng cú thụng tin hổ trợ cho quỏ trỡnh tỡm kiếm, khụng nhận ra ngay lời giải. Khụng phự hợp với khụng gian bài oỏn kớch thước lớn. Đối với loại bài toán này, phương pháp tỡm rộng đối mặt với các nhu cầu: - Cần nhiều bộ nhớ theo số nút cần lưu trữ. - Cần nhiều cụng sức xử lý cỏc nỳt, nhất là khi cỏc nhỏnh cõy dài, số nỳt tăng. - Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý. Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu. Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, việc tỡm kiếm khụng tập trung vào một chủ đề. 1.5. Cỏc vớ dụ. 28
Vớ dụ 1. Bài toán đong nước với m = 5, n= 4, k =3 Mức 1: Trạng thái đầu (0;0) Mức 2: Cỏc trạng thỏi (5;0), (0;4), Mức 3: (5;4), (1;4), (4,0) Mức 4: (1;0), (4;4) Mức 5: (0;1), (5;3) Ở mức 5 ta gặp trạng thái đích là (5;3) vỡ vậy cú được lời giải như sau: (0;0) (0;4) (4;0) (4;4) (5;3) Để có được lời giải này ta phải lưu lại vết của đường đi, có thể trỡnh bày quỏ trỡnh tỡm kiếm dưới dạng bảng sau: i T(i) MO  DONG (0;0) (0;0) (5;0) (0;4) (5;0) (0;4) (0;0) (5;0) (5;4) (0;0) (1;4) (0;4) (5;4) (0;0) (5;0) (1;4) (0;4) (5;4) (0;0) (4;0) (5;4) (1;4) (0;0) (5;0) (0;4) (4;0) (5;4) (0;4) (5;0) (1;4) (4;0) (0;0) (5;0) (0;4) (5;4) (1;4) (5;4) (0;4) (1;0) (4;0) (1;0) (0;0) (5;0) (0;4) (5;4) (1;4) (5;0) (4;0) (5;0) (4;4) (0;0) (1;0) (4;4) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (0;4) (1;0) (5;0) (1;4) (0;1) (4;4) (0;1) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (4;4) (5;4) (0;4) (4;0) (0;1) (5;3) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (5;3) (1;0) (4;4) (0;1) (5;1) (0;4) (0;0) (5;3) (5;1) (0;0) (5;0) (0;4) (5;4) (1;4) (4;0) (1;0) (1;0) (0;1) (5;3) 29
Vớ dụ 2. Bài toỏn trũ chơi 8 số Bảng xuất phỏt 2 8 3 1 6 4 7 5 Bảng kết thỳc 1 2 3 8 4 7 6 5 Mức 1: Cú một trạng thỏi 2 8 3 1 6 4 7 5 Mức 2: Cú ba trạng thỏi 2 8 3 2 8 3 2 8 3 1 4 1 6 4 1 6 4 7 6 5 7 5 7 5 Mức 3: Có năm trạng thái 2 8 3 2 8 3 2 3 1 4 1 4 1 8 4 7 6 5 7 6 5 7 6 5 2 8 3 2 8 3 6 4 1 6 30
1 7 5 7 5 4 Mức 4: Có mười trạng thái 8 3 2 8 3 2 1 4 7 1 4 7 6 5 6 5 2 8 2 8 3 1 4 3 1 4 5 1 7 5 7 6 2 3 2 3 1 8 4 1 8 4 7 6 5 7 6 5 8 3 2 8 3 2 6 4 6 4 1 7 5 1 7 5 2 8 2 8 3 1 6 3 1 6 4 7 5 4 7 5 Mức 6: Cú 12 trạng thỏi 1 2 3 2 3 4 8 4 1 8 7 6 5 7 6 5 31
8 3 2 8 3 2 1 4 7 1 4 7 6 5 6 5 2 8 2 8 3 1 4 3 1 4 5 7 6 5 7 6 8 3 2 3 2 6 4 6 8 4 1 7 5 1 7 5 2 8 3 2 8 6 7 4 1 6 3 1 5 7 5 4 2 3 2 8 3 1 8 3 1 5 6 7 5 4 7 4 Mức 6: Cú 24 trạng thỏi 1 2 3 1 2 3 8 4 7 8 4 7 6 5 6 5 . . . 33
Ở mức này ta gặp được trạng thái đích. 1 2 3 8 4 7 6 5 2. Phương pháp tỡm kiếm theo chiều sõu. 2.1. Kỹ thuật tỡm kiếm sõu. Tỡm kiếm sõu trong khụng gian bài toỏn được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngừ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tỡm. Nếu khụng đi tiếp đựoc, gọi là đến ngừ cụt, hệ thống quay lại một mức trờn đồ thị và tỡm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui. Thuật toỏn tỡm kiếm theo chiều sõu được hỡnh dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thỡ quay lại xột cành chưa đi qua. - Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp: + Nếu tồn tại đỉnh j kề i chưa được xét thỡ xột đỉnh này (nó trở thành đỉnh đó xột) và bắt đầu từ đó tiếp tục quá trỡnh tỡm kiếm với đỉnh này + Nếu với mọi đỉnh kề với i đều đó được xét thỡ i coi như duyệt xong và quay trở lại tỡm kiếm từ đỉnh mà từ đó ta đi đến được i. 2.2. Giải thuật. Input: Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu) Tập đích Goals 34
Output: Một đường đi p từ n0 đến một đỉnh n* Goals Method: Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack) MO và DONG Procedure DFS; (Depth First Search) Begin Push (MO,no) DONG=null; While MO <> null do begin n:=pop (MO); if n DICH then exit; push (DONG, n); For m T(n) and m DONG+MO do Push (MO, m); end; Write (‘Khụng cú lời giải’); End; Chỳ ý: Thủ tục Push(MO,n0) thực hiện việc bổ sung n0 vào stack MO Hàm Pop(MO) lấy phần tử đầu tiên trong Stack MO. 2.3. Đánh giá độ phức tạp của thuật toán tỡm kiếm sõu. Gải sử nghiệm của bài toán là đường đi có độ dài d, cây tỡm kiếm cú nhõn tố nhỏnh là k. Cú thể xóy ra nghiệm là đỉnh cuối cùng được xét ở mức d+1 theo luật trọng tài. Khi đó độ phức tạp thời gian của thuật toán tỡm kiếm theo chiều sõu trong trường hợp xấu nhất là O(kd). 35
Để đánh giá độ phức tạp không gian của thuật toán tỡm kiếm sâu ta có nhận xét ràng: Khi xét đỉnh j, ta chỉ cần lưu các đỉnh chưa được xét mà chúng là những đỉnh con của những đỉnh nằm trên đường đi từ đỉnh gốc đến j. Vỡ vậy chỉ cần lưu tối đa la k*d. Do đó độ phức tạp không gian của thuật toán là O(k*d). 2.4. Ưu và nhược điểm của phương pháp tỡm kiếm sõu. 2.4.1. Ưu điểm. Nếu bài toán có lời giải, phương pháp tỡm kiếm sõu bảo đảm tỡm ra lời giải. Kỹ thuật tỡm kiếm sõu tập trung vào đích, con người cảm thấy hài lũng khi cỏc cõu hỏi tập trung vào vấn đề chính. Do cỏch tỡm của kỹ thuật này, nếu lời giải ở rất sõu, kỹ thuật tỡm sõu sẽ tiết kiệm thời gian. 2.4.2. Nhược điểm. Tỡm sõu khai thỏc khụng gian bài toỏn để tỡm lời giải theo thuật toỏn đơn giản một cách cứng nhắc. Trong quá trỡnh tỡm nú khụng cú thụng tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán. Khụng phự hợp với khụng gian bài toỏn lớn, kỹ thuật tỡm kiếm sõu cú thể khụng đến lời giải trong khoảng thời gian vừa phải. 2.5. Cỏc vớ dụ. Vớ dụ 1. Bài toỏn đong nước với m = 5, n = 4, k = 3 Nếu ta chọn nhánh ưu tiên đổ đầy bỡnh thứ hai thỡ sẽ tỡm thấy lời giải rất nhanh. Quỏ trỡnh tỡm kiếm cú thể trỡnh bày bằng bảng dưới đây i T(i) MO  DONG (0;0) (0;0) (5;0) (0;4) (5;0) (0;4) (0;0) (0;4) (5;4) (0;0) (4;0) (5;0) (5;4) (0;0) (0;4) (4;0) 36
(4;0) (5;0) (4;4) (0;0) (5;0) (5;4) (0;0) (0;4) (4;0) (0;4) (4;4) (4;4) (5;4) (0;4) (4;0) (5;0) (5;4) (0;0) (0;4) (4;0) (4;4) (5;3) (5;3) (5;3) Lời giải tỡm được: (0;0) (0;4) (4;0) (4;4) (5;3) Vớ dụ 2. Bài toỏn Thỏp Hà nội với n = 3. Nhắc lại, dựng bộ ba (x1; x2; x3) biểu diễn trạng thỏi bài toỏn, với xi là cọc chứa đĩa lớn thứ i. i T(i) MO  DONG (1;1;1) (1;1;1) (1;1;2) (1;1;3) (1;1;2) (1;1;3) (1;1;1) (1;1;3) (1;1;1)(1;1;2) (1;1;2)(1;2;3) (1;1;1)(1;1;3) (1;2;3) (1;2;3) (1;1;3) (1;2;1) (1;1;2)(1;2;1)(1;2;2) (1;1;1)(1;1;3)(1;2;3) (1;2;2) (1;2;2) (1;2;3) (1;2;1) (1;1;2)(1;2;1)(3;2;2) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;2) (3;2;2) (1;2;2) (3;2;3) (1;1;2)(1;2;1)(3;2;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;2;1) (3;2;2) (3;2;1) (3;2;2) (3;2;3) (1;1;2)(1;2;1)(3;3;1) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;3;1) (3;2;2) (3;2;1) (3;3;1) (3;2;1) (3;3;2) (1;1;2)(1;2;1)(3;3;3) (1;1;1)(1;1;3)(1;2;3)(1;2;2) (3;3;3) (3;2;2) (3;2;1) (3;3;3) (3;3;3) 37
Lời giải của bài toỏn: (1;1;1) (1;1;3) (1;2;3) (1;2;2) (3;2;2) (3;2;1) (3;3;1) (3;3;3) Cả hai ví dụ trên, chúng ta đều thấy, tỡm kiếm theo chiều sõu đều cho lời giải tốt và nhanh. Vớ dụ 3. Bài toỏn tỡm dóy hợp lý với số hạng đầu a1 = 26 Nhắc lại: Dóy a1, a2, ,an được gọi là hợp lý nếu thoả hai điều kiện: - an là số nguyờn tố - ak+1 = ak+1 hoặc 2*ak Như vậy, khi biết ak thỡ ta xỏc định được ak+1. Vỡ vậy cú thể mụ tả trạng thỏi bài toỏn tương ứng với giá trj ak tại thũi điểm đang xét. Ta có thể chỉ ra một cỏch tỡm kiếm theo chiều sõu như sau I T(i) MO  DONG 26 26 27 52 27 52 26 52 53 104 27 53 104 26 52 104 105 208 27 53 105 208 26 52 104 208 209 416 27 53 105 209 416 26 52 104 208 . . . Với cỏch tỡm kiếm theo theo thuật toỏn một cỏch máy móc như vậy thỡ rừ ràng khụng bao giờ đạt được đích. Trong khi chúng ta dễ dàng nhận được lời giải, chăng hạn: a1 = 26; a2 = 52; a3 = 53. Như vậy n =3 3. Tỡm kiếm sõu dần 3.1. Kỹ thuật tỡm kiếm sõu dần. Kỹ thuật tỡm kiếm sõu dần là thực hiện việc tỡm kiếm với độ sâu ở mức giưói hạn d nào đó. Nếu không tỡm ra nghiệm ta tăng độ sâu lên d+1 và lại tỡm kiếm theo độ sâu tới mức d+1. Quá trỡnh trờn được lặp lại với d lần lượt là 1, 2, đến độ sâu max nào đó. 38
Kỹ thuật tỡm kiếm sõu dần thường được thực hiện khi cõy tỡm kiếm chứa nhỏnh vụ hạn, và nếu sử dụng tỡm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tỡm ra nghiệm. n0 D 39
3.2. Giải thuật. Thuật toỏn tỡm kiếm sõu dần sử dụng thuật toỏn tỡm kiếm sõu hạn chế như thủ tục con. Đó là thủ tục tỡm kiếm theo chiều sõu nhưng chỉ tới độ sâu d nào đó rồi quay lên. Thủ tục tỡm kiếm sõu hạn chế (depth_limitedsearch) Procedure Depth_limited_search(d); {d là tham số độ sâu} Begin Push (MO,no); Depth(n0)=0; {hàm depth ghi lại độ sâu mỗi đỉnh} DONG=null; While MO <> null do begin n:=pop (MO); if n DICH then exit; push (DONG, n); if depth(n)<=d then For m T(n) and m DONG do begin Push (MO, m); depth(m)=depth(n)+1; end; end; Write (‘Khụng cú lời giải’); End Thuật toỏn tỡm kiếm sõu dần (Depth_deepening_search) sẽ sử dụng thủ tục tỡm kiếm sõu hạn chế như thủ tục con: 40
Procedure Depth_deepening_search; Begin For d:=0 to max do Depth_limited_search(d); If thành cụng then exit; End; 3.3. Nhận xột. - Luụn tỡm ra nghiệm (nếu bài toỏn cú nghiệm), miễn là chọn max đủ lớn (giống như tỡm kiếm theo chiều rộng) - Có độ phức tạp thời gian là O(kd) (giống tỡm kiếm rộng) - Có độ phức tạp không gian là O(k*d) (giống tỡm kiếm sõu) - Giải thuật tỡm kiếm sõu dần thương áp dụng cho các bài toán có không gian trạng thái lớn và độ sâu của nghiệm không biết trước. 4. Phương pháp tỡm kiếm tốt nhất đầu tiên (Best First Search). Cả hai kỹ thuật tỡm kiếm rộng và tỡm kiếm sõu đều là phương pháp cơ bản để khai thác không gian bài toán. Chúng đều vét cạn không gian để tỡm ra lời giải theo thủ tục xỏc định trước. Mặc dù có sử dụng tri thức về trạng thái của bài toán để hướng dẫn tỡm kiếm nhưng không phổ biến. Cho dù có một số ưu điểm, nhưng chúng là những kỹ thuật thực hiện một cách máy móc. Chính vỡ vậy chỳng bị gỏn tờn là “kỹ thuật tỡm kiếm mự”. 4.1. Kỹ thuật tỡm kiếm tốt nhất đầu tiên. Kỹ thuật tỡm kiếm tốt nhất đầu tiên tỡm lời giải cú dựng tri thức về bài toỏn để hướng dẫn. Tri thức này hướng việc tỡm kiếm về nỳt lời giải trong khụng gian bài toỏn. Tại mỗi nút được xem xét, người ta sẽ quyết định việc tỡm kiếm tiếp tục theo nhỏnh nào tin tưởng sẽ dẫn đến lời giải. 41
Trong các chương trỡnh trớ tuệ nhõn tạo, kỹ thuật tỡm kiếm tốt nhất đầu tiên sử dụng hàm đánh giá. Hàm này dùng các thông tin hiện tại về mức độ quan trọng của bài toán tại nút đó để gán giá trị cho nút này, gọi là trọng số của nút. Giá trị này được xem xét trong lúc tỡm kiếm. Thụng thường, nút có trọng số nhỏ (lớn) nhất sẽ được chọn trong quá trỡnh tỡm kiếm. 4.2. Hàm đánh giá Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề đó để đánh giá các trạng thái của vấn đề. Với mỗi trạng thỏi u, ta sẽ xỏc dịnh một giỏ trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá. Phương pháp tỡm kiếm kinh nghiệm là phương pháp tỡm kiếm cú sử dụng đến hàm đánh giá. Trong quá trỡnh tỡm kiếm, tại mỗi bước ta sẽ chọn trạng thái kế tiếp là trạng thái có nhiều hứa hẹn dẫn tới đích nhiều nhất. Quỏ trỡnh tỡm kiếm trong khụng gian trạng thỏi cú sử dụng hàm đánh giá bao gồm các bước cơ bản sau: Biểu diễn thớch hợp cỏc trạng thỏi và cỏc toỏn tử chuyển trạng thỏi Xây dựng hàm đánh giá Thiết kế chiến lược chọn trạng thái ở mỗi bước 4.3. Ưu và nhược điểm của phương pháp tỡm kiếm tốt nhất đầu tiên. 4.3.1. Ưu điểm. - Phương pháp tỡm kiếm tốt nhất đầu tiên tổ hợp các ưu điểm của phương pháp tỡm kiếm rộng và tỡm kiếm sõu. - Ưu điểm chủ yếu của phương pháp tỡm kiếm tốt nhất đầu tiên là dùng tri thức để dẫn dắt việc tỡm kiếm. Tri thức này giỳp người ta bắt đầu từ đâu là tốt nhất và cách tốt nhất để tiến hành tỡm lời giải. - Tỡm kiếm tốt nhất đầu tiên tuân theo cách suy lý của một chuyờn gia. Do đó có thể thấy rừ đường đi hơn tỡm kiếm rộng và tỡm kiếm sõu. 4.3.2. Nhược điểm. 42
- Quỏ trỡnh tỡm kiếm cú thể đi xa khỏi lời giải. Kỹ thuật này chỉ xét một phần của không gian và coi đó là phần hứa hẹn hơn cả. 43
4.4. Giải thuật. Dữ liệu tương tự như giải thuật tỡm kiếm rụng và sõu, sử dụng danh sỏch MO để lưu các đỉnh sẽ xét. Procedure BFS; {Best First Search} Begin Push(MO,n0); while MO <> null do begin i := Pop(MO); if i Goals then exit; for j T(i) do Push(MO,j); Sort(MO); {theo thứ tự của hàm đánh giá} end; write(‘Khong co loi giai’); end; 4.5. Cỏc vớ dụ. Vớ dụ 1 Trong bài toỏn tỡm kiếm đường đi trên bản đồ giao thông, ta có thể lấy độ dài của đường chim bay từ một thành phố đang xét tới một thành phố đích làm giá trị của hàm đánh giá của thành phố đang xét. Vớ dụ 2 Bài toỏn 8 số. Chúng ta có thể đưa ra hai cách đánh giá 3 2 8 1 2 3 6 4 8 4 u = 7 1 5 đích = 7 6 5 - Hàm h1: Với mỗi trạng thỏi u thỡ h1(u) là số quân không nằm đúng vị trí của nó trong trạng thái đích. 44
Với vớ dụ trờn, ta cú h1(u)=4 - Hàm h2: Gọi h2(u) là là tổng khoảng cỏch giữa vị trớ của các quân trong trạng thái u và vị trí của nó trong trạng thái đích. Ở đây, khoảng cách được hiểu là số lần dịch chuyển ít nhất theo hàng hoặc cột để đưa một quân ở vị trí của hiện tại tới trạng thái đích. Với vớ dụ trờn, ta cú:h2(u)=2+3+1+3= 9 (vỡ quõn 3 cần ớt nhất 2 dịch chuyển, quõn 8 cần ớt nhất 3 dịch chuyển, quõn 6 cần ớt nhất 1 dịch chuyển và quõn 1 cần ớt nhất 3 dịch chuyển) 5. Tỡm kiếm đường đi có giá thành cực tiểu - Thuật toán AT Cho đồ thị G= (V, E) biểu diễn bài toán với đỉnh xuất phát n0 và tập đích DICH xác định. Với mỗi phộp chuyển trạng thỏi ni ni+1 tốn chi phớ c(ni, ni+1 ) ký hiệu c(u) với u= (ni, ni+1) E c(u) ni ni+1 Vấn đề: * Tỡm đường đi p: n0 n DICH sao cho c( p) c(u) min u p Chẳng hạn trong bài toỏn tỡm đường đi trong bản đồ giao thông, giá của cung (i,j) chính là độ dài của đường nối thành phố i với thành phố j. Độ dài đường đi được xác định là tổng độ dài các cung trên đường đi. Vấn đề đặt ra là tỡm đường đi ngắn nhất từ trạng thái ban đầu đến trạng thái đích. Phương phỏp giải 1) Nếu c(u) k(const) u E thỡ c( p) min # p min Dùng phương pháp tỡm kiếm theo chiều rộng. 2) Gọi g(n) là giá của đường đi cực tiểu từ đỉnh n0 đến n, khi đó bài toán có thể phát biểu như sau: Tỡm đường đi từ đỉnh n0 nk DICH sao cho: g(nk ) min g(n) / n DICH 45
Lúc đó, ta có: g(n0 ) 0 g(m) min g(n) c(n,m) (n,m) E Dùng 2 danh sách MO, DONG như trên. Tại mỗi thời điểm chọn đỉnh n trong MO ra xét là đỉnh thoả. Thuật toỏn AT Input: Đồ thị G = (V,E), Đỉnh xuất phỏt n0 Hàm chi phớ c: E R+ c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j) E Tập các đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến đỉnh n* DICH sao cho g(n*) = c(p) = min{g(n)| n DICH}. Procedure AT; { Dựng g0(n) là chi phớ cực tiểu của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét và xem như hàm g} Begin g(n0):= 0; push(MO, n0); While MO null then for m T(n) do 46
if m MO+DONG then begin push(MO,m); g(m):=g(n)+c(n,m); cha(m):=n; end else if g(m) >g(n)+c(n,m) then begin g(m):=g(n)+c(n,m); cha(m):=n; end; end; writeln(‘Khong co duong di’); End; Vớ dụ 1. Bài toán Tháp Hà Nội -với chi phí chuyển đĩa như sau: Chi phí chuyển đĩa nhỏ giữa 2 cọc gần 1 Chi phí chuyển đĩa nhỏ giữa 2 cọc xa 3 Chi phí chuyển đĩa vừa giữa 2 cọc gần 2 Chi phí chuyển đĩa vừa giữa 2 cọc xa 5 Chi phí chuyển đĩa lớn giữa 2 cọc gần 4 Chi phí chuyển đĩa lớn giữa 2 cọc xa 8 Xuất phát từ đỉnh (1,1,1), ta có g(1,1,1) = 0. Khi xét đỉnh (1,1,1) ta có các đỉnh kề và chi phí tương ứng : g(1,1,2) = 1; g(1,1,3) = 3; như vậy đỉnh (1,1,2) được chọn Các đỉnh kề của (1,1,2) có giá trị hàm g: g(1,1,3) = 2 (ở đây giá của đỉnh (1,1,3) được tính lại); g(1,3,2) = 5; chọn đỉnh (1,1,3), ta lại tính tiếp giá trị hàm g của các đỉnh kề với đỉnh này: 47
g(1,2,3) = 2; lại chọn đỉnh (1,2,3); chi phí của các đỉnh kề với nó: g(1,2,1) = 2 + 3 = 5; g(1,2,2) = 2 + 1 = 3; chọn đỉnh (1,2,2) g(1,2,1) = 3 +1 = 4 (được tính lại); g(3,2,2) = 3 + 8 = 11, chọn đỉnh (1,2,1) Cứ tiếp tục như vậy cho đến khi xét đỉnh (3,3,3). Vớ dụ 2 A 8 5 n0=A 4 DICH={F,K} B C D 2 9 3 1 1 E F G H I 2 K Cú thể trỡnh bày quỏ trỡnh tỡm kiếm bằng bảng dưới đây. Ký hiệu giỏ trị g(n) là chỉ số dưới tương ứng đỉnh n: ng(n) i T(i) MO DONG A0 A B C D B8 C4 D5 A C G B8 D5 G5 A C D H I B8 G5 H14 I6 A C D G B8 H14 I6 A C D G I K B8 H14 K8 A C D G B E F H14 K8 E10 F11 A C D G B K Lời giải của bài toỏn là A D I K và chi phí của đường đi tỡm được là 8 Vớ dụ 3. n0 = A; DICH = {G} 48
A 5 6 3 B C 1 4 D 9 7 4 E 8 G F 3 2 5 i T(i) MO DONG A0 A B C D B5 C3 D6 A C A B E F D B4 D6 E7 F11 A C B A C E D6 E7 F11 A C B D A C F G E7 F9 G15 A C B D E B C F F9 G15 A C B D E F C D E G G14 A C B D E F G Đường đi tỡm được p: A D F G. Chi phí của đường đi là 14. 6. Tỡm kiếm cực tiểu sử dụng hàm đánh giỏ - Thuật toỏn A* Đối với nhiều bài toán, việc tỡm kiếm đường đi cực tiểu sẽ được định hướng tập trung xung quanh đường đi tốt nhất; nếu sử dụng các thông tin đặc tả về bài toán gọi là các heuristic. Đối với việc tỡm kiếm đường đi với chi phí cực tiểu, người ta sử dụng hàm đánh giá heuristic như sau: Gọi g(n): giá cực tiểu đường đi từ n0 n. Tại đỉnh n, g(n) xác định được. Gọi h(n): giá cực tiểu đường đi từ n DICH, h(n) không xác định được người ta tỡm cỏch ước lượng giá trị này. Đặt f0(n)=g0(n)+h0(n): dự đoán chi phí cực tiểu của đường đi từ n0 DICH có đi qua đỉnh n. 49
g0(n) là chi phí của đường đi từ đỉnh xuất phát đến đỉnh n tại thời điểm đang xét. h0(n) là ước lưọng (dự đoán) chi phí đường đi từ đỉnh n đến đích. Việc chọn giá trị xấp xỉ h0(n) của h(n) không có một phương pháp tổng quát và được xem như một nghệ thuật. Giá trị này sẽ do các chuyên gia đưa ra. Lỳc này giải thuật tỡm kiếm cực tiểu sẽ thay việc xột hàm g bởi hàm f. Tuy nhiên, người ta cũng chứng minh được 2 kết quả như sau: Kết quả 1: Nếu h0(n) cú tớnh chất: 0 h 0 (n) h(n) n và c(u) 0 u E thỡ thủ tục TKCT sử dụng hàm f0(n) để chọn phần tử trong MO ra xét (thay g(n)) sẽ cho đường đi từ n0 n* DICH sao cho g(n* ) min g(n) n DICH 0 0 Kết quả 2: Giả sử dùng 2 hàm ước lượng h1 và h2 thoả tớnh chất: 0 0 h2 (m) h2 (n) h(m, n) (giá cực tiểu của đường đi từ m n) và 0 0 n N, 0 h1 (n) h2 (n) h(n) . Khi đó #DONG2 #DONG1 Nhận xột: h0  h phương án tốt nhất h0  0 phương án tồi nhất Thuật toỏn A* Input: Đồ thị G = (V,E), Đỉnh xuất phát n0 Hàm chi phớ c: E R+ c(i,j): xác định chi phí chuyển từ đỉnh i sang đỉnh j với (i,j) E h: V R+; h(n) xác định dự đoán chi phí tối ưu của đường đi từ đỉnh n đến đích. (ký hiệu h thay cho h0, (tương tự g)) Tập các đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến đỉnh n* DICH Procedure A* ; Begin 50
g(n0):= 0; push(MO, n0); While MO null then for m T(n) do if m MO+DONG then begin push(MO,m); tớnh f(m); cha(m):=n; end else if fmới(m) > fcũ(n) then begin f(m):= fmới(m); cha(m):=n; end; end; writeln(‘Khong co duong di’); End; Vớ dụ 1. Cho đồ thị biểu diễn bài toán và giá trị dự đoán h0 như sau: n A B C D E F G H 51
h0(n) 14 10 10 5 5 4 4 0 5 A 7 B 3 2 D C 4 7 6 3 E 5 12 F 2 G H 3 Tỡm đường đi từ đỉnh A đến đỉnh H. Trước tiên đỉnh A được đưa vào danh sách MO g(A) = 0; h(A) = 14; f(A) = 14 Xét đỉnh A, (đưa A vào danh sách DONG) ta có các đỉnh kề B, C, D: g(B) = 5; f(B) = 15; g(C) = 3; f(C) = 13; g(D) = 7; f(D) = 12 chọn đỉnh D. Xét đỉnh D (đưa D vào danh sách DONG) có các đỉnh kề A, C, E. Đỉnh A đó ở trong danh sỏch DONG, ta tớnh lại f(C) và tớnh f(E): f(C) không thay đổi; f(E) = g(D) +c(D,E) + H(E) = 7 + 6 + 5 = 18; f(E) = 18, chọn đỉnh C, có các đỉnh kề A, D, E. Tính lại f(E) = 12, chọn E. Các đỉnh kề của E là C, D, F, G. Tính f(F) = 14; f(G) = 16, chọn F. Các đỉnh kề của F là E, G, B và f(B), f(E), f(G) không đổi, chọn B. Các đỉnh kề của B là F, H. f(H) = 17, chọn G. Tớnh lại f(H) = 15 và dừng. Đường đi tỡm được là p: A C E G H với chi phí đường đi là 15 7. Phương pháp tỡm kiếm leo đồi (hill-climbing search) 7.1. Kỹ thuật tỡm kiếm leo đồi. Tỡm kiếm leo đồi là tỡm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tỡm kiếm theo độ sâu, khi phát triển một đỉnh u thỡ bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá. 7.2. Giải thuật. 52
Input: Đồ thị G = (V,E), đỉnh xuất phát n0. Hàm đánh giá h(n) đối với mỗi đỉnh n. Tập đỉnh đích DICH Output: Đường đi từ đỉnh n0 đến DICH Procedure HLC; {Hill Climbing Search} begin Push(MO,n0); while MO null then begin L:= null; for j T(i) do if j chưa xét then đưa j vào danh sách L sắp xếp L theo thứ tự hàm đánh giá; chuyển danh sách L vào đầu danh sách MO; end; write(‘Khong co loi giai’); end; 7.3. Nhận xột. Phương pháp tỡm kiếm leo đồi chú trọng tỡm hướng đi dễ dẫn đến trạng thái đích nhất. Cách đó được đưa ra nhằm làm giảm công sức tỡm kiếm. Thuật toỏn tỡm kiếm leo đồi thực chất là thuật toỏn tỡm kiếm theo chiều sõu, song tại 53
mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đich nhất để phát triển trước. Vấn đề quan trọng là biết khai thác kheo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhnah quỏ trỡnh tỡm kiếm. Thụng thường ta gán mỗi trạng thái của bài toán với một số đo (hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó. Điều đó có nghĩa là nếu trạng thái hiện thời là u thỡ trạng thỏi v sẽ được phát triển tiếp theo nếu v kề với u và hàm đanh giá của v đạt giá trị max (hoặc min). Tuy nhiên phương pháp này không được cải thiện so với các phương pháp khác trong một số trường hợp sau: Cực trị địa phương: nút đang xét tốt hơn các nút lân cận, nhưng đó không phải là phương án tốt nhất trong toàn thể, ví vậy có thể phải quay lui về nút trước để đi theo hướng khác. Giải pháp này đũi hỏi ghi nhớ lại nhiều đường đi. Cao nguyên bằng phẳng: Các giá trị của các phương án như nhau, không xác định được ngay hướng nào là tốt hơn trong vùng lân cận. 7.4. Cỏc vớ dụ. Vớ dụ 1. Bài toỏn trũ chơi 8 số. 2 8 3 1 2 3 trạng thái đầu 1 6 4 trạng thái đích 8 4 7 5 7 6 5 Trong bài toán này ta sử dụng hàm đánh giá, ký hiệu là h với ý nghĩa: h(u) cho biết số cỏc chữ số trong trạng thái u không trùng với vị trí cú nó trong trạng thái đích. Trạng thái có tiềm năng dẫn đến đích nhanh nhất (được ưu tiên phát triển trước) là trạng thái có hàm đánh giá h đạt giá trị min 54
Minh hoạ cõy tỡm kiếm cho trũ chơi này theo giải thuật leo đồi ở trang sau Trạng thái được chọn đi tiếp ở hướng mũi tên. Ở mức 3 chúng ta thấy có hai trạng thái cùng giá trị hàm đánh giá (= 3). Đây là trương hợp “cao nguyên băng phẳng” như nhận xét trên, nếu ta chọn phương án kia thỡ chắc chắn quỏ trỡnh tỡm kiếm sẽ khỏc đi nhiều. Trường hợp này dành cho độc giả. 55
2 8 3 1 6 4 7 5 h(u) = 4 2 8 3 2 8 3 2 8 3 1 6 4 1 4 1 6 4 7 5 7 6 5 7 5 h(u) = 5 h(u) = 3 h(u) = 5 2 8 3 2 3 2 8 3 1 4 1 8 4 1 4 7 6 5 7 6 5 7 6 5 h(u) = 3 h(u) = 3 h(u) = 4 2 3 2 3 1 8 4 1 8 4 7 6 5 7 6 5 h(u) = 2 h(u) = 4 1 2 3 8 4 7 6 5 h(u) = 1 1 2 3 1 4 7 5 Phương pháp sinh và thử. Chiến lược này đơn giản, gồm ba bước: 56
- Trước hết tạo ra một giải pháp. Trong vài bài toán cụ thể đó là việc chọn một lời giải trong không gian các lời giải hay tạo ra một đường đi. - Thứ hai, thử xem lời giải đó có thích hợp không bằng cách so sánh phương án khác hay so sanh với điểm cuối cần suy diễn. - Tiếp theo, nếu lời giải đạt được thỡ dừng, ngước lại, lặp lại từ bước đầu với nút khác. Với phương pháp này nếu bài toán có llời giải thỡ sẽ đưa đến đích. Tuy nhiên kích thước bài toán lớn sẽ tăng khối lượng tính toán. Việc tạo lời giải ban đầu có thể thực hiện ngẫu nhiên, và cũng hy vọng ngẫu nhiên mà đạt được lời giải, bởi vậy, không thể không tính đến chỉ một vài hướng đi được cảm nhận là tốt, và loại trừ trước các hướng không dẫn đến lời giải. Vớ dụ1. Tỡm số cú 6 chữ số mà tổng bỡnh phương các chữ số chia hết cho 3. Giai đoạn sinh: tạo ra số có 6 chữ số và ta gọi các chữ số từ trái qua phải lần lượt là a, b, c, d, e, f thỡ 0 < a <= 9 , 0 <= b, c, d, e, f <= 9. Giai đoạn thử: nểu a*a + b*b + c*c + d*d + e*e + f*f chia hết cho 3 thỡ chon, ngược lại, tạo ra số khỏc. Vớ dụ 2. Một xâu nhị phân được gọi là thưa nếu trong xâu không có hai chữ số 1 đứng kề nhau. Tỡm xõu nhị phõn thưa có chiều dài n. Giai đoạn sinh: Tạo ra một xâu nhị phân S có chiều dài n. Giai đoạn thử: Kiểm tra có phải xâu thưa không? (Pos(‘11’,S) = 0). Trong hai vớ dụ trờn, sinh viờn cú thể lập trỡnh để tỡm tất cả cỏc lời giải của bài toỏn, chẳng hain tỡm tất cả cỏc xõu nhị phõn thưa có chiều dài n cho trước. Vớ dụ 3. Một bệnh nhõn cú một vài triệu chứng, chẳng hạn: sốt cao về buổi chiều, ho và mệt mỏi , . Bác sĩ có chẩn đoán nghi bị lao phổi, người ta sẽ cho làm ngay xét nghiệm, nếu đúng là dương tính thỡ kết luận và điều trị bệnh lao 57
phổi, ngược lai, băt buộc bác sĩ phải chuyển hướng suy nghĩ sang một bệnh khác, v.v 58
Phương pháp thoả món ràng buộc. Phương pháp thoả món ràng buộc hổ trợ cho phương pháp sinh và thử, khi chú ý tới một số ràng buộc ỏp đặt lên các nút trong không gian bài toán. Mục đích đặt ra là xác định đường đi trong đồ thị không gian bài toán, đường đi từ trạng thái đầu đến trạng thái cuối đáp ứng một vài ràng buộc nào đó. Do vậy quá trỡnh tỡm kiếm lời giải bao gồm hai phần liờn quan chặt chẽ với nhau: - Tỡm kiếm trong khụng gian cỏc ràng buộc. - Tỡm kiếm trong khụng gian cỏc bài toỏn ban đầu. Nội dung của phương pháp như sau: Thực hiện các bước từ a) đến e) dưới đây cho đến khi tỡm được lời giải đày đủ của bài toán hoặc tất cả các đương đều đó duyệt qua nhưng không cho kết quả. a) Chọn một đỉnh chưa được xét trong đồ thị tỡm kiếm. b) Áp dụng cỏc luật suy diễn trờn cỏc ràng buộc đối với đỉnh đó chọn để tạo ra tập các ràng buộc mới. c) Nếu tập cỏc ràng buộc mới cú mõu thuẫn thỡ đưa ra thông báo đường đi hện thời tới nút đang xét dẫn tới bế tắc. d) Nếu tập ràng buộc mô tả lời giải đầy đủ của bài toán thỡ dừng và đưa ra thông báo thành công. Ngược lai, sang bước sau. e) Áp dụng các luật biến đổi không gian trạng thái tương ứng để tạo ra lời giải bộ phận, tương hợp với tập các ràng buộc hiện thời. Thêm các lời giải bộ phận này vào đồ thị tỡm kiếm. Vớ dụ. Xét bài toán điền các chữ số phân biệt thay cho các chữ cái S, E, N, D, M, O, R, Y sao cho phép cộng sau là đúng: SEND MORE MONEY Các ràng buộc ban đầu: - Cỏc chữ cỏi khỏc nhau khụng nhận cựng một giỏ trị. 59
- Cỏc ràng buộc số học (cộng cú nhớ hoặc khụng cú nhớ. Gọi C1, C2, C3, C4 lần lượt lá số nhớ của các cột từ phải sang trái. Khi đó ta xây dựng các ràng buộc cụ thể như sau: E, N, D,O, R, Y thuộc tập {0 9} (1) S, M thuộc tập {1 9} (2) C1, C2, C3, C4 thuộc tập {0,1} (3) D + E = Y + 10*C1 (4) N + R + C1 = E + 10*C2 (5) E + O + C2 = N + 10*C3 (6) S + M + C3 = O + 10*C4 (7) M = C4 (8) Từ ràng buộc (2) và (8) suy ra M = 1 và C4=1 (9) Từ ràng buộc (7) và (9) suy ra S +C3 = O + 9, lúc này có hai phương án để lựa chọn: Phương án 1: C3 = 0, khi đó ta có S = O + 9, như vậy S = 9 và O = 0 (10-1) Từ ràng buộc (6) ta cú E + C2 = N, suy ra C2 = 1 và E + 1 = N (11-1) Từ ràng buộc (5), ta có R + C1 = 9, như vậy R = 8 và C1 = 1 (12-1) (do kết hợp với cỏc ràng buộc (2) và (10-1). Từ ràng buộc (4) ta cú D + E = Y +10. Đến bứơc này ta có thể khảng định các giá trị của D, E, Y chỉ có thể nhận trong tập {2, 3, 4, 5, 6, 7}. Ngoài ra D + E >= 12. Vỡ vậy chỉ cú cỏc khả năng sau có thể xóy ra: - D = 5 và E = 7 - D = 7 và E = 5 (hai truờng hợp này Y = 2) - D = 6 và E = 7 - D = 7 và E = 6 (hai trường hợp sau Y = 3) 60
Xét khả năng thứ nhất. Từ ràng buộc (11-1) ta suy ra N = 8 mâu thuẫn với (12- 1) nên bị loại Xét khả năng thứ hai. Từ ràng buộc (11-1) ta suy ra N= 6. Kiểm tra điều kiện bài toán đều thoả món. Vậy ta cú nghiệm là: S = 9, E = 5, N= 6, D = 7, M= 1, O = 0, R = 8, Y = 2. Xét khả năng thứ ba. Từ ràng buộc (11-1) suy ra N = 8 mõu thuẫn với (12-1) Xét khả năng thứ tư. Từ ràng buộc (11-1) suy ra N=7 = D mõu thuẫn. Phương án 2. C3 = 1. Từ ràng buộc (7) ta cú S = O + 8, suy ra S = 8 và O = 0 (10-2) (vỡ M=1 và S <= 9). Từ ràng buộc (6) ta có E = N +10 mâu thuẫn với ràng buộc (1). vậy phương án 2 không có lời giải. Cài đặt một số giải thuật. Một số quy ước: Giả sử đồ thị G được cho bởi ma trận kề A. Các danh sách MO và DONG được lưu trong cùng một mảng, với các chỉ số riêng. Mảng logic Dau dùng để đánh dấu các đỉnh đó xột (nằm trong danh sỏch DONG 10.1. Tỡm kiếm rộng. Danh sách MO và DONG được lưu trong mảng Q, d và c là chỉ số của phần tử đầu và cuối của queue Q. V = { 1 n} Thủ tục Duyet_rong(i) đánh dấu tất cả các đỉnh từ i có thể đến được đỉnh đó. Procedure Khoitao; Begin 61
Fillchar (Dau, n, True); End; Procedure Duyet_rong (i:byte); Var Q: array [1 100] of byte; d, c, j, k: byte; Begin d:=1; {Khởi tạo hàng đợi rỗng } c:=1; Q[c]:= i; Dau[i]:= false; While d<=c do begin j:= Q[d]; inc(d); for k:=1 to n do if (A[j,k]=1) and Dau[k] then begin inc(c); Q[c]:=k; Dau[k]:=false; end; end; End; Vớ dụ 1. Tỡm đường đi từ đỉnh i0 đến đỉnh j0 của đồ thị G. Dữ liệu được lưu vào file Text có cấu trúc như sau: - Dũng đầu tiên chứa 3 số n, i0, j0 (n là số đỉnh của đồ thị) - n dũng tiếp theo lần lượt chứa giá trị n dũng của ma trận A. Tên file được nhập từ bàn phím khi thực hiện chương trỡnh. 62
Giỏ trị của mảng Truoc tạ vị trí j Truoc[j] xác định đỉnh đứng trước j trong đường đi tỡm được. Program đuongdi; Var A: array[1 50,1 50] of byte; Dau: array[1 50] of boolean; Truoc: array[1 50] of byte; n, i0, j0: byte; Procedure khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile); reset(f); readln(f,n,i0,j0); for i:=1 to n do begin for j:=1 to n do read(f, A[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; 63
Procedure BFS(i:byte); Var Q: array [1 50] of byte; d,c,j,k: byte; Begin d:=1; c:=1; Q[c]:=i; Dau[i]:=false; Truoc[i] := 0; While d 0 then inkq(truoc[j]); 64
write(j:4); End; Procedure Duyet; Var i:byte; Begin BFS(i0); if Dau[j0] then inkq(j0) else writeln(‘ Khong co duong di’); End; BEGIN {main} Khoitao; Duyet; Readln; END. Vớ dụ 2. Tỡm số thành phần liờn thụng của một đồ thị . Dữ liệu được lưu vào file Text có cấu trúc như sau: - Dũng đầu tiên chứa số n (số đỉnh của đồ thị) - n dũng tiếp theo lần lượt chứa giá trị n dũng của ma trận A. - Tên file được nhập từ bàn phím khi thực hiện chương trỡnh. Program lienthong; Var A: array[1 50,1 50] of byte; Dau: array [1 50] of boolean; n, So:byte; Procedure khoitao; 65
Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile); reset(f); readln(f,n); for i:=1 to n do begin for j:=1 to n do read(f, A[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); So:=0; End; Procedure BFS(i:byte); Var Q: array [1 50] of byte; d,c,j,k: byte; Begin d:=1; c:=1; Q[c]:=i; 66
Dau[i]:=false; While d<=c do begin j:=Q[d]; inc(d); for k:=1 to n do if (a[j,k]=1) and Dau[k] then begin inc(c) ; Q[c]:=k; Dau[k]:=false; end; end; End; Procedure Duyet; Var i:byte; Begin For i:=1 to n do If Dau[i] then begin inc(So); BFS (i); end; writeln(‘So thành phần liờn thụng:’, So); End; 67
BEGIN {main} Khoitao; Duyet; Readln; END. 68
10.2. Tỡm kiếm sõu. Với giả thiết như duyệt rộng, do MO hoạt động như stack nên dùng thủ tục đệ quy. Procedure DFS (i:byte); {Depth First Search} {Xuất phát từ đỉnh i, đánh dấu các đỉnh được xét khi tỡm kiếm theo chiều sõu} Var j: byte; Begin Dau[i]:=false; For j:=1 to n do If (a[i,j]=1) and Dau[j] then DFS (j); End; Vớ dụ 1. Tỡm đường đi từ đỉnh i0 đến đỉnh j0. Program Duong_di; Var A: array[1 50,1 50] of byte; Truoc: array [1 50] of byte; Dau: array [1 50] of boolean; n, i0, j0: byte; Procedure Khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); 69
readln(tenfile); assign(f, tenfile); reset(f); readln(f,n,i0,j0); for i:=1 to n do begin for j:=1 to n do read(f, a[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; Procedure DFS (i:byte); Var j: byte; Begin Dau[i]:=false; For j:=1 to n do If (a[i,j]=1) and Dau[j] then DFS (j); End; Procedure inkq(j: byte); Begin if Truoc[j] <> 0 then inkq(truoc[j]); write(j:4); 70
End; Procedure duyet; Begin DFS(i0); if dau[j0] then inkq(j0) else writeln(‘Khong co duong di’); End; BEGIN {main} Khoitao; Duyet; Readln; END. Vớ dụ 2. Tỡm tất cả hoỏn vị của (1,2, n) Program hoanvi; Var A:array [1 50] of byte; n:byte; Dau: array [1 50] of boolean; Procedure Khoitao; Begin write(‘n = ‘); readln(n); Fillchar(Dau,n, true); 71
End; 72
Procedure DFS (i:byte); Begin if i<n then for j:=1 to n do if Dau[j] then begin A[i]:=j; Dau[j]:=false; DFS (j); Dau[j]:=true; end else begin j:=1; While not Dau[j] do inc (j); a[n]:=j; begin for j:=1 to n do write (A[j]:4); witeln; end; end; End; BEGIN {main} Khoitao; DFS (1); Readln; 73
END. 10.3. Thuật toỏn AT – Tỡm kiếm cưc tiểu. Giả thiết dữ liệu lưu trữ như tỡm kiếm rộng. cp là mảng chi phí của đồ thị G. Đồ thị G được lưu trữ bởi ma trận chi phí cp, trong đó cp[i,j] = Vocung có nghĩa là không có cung (i,j). Procedure ddcuctieu; Const Vocung = 70000; Var A: array[1 50,1 50] of byte; Truoc: array [1 50] of byte; Dau: array [1 50] of boolean; cp: array[1 50, 1 50] of word; n, i0, j0: byte; Procedure Khoitao; Var i, j : byte; f:text; tenfile:string; Begin write(‘ten file’); readln(tenfile); assign(f, tenfile); reset(f); readln(f,n,i0,j0); 74
for i:=1 to n do begin for j:=1 to n do read(f, cp[i,j]); readln(f); end; close(f); Fillchar (Dau,n,true); End; Procedure inkq(j: byte); Begin if Truoc[j] <> 0 then inkq(truoc[j]); write(j:4); End; Procedure Timkiem; Begin g[i0]:=0; truoc[i0]:=0; d:=1; c:=1; Q[c]:=i0; While d<=c do begin k:=d; for l:=d+1 to c do if g[q[l]]<g[q[k]] then 75
k:=l; tam:=q[d]; q[d]:=q[k]; q[k]:=tam; m:=q[d]; inc(d); if m=j0 then inkq(j0) else for l:=1 to n do if (cp[m,l] g[m]+cp[m,n] then begin g[l]:= g[m]+cp[m,n]; truoc[l]:=m; end; end; End; 76
Begin Khoitao; Timkiem; End; 10.4. Tỡm kiếm leo đồi. Trong chương trỡnh cài đặt này, chúng ta quy ước nếu đỉnh đang xét là đỉnh u, thỡ đỉnh kề với u có khả năng đến đích nhất là đỉnh có khoảng cách với u lớn nhất. Khi đó giải thuật leo đồi có thể trỡnh bày lại như sau. Leodoi(i,j): Thực hiện giải thuật leo đồi từ đỉnh i đến đỉnh j. - Nếu (i, j) E : d=c[i,j], push(i,j,k), exit - Nếu (i,j) E: Tỡm k sao cho c[i,k]=max {c[l,k]/ l T[i] and dau[i,l]}: Nếu cú (d=c[l,k]): dau[i,l]=false, push(i,j,d), Leodoi(k,j) Ngược lại (d=0): pop(k,j,d), leodoi(k,j) Dữ liệu đựơc thiết kế như sau: - Mảng A lưu danh sách các cung của đồ thị G - S là stack lưu danh sách các đỉnh sẽ được xét và Top là đỉnh của S - i0, j0 là đỉnh xuất phát và đỉnh kết thúc - Toàn bộ thông tin được lưu trong file dạng Text có cấu trúc như sau: dũng đầu lưu m (số cung của đồ thị), i0, j0; m dũng tiộp theo mỗi dũng chứa thông tin của mộtcung đồ thị G (đỉnh đầu, đỉnh cuối và độ dài cung). Procedure Leodoi; Type cung = record dau, cuoi: byte; 77
kc: word; end; Var S, A: array[1 50] of cung; B: array[1 50] of boolean; m,i0,j0, Top: byte; Procedure Khoitao; Var f: text; l: byte; d: word; tenfile: string; begin write(‘Nhap ten file: ‘); readln(tenfile); assign(f,tenfile); reset(f); readln(f,m,i0,j0); for l:=1 to m do with A[l] do readln(f,dau, cuoi, kc); fillchar(B, l, false); Top:= 0; end; Procedure Pop( Var i,j: byte; var d: word); {Lấy một bản ghi (i,j,d) từ S} begin 78
with S[Top] do begin i:= dau; j:= cuoi; d:= kc; end; dec(Top); end; Procedure TimKiem(i: byte; Var j: byte; var d: word); { Tỡm cung (i,j) cú c[i,j] lớn nhất, nếu cú thỡ d = c[i,j] và đấnh dấu cung ơi,jư là true, ngược lại d = 0 } Var l,p: byte; begin d:=0; for l:= 1 to m do if (A[l].dau = i) and (A[l].kc > d) and not B[l] then begin j:= A[l].cuoi; p:= l; d:= A[l].kc; end; B[l]:= true; end; Function DenDich(i,j: byte; var d:word): boolean; Var 79
l: byte; begin for l:= 1 to m do if (A[l].dau = i) and (A[l].cuoi = j) then begin d:= A[l].kc; DenDich:= true; end else begin DenDich:= false; d:= 0; end; end; Procedure Inkq(j:byte); Var d:word; k: byte; begin d:=0; for k:= 1 to Top do begin write(S[k].dau); d:=d + S[k].kc; end; writeln(j); writeln(‘ Chi phi: ‘,d); 80
end; Procedure Duongdi(i,j: byte); Var k,d: byte; Begin if Dendich(i,j) then begin push(i,j,d); inkq(j); exit; end; Timkiem(i,k,d); if d > 0 then begin push(i,j,d); duongdi(k,j); end else if Top > 0 then begin pop(i,j,d); duongdi(i,j); end else writeln(‘Khong co duong di’); end; 81
Begin {leo doi} Khoitao; Duongdi(i0,j0); end; 82
11. Bài tập. Bài tập 1. Cho ma trận kề A= (aij) biểu diễn một đồ thị vô hướng G = (V,E) dưới đây: 0 4 4 0 7 3 7 0 3 8 6 3 0 5 8 5 0 2 3 6 2 0 trong đó aij= nếu (i,j) E, ngược lại aij là chi phí để đi từ đỉnh i sang đỉnh j. a. Hóy tỡm đường đi từ đỉnh 1 sang đỉnh 4 theo các phương pháp tỡm kiếm rộng và tỡm kiếm sõu. b. Tỡm đường đi ngắn nhất từ đỉnh 1 sang đỉnh 4 LờI GIảI - Vẽ đồ thị G được biểu diễn bởi ma trận kề A ở trên 4 3 1 2 6 7 6 2 3 8 5 3 5 4 83
- Phương pháp duyệt rộng n t(n) open  close 1 1 2 2 1 2 1, 3, 6 3, 6 1, 2 3 2, 4, 5, 6 6, 4, 5 1, 2, 3 6 2, 3, 5 4, 5 1, 2, 3, 6 4 dich dừng Đường đi từ đỉnh 1 đến đỉnh 4 theo phương pháp duyệt rộng là: 1 2 3 4 - Phương pháp duyệt sâu n t(n) open  close 1 1 2 2 1 2 1, 3, 6 3, 6 1, 2 6 2, 3, 5 3, 5 1, 2, 6 5 3, 4, 6 3, 4 1, 2, 6, 5 4 dich dừng Đường đi từ đỉnh 1 đến đỉnh 4 theo phương pháp duyệt sâu là: 1 2 6 5 4 - Phương pháp tỡm kiếm cực tiểu n t(n) open close 10 1 2 24 1 2 1, 3, 6 311, 67 1, 2 6 2, 3, 5 311, 59 1, 2, 6 5 3, 4, 6 311, 414 1, 2, 6, 5 3 2, 4, 5, 6 414 1, 2, 6, 5, 3 4 DICH 84
dừng Vậy đường đi ngắn nhất: 1 2 6 5 4 với chi phớ 14 Bài tập 2. Người ta sử dụng hai bỡnh chứa cú dung tớch lần lượt là 3(lít) và 4(lít) để đong 2(lít) nước. giả sử lượng nước được lấy từ vũi khụng hạn chế và cụng để lấy nước từ vũi cho đầy một bỡnh là 3, cụng để đổ nước trong một bỡnh ra ngoài là 2 và đổ nước từ bỡnh này sang bỡnh khỏc thỡ tốn cụng là 5. Hóy chỉ ra quỏ trỡnh tỡm kiếm lời giải bằng phương pháp tỡm kiếm theo chiều rộng và tỡm kiếm leo đồi. Lời giải - Phương pháp tỡm kiếm theo chiều rộng n t(n) open  close (0,0) (0,0) (0,4), (3,0) (0,4), (3,0) (0,0) (0,4) (0,0), (3,4), (3,1) (3,0), (3,4), (0,0), (0,4) (3,0) (0,0), (3,4), (0,3) (3,1) (0,0),(0,4),(3,0) (3,4) (0,4), (3,0) (3,4), (3,1), (0,0),(0,4),(3,0), (3,4) (3,1) (0,1), (3,0), (3,4), (0,3) (0,0),(0,4),(3,0), (3,4), (3,1) (0,3) (0,4) (0,0), (0,4), (3,1), (0,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3) (3,3), (3,0) (0,3), (0,1) (0,1) (0,0), (3,1), (0,4), (0,1), (3,3) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (1,0) (3,3), (1,0) (0,1) (3,3) (0,3), (3,0), (2,4) (1,0), (2,4) (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (0,1), (3,3) (1,0) (0,0), (3,0), (1,4), (2,4), (1,4), (0,0),(0,4),(3,0), (3,4), (3,1), (0,3), (0,1) (0,1), (3,3), (1,0) (2,4) 85
Quỏ trỡnh đong nước theo phương pháp duyệt rộng là: (0,0) (3,0) (0,3) (3,3) (2,4) - Phương tỡm kiếm leo đồi (giả thiết đỉnh kề với đỉnh đang xáe và có khoảng cách đên đỉnh đó lớn nhất là đỉnh có triển vọng đến đích nhất) ((0,0), (2,4)) E k= (3,0) c[(0,0), (3,0)]=5 ((3,0), (2,4)) E k= (0,3) c[(3,0), (0,3)]=5 ((0,3), (2,4)) e k= (3,3) c[(0,3), (3,3)]=5 ((3,3), (2,4)) E dừng c[(3,3), (2,4)]=5 Quỏ trỡnh đong nước theo phương pháp leo đồi là: (0,0) (3,0) (0,3) (3,3) (2,4) với chi phớ 20 Bài tập 3. Đại dương được xem như là một mặt phẳng toạ độ trên đó có n hũn đảo với toạ độ lần lượt là (x1, y1), (x2, y2), , (xn, yn). Một chiếc ca nô xuất phát từ đảo d1 muốn tuần tra đến đảo d2. bỡnh xăng của ca nô chỉ chứa đủ xăng để đi được một quóng đường dài không quá m (km). Trên đường đi ca nô có thể ghé một số đảo nào đó để tiếp thêm xăng, lúc này ca nô được tiếp thêm xăng đầy bỡnh chứa. Hóy chỉ ra một đường đi từ đảo d1 đến đảo d2 sao cho số lần ghé đảo trung gian để tiếp thêm xăng là ít nhất. Hướng dẫn Ta xem hai đảo là kề nhau nếu khoảng cách giữa chúng không vượt quỏ m (km). Bài toỏn cần tỡm đường đi từ đảo d1 đến đảo d2 thông qua các đảo kề nhau. Thuật toỏn tỡm kiếm theo chiều rộng cho phộp tỡm đường tỡm ra đường đi nối hai đảo qua ít cạnh trung gian nhất (tức là ít đảo trung gian nhất). 86
Dữ liệu vào lưu trong file dạng text, dũng đầu chứa số đảo n, dũng thứ hai chứa khoảng cỏch lớn nhất cano cú thể đi liên tục, n dũnh tiếp theo mỗi dũng chứa hai giỏ trị tương ứng với toạ độ của mỗi đảo. Bài tập 4. Một mạng lưới giao thông giữa n thành phố (các thành phố được đánh số từ 1 đến n) được cho bởi ma trận a=(aij)n*n , trong đó: 0, nếu không có đường đi trực tiếp từ i đến j aij= 1, nếu có đường đi trực tiếp từ i đến j và là đường đi an toàn 2, nếu có đường đi trực tiếp từ i đến j nhưng phải qua một chặng đường nguy hiểm Quy ước: aii=1, i =1 n Cho trước hai thành phố i0, i1. hóy tỡm một đường đi từ i0 đến i1 sao cho số chặng đường nguy hiểm phải đi qua là ít nhất. Hướng dẫn: Trước hết phải xác định đồ thị biểu diễn bài toán. Ở đây dễ thấy rằng mỗi thành phố tương ứng với một đỉnh của đồ thị, vấn đề chỉ cũn xỏc định tập cung E căn cứ vào giả thiết của bài toán. Bài tập 5. Cho bảng vuụng gồm m*n ụ. Trờn mỗi ụ ghi số 0 hay 1. a. Từ một ô nào đó có thể chuyển sang ô chứa số 1 có chung cạnh với nó. giả sử đang ở ô (h,c). Hóy tỡm xem cú cỏch di chuyển từ ụ này ra một ụ ở mộp bảng hay khụng? Tỡm cỏch chuyển qua ớt ụ nhất. b. Một miền của bảng là tập hợp cỏc ụ cú chung cạnh và cú cựng giỏ trị. hóy đếm xem bảng có bao nhiêu miền. miền lớn nhất có bao nhiêu ô. c. Cho phép thay đổi giá trị tất cả các ô trong cùng một miền. Hóy xỏc định miền cần thay đổi để số miền giảm nhiều nhất. d. Hóy xỏc định miền cần thay đổi để thu được một miền mới lớn nhất. 87
Hướng dẫn: Mỗi ô tương ứng với một đỉnh của đồ thị. Hai đỉnh kề nhau khi và chỉ khi hai ô tương ứng có thể chuyển sang nhau. Mỗi miền của bảng tương ứng với một miền liên thông của đồ thị. Bài tập 6. Lập chương trỡnh đối với bài toán đong nước, với các số m, n, k là các số dương bất kỳ được nhập từ bàn phím khi thực hiện chương trỡnh. Hướng dẫn: Sử dụng thuật toỏn tỡm kiếm rộng sẽ cho số lần thao tỏc là ớt nhất. Bài tập 7. Một toà lâu đài được mô tả bằng một hỡnh chữ nhật cú m*n ụ. Giữa cỏc ụ cú một số bức tưũng ngăn cách chia lâu đài thành các phũng. Như vậy, mỗi phũng tương ứng với tập cỏc ụ thụng nhau. Tại ô (i,j), cho biết thông tin có tường ngăn giữa ô này với bốn ô kề với nó không bởi giá trị aij là một số nhị phân 4 chữ số tương ứng ô (i,j) có (1) hoặc không có (0) tường ở phía Tây, Bắc, Đông, Nam. Vớ dụ aij = 1001 cú nghĩa là ô (i,j) có tường ở phía Tây và Nam, nhưng không có tường ở phía Bắc và Đông. Hóy viết chương trỡnh thực hiện cỏc yờu cầu sau: a. Đếm số phũng của toà lõu đài. b. Cho biết phũng lớn nhất cú diện tớch là bao nhiờu ụ. c. Cho biết nờn phá bức tường ngăn hai phũng nào để được một phũng mới cú diện tớch lớn nhất. Hương dẫn: Giỏ trị aij có thể nhận tương ứng với số thập phân từ 0 đến 15. Vỡ vậy ta lưu dữ liệu trong file dạng text có cấu trúc như sau: dũng đầu chứa hai số m,n. Từ dũng thứ hai đến dũng thứ m+1, chứa cỏc hàng của ma trận A = (aij). Kết quả đưa ra file dạng text có cấu trúc như sau: dũng đầu chứa số phũng, dũnh hai chứa diện tớach phũng lớn nhất và dong ba chứa hàng, cột, hướng của bức tường cần phá. Chẳng hạn dữ liệu vào là 88
4 6 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 Dữ liệu ra sẽ là: 5 9 4 1 Dong Bài tập 8. Một sân chơi hỡnh chữ nhật gồm m*n ụ đơn vị. Trên mỗi ô (i,j) có đóng các trụ bê tông chiều cao aij. Giả thiết nước không thấm qua được các cạnh giữa hai trụ bờ tụng kề nhau. Sau một trận mưa đủ lớn, hóy tớnh nước đọng lại trên sân. Hướng dẫn Chia nước thành từng tầng có chiều cao bằng 1. Tính thể tích nước đọng trên mỗi tầng theo thuật toán loang tỡm thành phần liờn thụng. Bài tập 9. Tỡm 2 chữ số phõn biệt a và b sao cho thoó món hai điều kiện sau: a. a2b chia hết cho 3 b. a2b - ab=110 Bài tập 10. Gảii bài toán đoán chữ sau DONALD CROSS + GERALD + 89
ROADS ROBERT DANGER Bài tập 11. Cho số cú hai chữ số. Nếu viết thờm hai chữ số về bờn phải số đó thỡ được số mới lớn hơn số đó ho là 1986 đơn vị. Hóy tỡm số đó cho và hai chữ số viết thờm đó. Bài tập 12. Giải bài toán đoán chữ sau: T + TH THA THAN 4321 Chương trỡnh tham khảo Program cano_di_tuan; { Bài tập 3} uses crt; type dao = record x,y: integer; end; var n,d1,d2,so: byte; m: word; a: array[byte] of dao; b: array[byte] of boolean; tr: array[byte] of byte; 90
procedure nhap; var f: text; s: string[20]; i: byte; begin clrscr; write('ten file du lieu:'); readln(s); assign(f,s); reset(f); readln(f,n); readln(f,m); for i:=1 to n do with a[i] do readln(f,x,y); close(f); end; procedure indulieu; var i: byte; begin writeln('so dao:',n); writeln('gioi han khoang cach:',m); for i:=1 to n do with a[i] do writeln('toa do dao ',i,' : (',x,',',y,')'); end; 91
procedure khoitao; var i: byte; begin for i:=1 to n do b[i]:= true; end; function kc(i,j: byte):real; begin kc:= sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); end; procedure bfs(i: byte); var j,k,d,c: byte; q: array[byte] of byte; begin d:=1; c:=1; q[1]:=i; b[i]:= false; while d<=c do begin j:= q[d]; d:=d+1; for k:=1 to n do 92
if b[k] and (kc(k,j) d2 do begin write(' >',tr[i]); so:=so+1; i:=tr[i]; end; writeln; writeln('duong di tren ghe qua ',so-1,' dao'); end; 93
procedure timduongdi; begin write('dao xuat phat: '); readln(d1); write('dao ket thuc: '); readln(d2); bfs(d2); if b[d2] then write('khong co duong di tu ',d1,' den ',d2) else inketqua; readln; end; BEGIN nhap; khoitao; indulieu; timduongdi; END. Program laudai; { Bài tập 7} uses crt; type size = 0 100; var m,n,so,p,hang,cot: size; A:array[size,size] of 0 15; ph: array[size,size] of word; S: array[size] of word; 94
dt: word; huong: string[4]; procedure nhap; var f: text; i,j: size; begin clrscr; assign(f,'input.pas'); reset(f); read(f,m,n); for i:=1 to m do for j:=1 to n do read(f,A[i,j]); close(f); end; procedure khoitao; var i,j: size; begin for i:=1 to m do for j:=1 to n do ph[i,j]:=0; so:=0; end; 95
procedure bfs(i,j: size); var qh,qc: array[size] of size; d,c,k,l: size; begin ph[i,j]:= so; d:=1; c:=1; qh[1]:=i; qc[1]:=j; while d =8 then S[k,l]:=A[k,l]-8 else if (k =4 then A[k,l]:=A[k,l]-4 else 96
if (l =2 then A[k,l]:= A[k,l]-2 else if (k>1) and (ph[k-1,l] = 0) then begin c:=c+1; qh[c]:=k-1; qc[c]:=l; ph[k-1,l]:=so; end; if A[k,l] >=1 then A[k,l]:= A[k,l]-1 else if (l>1) and (ph[k,l-1]=0) then begin c:=c+1; qh[c]:=k; qc[c]:=l-1; ph[k,l-1]:=so; end; end; 97
end; procedure demphong; var i,j: size; begin for i:=1 to m do for j:=1 to n do if ph[i,j] = 0 then begin so:= so+1; bfs(i,j); end; end; procedure smax; var i: word; j,k: size; begin dt:=0; for i:=1 to so do begin S[i]:=0; for j:=1 to m do for k:=1 to n do if ph[j,k]=i then S[i]:= S[i]+1; if S[i] > dt then dt:= S[i]; 98
end; end; procedure phatuong; { Chỉ cần phá phía Đông hoặc phía Nam, phía Tây của ô (i,j) tương ứng là phía Đông của ô (i,j-1), tươnh tự, phía Bắc của ô (i,j) tương ứng phía Nam của ô (i- 1,j)} var i,j: size; max,tg: word; begin max:=0; for i:=1 to m do for j:=1 to n do begin if i ph[i+1,j] then begin tg:= S[ph[i,j]] + S[ph[i+1,j]]; if tg >= max then begin hang :=i; cot:=j; huong:= 'nam'; max:= tg; end; end; if j<n then 99
if ph[i,j] = max then begin hang:=i; cot:=j; huong:= 'dong'; max:= tg; end; end; end; end; procedure inkq; var i,j: size; f: text; begin assign(f,'out.pas'); rewrite(f); writeln(f,so); writeln(f,dt); writeln(f,hang,' ',cot,' ',huong); close(f); end; BEGIN nhap; 100
khoitao; demphong; smax; phatuong; inkq; END. Chương 3 PHÂN RÃ BÀI TOÁN - TèM KIẾM LỜI GIẢI TRÊN ĐỒ THỊ VÀ/ HOẶC 1. Đặt vấn đề. Trong chương 2, chúng ta đó nghiờn cứu việc biểu diễn bài toỏn thụng qua cỏc trạng thỏi và cỏc toỏn tử. Khi đó việc tỡm lời giải của bài toỏn được quy về việc tỡm đường đi trong không gian trạng thái. Trong chương này chúng ta sẽ nghiên cứu một phương pháp luận khác để giải quyết vấn đề, dựa trên việc quy vấn đề về các vấn đề con. í tưởng chủ yếu là xuất phát từ bài toán ban đầu, tách ra các bài toán con, quá trỡnh này tiếp tục đối với các bài toán con cho đến khi gặp các bài toán sơ cấp (bài toán có lời giải ngay). Vớ dụ 1. Xột bài toỏn tớnh tớch phõn x(ln x x2 )dx . Thông thường để tính tích phân bất định, chúng ta thường sử dụng các quy tắc tính tích phân: tích phân của tổng, quy tắc tích phân từng phần hay các phép biến đổi v.v để đưa tích phân cần tính về tích phân của các hàm số sơ cấp mà chúng ta đó biết cỏch tớnh. Đối với tích phân trên, áp dụng quy tắc tích phân của tổng ta đưa về hai tích phân xlnxdx và tớch phõn x3dx. Áp dụng quy tắc tích phân từng phần ta đưa tích phân xlnx về tớch phõn xdx. Quỏ trỡnh trờn cú thể biểu diễn bởi đồ thị trong Hỡnh 1. x(lnx+x2)dx 101 xlnxdx x3dx
Hỡnh 1. Trong bài toán tích phân, các tích phân cơ bản là các trạng thái kết thúc. Vớ dụ 2. Bài toỏn tỡm đường đi trên bản đồ giao thông. Bài toán này đó được phát biểu như bài toán tỡm đương đi trong không gian trạng thái, trong đó mỗi trạng thái ứng với một thành phố, mỗi toán tử ứng với một con đường, nối thành phố này với thành phố khác. Bây giờ ta đưa ra một cách bểu diễn khác dựa trên việc quy vấn đề về các vấn đề con Xét bản đồ giao thông giữa các thành phố trong Hỡnh 2. A C D H F E G I B K Hỡnh 2. Giả sử ta cần tỡm đường đi từ thành phố A đến thành phố B. Có một con sông chảy qua hai thành phố E và G và có cầu qua sông ở mỗi thành phố đó. Như vậy mọi đường đi từ A đến B đều phải đi qua E hoặc G. Khi đó bài toán tỡm đường đi từ A đến B được quy về một trong hai bài toán: 102
1) Bài toỏn tỡm đường đi từ A đến B qua E 2) Bài toỏn tỡm đường đi từ A đến B qua G Mỗi một bài toán trên lại có thể phân nhỏ như sau: 1) Bài toỏn tỡm đường đi từ A đến B qua E được quy về: 1.1. Tỡm đường đi từ A đến E và 1.2. Tỡm đường đi từ E đến B 2) Bài toỏn tũm đường đi từ A đến B qua G được quy về: 2.1. Tỡm đường đi từ A đến G và 2.2. Tỡm đường đi từ G đến B Tổng quát, từ bài toán P ta đưa về một trong các trường hợp: - Đưa P về các bài toán tương đương: P1, P2, , Pk - Đưa P về các bài toán con: P1, P2, , Pk Phương pháp phân chia bài toán ban đầu như trên đó gặp trong lập trỡnh truyền thống với cỏch gọi “chia để trị” , “Modul hoá”. 2. Đồ thị VÀ/HOẶC: Không gian trạng thái mô tả việc quy vấn đề về các vấn đề con có thể biểu diễn dưới dạng đồ thị định hướng đặc biệt gọi là đồ thị và/hoặc. Đồ thị này được xây dựng như sau: Mỗi bài toán ứng với một đỉnh của đồ thị. Nếu có một toán tử quy bài toán về các bài toán tương đương thỡ sẽ cú cỏc cung đi từ bài toán xuất phát đến các bài toán tương đương đó. Nếu một toỏn tử quy bài toỏn về cỏc bài toỏn con thỡ cũng cú cỏc cung nối từ bài toỏn xuất phỏt đến các bài toán con, ngoài ra giữa các cung này cũng có đường nới với nhau Chẳng hạn, giả sử bài toán A được đưa về hai bài táon tương đương A1 và A2. Bài toán A1 lại được quy về hai bài toán con B1 và B2, ta có biểu diễn như hỡnh 3. 103
A A1 A2 B1 B2 Hỡnh 3 Một cỏch hỡnh thức ta cú thể định nghĩa đồ thị và/hoặc như sau: Đồ thị G = (V, E) được gọi là đồ thị VÀ/HOẶC nếu n V , T(n) hoặc các bài toán con của n (n gọi là các đỉnh VÀ) hoặc là tập các bài toán tương đương với n (n gọi là đỉnh HOẶC). Cách biểu diễn như sau: n n1 n2 nk n được gọi là đỉnh HOẶC (n n1 nk ) n n1 n2 nk n được gọi là đỉnh VÀ (n n1  nk ) KHI ĐÓ Để GIảI BÀI TOỏN N TA PHảI TỡM Đồ THị CON CủA G LÀ MộT CÂY CÓ GốC LÀ ĐỉNH XUấT PHÁT N SAO CHO MọI ĐỉNH TRÊN Đồ THị CON NÀY ĐƯA Về ĐƯợC CÁC BÀI TOÁN SƠ CấP (ĐỉNH KếT THÚC). Nhận xét: Gọi VA: tập các đỉnh VÀ 104
VO: tập các đỉnh HOẶC Nếu VA=  tỡm lời giải trờn đồ thị biểu diễn bằng khụng gian trạng thỏi Khi đó: - Bài toán n được gọi là giải được nếu: + hoặc n là đỉnh kết thúc + hoặc T(n)={n1, n2, , nk} và nếu n là đỉnh HOẶC i (1 k) sao cho ni giải được, ngược lại ni giải được i 1 k . - Bài toán n được gọi là không giải được nếu: + hoặc n là đỉnh lá và n không phải là đỉnh kết thúc. + hoặc T(n)={n1, n2, , nk}và nếu n là đỉnh HOẶC i (1 k) sao cho nj không giải được, ngược lại ni không giải được i 1 k . Để tỡm lời giải của bài toỏn khi được phân ró về đồ thị VÀ/HOẶC không phải tỡm đường đi mà phải đi tỡm đồ thị con gọi là đồ thị con lời giải (hay cây lời giải) Cây lời giải là đồ thị con G’ của G thoả: - Đỉnh gốc (xuất phát) n0 V' - n V ' , n giải được. Ta có sự tương quan: Phõn ró bài toỏn Đồ THị VÀ/HOẶC Bài toỏn Đỉnh Chuyển bài toỏn thành cỏc bài toỏn Cung con Bài toán sơ cấp Đỉnh cuối 105
Cỏc bài toỏn con phụ Đỉnh VÀ Các bài toán con độc lập Đỉnh HOẶC Giải bài toỏn Tỡm đồ thị con lời giải bài toán 3. Các phương pháp tỡm kiếm lời giải trờn đồ thị và/hoặc. Sau khi lựa chọn mô tả bài toán và các toán tử quy bài toán về bài toán con, ta có thể xây dựng đồ thị Và/hoặc để giải quyết bài toán ban đầu hoặc chứng tỏ tính không giải được của nó. Cũng như đồ thị trong không gian trạng thái, đồ thị và/hoặc có thể cho dưới dạng tường minh hoặc không tường minh trên cơ sở toán tử xây dựng. Các phương pháp tỡm kiếm trờn đồ thị và/hoặc khác nhau chủ yếu ở phương pháp lựa chọn và sắp xếp đỉnh trước khi tháo chúng. Tương tự như trong không gian trạng thái, ta cung có các phương pháp sau: - Tỡm kiếm theo chiều rộng. - Tỡm kiếm theo chiều sõu. - Tỡm kiếm cõy lời giải cú giỏ nhỏ nhất. Cỏc quỏ trỡnh này khỏc hẳn với cỏc quỏ trỡnh lựa chọn trong khụng gian trạng thỏi. Sự khỏc biệt chủ yếu là do việc kiểm tra tớnh kết thỳc của quỏ trỡnh tỡm kiếm và cỏc phương pháp sắp xếp và lựa chọn đỉnh để xét phức tạp hơn nhiều Thay cho việc tỡm kiếm đỉnh thoả món điều kện đích, chúng ta phải tiến hành tỡm kiếm đồ thị lời giải. Do đó, ở những thời điểm nhất định, ta phải kiểm tra xem đỉnh đầu có giải được hay không, nếu đỉnh đầu giải được thỡ kết thỳc cụng việc, trong trường hợp ngược lại thỡ tiếp tục xột cỏc nỳt. Nếu đỉnh đang xét không phải là đỉnh kết thúc và nó là đỉnh lá, tức là đỉnh không giải được. Lúc 106
này phải kiểm tra đỉnh đàu có phải không giải được hay không, nếu đúng thỡ dừng, ngược lại, tiếp tục tỡm kiếm. Trước khi tỡm kiếm lời giải trong đồ thị VÀ/HOẶC, chúng ta xây dựng các hàm kiểm tra một đỉnh n nào đó tại thời điểm đang xét có giải được hay không giải được không? Function giaiduoc(n):boolean; Begin If then giaiduoc:=true else if T(n) null then if T(n)VA then khonggd or(khonggd(m)) m T (n) else 107
khonggd and(khonggd(m)) m T (n) else if then khonggd:=true else khonggd:=false; End; 3.1. Phương pháp tỡm kiếm chiều rộng: Procedure TKR; Begin Push(n0, MO); While MO null then for m T (n) do begin push(m, MO); if T(m)=null then if giaiduoc(m) then if giaiduoc(n0) then exit else for k MO do if giaiduoc(k) then 108
MO:=MO-[k] Else If khonggd(m) then If khonggd(n0) then Exit Else For k MO do if khonggd(k) then MO:=MO-[k] end; end; write(‘Khong ket luan’); End; Nhận xột: Nếu tồn tại cõy lời giải thỡ thủ tục tỡm kiếm rộng sẽ dừng và cho kết quả là cõy lời giải cú độ cao nhỏ nhất. Vớ dụ. Xét đồ thị Hỡnh 3. A B C D E* F G H* I J K L* M* N O* Hỡnh 3 109
CÁC ĐỉNH KếT THÚC LÀ CÁC ĐỉNH ĐÁNH DấU *. QUỏ TRỡNH TỡM KIếM LờI GIảI CủA ĐŨ THị TRờN BằNG PHƯƠNG PHÁP TỡM KIếM RộNG CÚ THể TRỡNH BÀY ở BảNG SAU n T(n) MO DONG A A B, C, D B C D A B E*, F C D F A B C G D F G A B C D H*, I F G I A B C D F J G I J A B C D F G K0 I J A B C D F G I L* Dừng Cõy lời giải ở Hỡnh 4. A D H* I L* Hỡnh 4 3.2. Tỡm kiếm theo chiều sõu: Hoàn toàn tương tự tỡm kiếm theo chiều rộng, chỉ khỏc thứ tự lấy cỏc đỉnh trong danh sách MO ra xét. Ở đây MO được truy xuất theo nguyờn tắc LIFO. Vớ dụ. Xét đồ thị ở Hỡnh 5. A B C 110
D E F* G H* I* J* K* L* M* Hỡnh 5. Quỏ trỡnh tỡm theo chiều sõu tiến hành như sau: n T(n) MO DONG A A B, C B C C F* , G BG G L*, M* : giải được A giải được CÕY LờI GIảI ở HỡNH 6. A C F* G L* M* Hỡnh 6. 111
3.3. Tỡm kiếm cõy lời giải cực tiểu: Cõy G=(V, E) biểu diễn sự phõn ró của bài toỏn gốc n0. ỨNG VớI MỗI PHộP CHUYểN BÀI TOỏN N SANG BÀI TOỏN V TốN CHI PHớ C(U,V). c: E R+ (u,v) c(u,v) Vấn đề đặt ra tỡm cõy lời giải cú tổng chi phớ bộ nhất. Đối với không gian trạng thái, ta đó sử dụng hàm đánh giá để sắp thứ tự các nút trong MO trước khi xử lý và hàm h(n) là giỏ của đường đi tối ưu từ đỉnh n DICH. Trong cây VÀ/HOẶC đó chính là khái niệm giá tối ưu của cây lời giải với gốc là đỉnh n đó cho. Đối với đỉnh n V, giá của n được tính phụ thuộc vào quy ước chọn giá chung của đồ thị. Có 2 loại giá: giá cực đại (max) và giá tổng cộng (). Định nghĩa giá tối ưu của cây lời giải có gốc n như sau: - Nếu n là đỉnh kết thúc thỡ h(n) = 0 - Nếu n không phải là đỉnh kết thúc và n là đỉnh hoặc cú tập T(n) = {n1,. . .,nk} khỏc rỗng thỡ h(n) = min(c(n,ni)+h(ni)). - Nếu n không phải là đỉnh kết thúc và n là đỉnh và cú tập T(n) = {n1,. . .,nk} khỏc rỗng thỡ : k + Đối với giỏ tổng cộng h(n)  (c(n, ni ) h(ni )) i 1 + Đối với giá cực đại h(n) (c(n, ni ) h(ni )) 112
- h(n) không xác định đối với những đỉnh không giải được. Tương tự như trong không gian trạng thái ta xác đinh ước lượng của h là h0 tại các đỉnh không phải là đỉnh không giải được Cây lời giải được xây dựng dần dần trong quá trỡnh mở rộng cõy lựa chọn, tại mỗi thời điểm các nút lá của nó thuộc một trong ba dạng sau: - Các đỉnh kết thúc. - Các đỉnh lá không phải là đỉnh kết thúc. - Các đỉnh chưa được xử lý. Trong cõy tỡm kiếm, ở mỗi bước có thể chứa một tập các cây con có gốc n0 sao cho chúng có thể trở thành phần trên của cây lời giải đầy đủ (cũng giống như các đường đi từ đỉnh n0 đến các đỉnh trong danh sách MO trong giải thuật tỡm kiếm trờn đồ thị biểu diễn bài toán trong khụng gian trạng thỏi ). Ta gọi cỏc cõy này là cõy lời giải tiềm tàng gốc n0. Như vậy bài toán tỡm kiếm cõy lời giải cực tiểu cú thể đưa về hai bài toán con: Bài toỏn 1. Xác định ước lượng h0(n) 1) n là đỉnh lá - Nếu n là đỉnh kết túc thỡ h0(n) = 0 - Nếu n không phải là đỉnh kết thúc thỡ h0(n) không xác đinh (có thể gán giá trị ) - Nếu n chưa được xử lý thỡ h0(n) nhận một giá trị ước lưọng dựa trên thông tin về bài toán (thưũng tham khảo ý kiến chuyờn gia) 2) n không phải là đỉnh lá, T(n) = {n1, ,nk} 0 - Nếu n là đỉnh Hoặc thỡ h (n) = min(c(n,ni)+h(ni)) - Nếu n là đỉnh Và thỡ 113
k 0 0 - Đối với giá tổng cộng h (n) (c(n, ni ) h (n i )) i 1 0 0 - Đối với giá cực đại h (n) = Max(c(n,ni)+h (ni)) Bài toỏn 2. Xõy dựng cõy lời giải tiềm tàng G’ mụ tả quỏ trỡnh chuyển bài toỏn n0 về bài toán n. Gọi G’ = (V’, E’) là đồ thị con của G với tập đỉnh V” xác định như sau: - n0 V’ - Với mỗi n V’ có các đỉnh con n1, , nk. Nếu n là đỉnh hoặc 0 thỡ chọn đỉnh con ni vào V’ sao cho c(n,ni) + h (ni) nhỏ nhất và khonggd(ni) = false. Nếu n là đỉnh và thỡ chọn tất cả cỏc đỉnh ni vào V’ nếu khonggd(ni) = false với mọi i. Thuật toỏn. Input: Cõy và hoặc G = (V,E) với gốc n0. Giá trị ước lương ban đầu h0. TậP ĐỉNH KếT THÚC. c: E R+ và laọi chi phí (tổng công hoặc cực đại) Output: Cõy lời giải tối ưu. Method: push(MO,n0); while MO <> null do begin Xõy dựng cõy tiềm tàng G’; 114
n:= pop(MO Lỏ(G’); Push(DONG,n); if n là đỉnh kết thúc then begin if giaiduoc(n0) then exit; { Cõy lời giải là G’} for k MO do if giaiduoc(k) then MO := MO - {k}; end else if T(n) <> null then for m T(n) do begin push(MO,m); Tớnh lại h0(m) end else if khonggd(n) then begin if khonggd(n0) then exit; 115
for k MO do if khonggd(k) then MO:= MO - {k}; for m DONG do Tớnh lại h0(m) end; writeln(‘khong co loi giai’); end; 4. Cõy tỡm kiếm và cỏc đấu thủ. TRONG NHIềU TRŨ CHƠI TRÊN MÁY TÍNH CÓ THể SINH RA CÁC CÂY ứNG VớI CÁC NƯớC ĐI CủA ĐấU THủ. ĐặC THÙ CủA LOạI TRŨ CHƠI NÀY LÀ CHÚNG THể HIệN Sụ LUÂN PHIÊN GIữA HAI ĐấU THủ. VIệC CHọN CÁC NƯớC ĐI CHO MỗI ĐấU THủ TƯƠNG ứNG VớI VIệC TỡM KIếM CÕY. Để QUYếT ĐịNH MộT TRONG NHữNG LựA CHọN CÓ THể ĐƯợC, NGƯờI TA PHảI NHớ NHIềU TỡNH HUốNG CủA BÀI TOỏN. TUY NHIờN KHụNG THể LƯU TRữ QUÁ NHIềU THụNG TIN VÀ CŨNG KHụNG Xử LÝ TấT Cả TRạNG THỏI CủA BÀI TOỏN ĐƯợC. DO VậY NGƯờI TA CÓ THể DÙNG MộT CHIếN THUậT PHÙ HợP, CHỉ QUYếT ĐịNH TRÊN TậP TỡNH HUốNG HạN CHế. 4.1. Thủ tục minimax. XộT TRŨ CHƠI VớI HAI ĐấU THủ MAX VÀ MIN, MAX TỡM CỏCH LÀM CựC ĐạI GIÁ TRị HÀM ƯớC LƯợNG THÔNG QUA VIệC XÁC ĐịNH GÁ TRị HÀM ƯớC LƯợNG ở MỗI NƯớC ĐI CÓ THể VÀ CHọN NƯớC ĐI TƯƠNG ứNG VớI GIÁ TRị LớN NHấT, TIếP THEO ĐÓ ĐốI THủ MIN TỡM CỏCH LÀM CựC TIểU GIỏ TRị ƯớC LƯợNG NÀY. 116
Diễn đạt theo ngôn ngữ đồ thị Và/Hoặc, Mỗi đỉnh tương ứng với nước đi của Max, giá trị của đỉnh này sẽ lấy giá trị cực đại của các giá trị của các đỉnh con và đỉnh này quy ước gọi là đỉnh Hoặc. Một đỉnh tương ứng với nước đi của Min sẽ lấy giá trị cực tiểu trong số các giá trị đối với các đỉnh con của nó và đỉnh này quy ước gọi là đỉnh loại Và. Vớ dụ. Trũ chơi caro trên bảng ô vuông. Đấu thủ Max đặt các dấu X, đấu thủ Min đặt dấu O. Ta xét ước lượng c(p) đối với mỗi thế cờ p như sau: c(p) = (số dũng, số cột, số đường chéo cũn mở đới với Max) – (số dũng, số cột, số đường chéo cũn mở đối với min) Giả sử ta hạn chế kích thước 3x3 và ở mỗi nước đi, các đấu thủ tính trước hai nước. Nếu đấu thủ Max đi trước độc giả có thể kiểm tra, nước đi đầu tiên của Max sẽ là: X 4.2. Thủ tục Alpha – Beta Cỏc giỏ trị ước lượng phát sinh tương ứng với các đỉnh Và, Hoặc được gọi là các -giỏ trị và -giá trị tương ứng. Thủ tục alpha-beta bắt đầu từ nút gốc với giá trị alpha là - và beta là + . Thủ tục alpha-beta gọi đệ quy với dóy số giữa alpha và beta. Để thực hiện tỡm kiếm minimax bằng thủ tục alpha – beta, cú cỏc bước sau: 1) Nếu mức của cõy là gốc, lấy giỏ trị alpha là - và gia trị beta là + . 2) Nếu đó đến bước kết thúc tỡm kiếm, tớnh giỏ trị hàm ước lượng của vị trí hiện tại cho đấu thủ tương ứng. Cho ra kết quả. 3) Nếu mức ứng với đấu thủ min: 117
i) Cho đến khi các nút con được kiểm tra bằng thủ tục alpha – beta hoặc cho đến khi alpha >= beta, thực hiện các bước sau: + Dựng thủ tục alpha – beta với cỏc giỏ trị alpha – beta hiện cú trờn cỏc nỳt con. Ghi lại giỏ trị do thủ tục đưa ra. + So sánh giá trị thu được với beta, nếu giá trị thu được nhỏ hơn beta thỡ cho beta nhận giỏ trị này. ii) Cho ra giỏ trị beta. 4) Ngược lại, mức này ứng với đấu thủ beta, thực hiện: i) Cho đến khi các nút con được kiểm tra bằng thủ tục alpha – beta hoặc cho đến khi alpha >= beta, thực hiện các bước sau: + Dùng thủ tục alpha – beta với các giá trị alpha – beta hiện có trên các nút con. Ghi lại giá trị do thủ tục đưa ra. + So sánh giá trị thu được với alpha, nếu giá trị thu được lớn hơn alpha thỡ cho alpha nhận giỏ trị này. ii) Cho ra giỏ trị alpha. Chương 4 BIỂU DIỄN BÀI TOÁN BẰNG LOGIC VÀ CÁC PHƯƠNG PHÁP CHỨNG MINH Như ta đó biết, khụng thể cú phương phỏp giải quyết vấn đề tổng quỏt cho mọi bài toỏn. Cú thể phương phỏp này phự hợp cho bài toỏn này, nhưng lại khụng phự hợp cho lớp bài toỏn khỏc. Điều này cú nghĩa là khi núi tới một bài 118
toỏn, ta phải chỳ ý đến phương phỏp biểu diễn nú cựng với cỏc phương phỏp tỡm kiếm trong khụng gian bài toỏn nhận được. 1. Biểu diễn bài toỏn nhờ khụng gian trạng thỏi (cú cỏc chiến lược tỡm kiếm trờn đồ thị biểu diễn vấn đề) 2. Quy về cỏc bài toỏn con 3. Biểu diễn vấn đề nhờ logic hỡnh thức (cú cỏc phương phỏp suy diễn logic) và trong phần này sẽ trỡnh bày phương pháp biểu diễn vấn đề nhờ logic hỡnh thức và các phương pháp giải quyết vấn đề trờn cỏch biểu diễn này. Logic hỡnh thức thường dùng để thu gọn quỏ trỡnh tỡm kiếm lời giải. Trước khi giải quyết vấn đề, nhờ phõn tớch logic, cú thể chứng tỏ rằng một bài toỏn nào đú cú thể giải được hay khụng?. Ngoài ra, cỏc kết luận logic rất cần ngay cả trong cỏch tiếp cận dựa trờn khụng gian trạng thỏi và quy bài toỏn về bài toỏn con. Chẳng hạn, trong cỏc phương phỏp dựa trờn khụng gian trạng thỏi, cỏc kết luận logic dựng để kiểm tra một trạng thỏi nào đú cú phải là trạng thỏi đớch hay khụng?, Ngoài ra, logic hỡnh thức cú thể được sử dụng để giải quyết những bài toỏn chứng minh logic, chẳng hạn như chứng minh một khẳng định nào đú là đỳng khi biết những tiền đề ban đầu và cỏc luật suy diễn. Đõy là một dạng quen thuộc nhất và được cỏc chuyờn gia TTNT quan tõm ngay từ đầu. Vớ Dụ Ta cú thể dựng cỏc biểu thức logic để mụ tả mối quan hệ của cỏc thành phần trong 1 tam giỏc như sau: 1) a  b  c p 2) b  p  c a 3) a  p  c b 119
4) a  b  p c 5) S  c hc 6) a  b  C c 7) a  b  C S 8) a  b  c  p S 9) S  hc c (Trong đó: a, b, c là ký hiệu cỏc cạnh, A, B, C là ký hiệu cỏc gúc tương ứng, p là ký hiệu nữa chu vi, và hc là đường cao xuất phát từ đỉnh C của tam giác) Giả sử ta biết cỏc cạnh a, b và một gúc C. Ta cú thể cú kết luận về đường cao hc khụng? 1. BI ỂU DI ỄN VẤN ĐỀ NHỜ LOGIC HèNH THỨC 1.1. Logic mệnh đề Đây là kiểu biểu diễn tri thức đơn giản nhất và gần gũi nhất đối với chúng ta. a) Mệnh đề là một khẳng định, một phát biểu mà giá trị của nó chỉ có thể hoặc là đúng hoặc là sai. Vớ dụ phát biểu "1+1=2" (có giá trị đúng) phỏt biểu "Trời mưa" (Giỏ trị của mệnh đề khụng chỉ phụ thuộc vào bản thõn mệnh đề đú. Cú những mệnh đề mà giỏ trị của nú luụn đỳng hoặc sai bất chấp thời gian nhưng cũng cú những mệnh đề mà giỏ trị của nú lại phụ thuộc vào thời gian, khụng gian và nhiều yếu tố khỏc quan khỏc. Chẳng hạn như mệnh đề : "Con người khụng thể nhảy cao hơn 5m với chõn trần" là đỳng khi ở trỏi đất , cũn ở những hành tinh cú lực hấp dẫn yếu thỡ cú thể sai.) b) Biểu thức logic - Ta ký hiệu mệnh đề bằng những chữ cái la tinh như a, b, c, và cỏc ký hiệu này được gọi là biến mệnh đề 120
- Biểu thức logic được định nghĩa đệ quy như sau: Cỏc hằng logic (True, False) và cỏc biến mệnh đề là cỏc biểu thức logic Cỏc biểu thức logic kết hợp với cỏc toỏn tử logic (phộp tuyển (), phộp hội ( ), phủ định ( , ~, ), phộp kộo theo ( , ), phộp tương đương ( , )) là cỏc biểu thức logic. Tức là nếu E và F là cỏc biểu thức logic thỡ E  F, E  F, E F, E  F cũng là cỏc biểu thức logic Thứ tự ưu tiên của các phép toán logic: , , , ,  Vớ Dụ MộT Số BIểU THứC LOGIC: 1) True 2)  p 3) p  (p  r) - Biểu thức logic dạng chuẩn: là biểu thức được xây dựng từ các biến mệnh đề và các phép toán , , . Vớ Dụ P  ( P  R) (Chỳng ta đó từng sử dụng logic mệnh đề trong chương trỡnh rất nhiều lần (như trong cấu trúc lệnh IF THEN ELSE) để biểu diễn các tri thức "cứng" trong máy tính ! ) c) Bảng chõn trị (bảng chõn lý) Dựng để dỏnh giỏ giỏ trị của biểu thức logic. p q p p  q p  q p  p q p  q q T T F T T T T T T F F T F F F F F T T T F T T F 121