Giáo trình Trí tuệ nhân tạo (Phần 1)

ĐẠI HỌC HUẾ 
TRƯỜNG ĐẠI HỌC KHOA HỌC 
Giáo trình 
TRÍ TUỆ NHÂN TẠO 
Huế, 2004 
Lời nói đầu 
Trong các năm qua, nhiều tài liệu của ngành công nghệ thông tin đã được giới 
thiệu nhiều cho các cán bộ nghiên cứu, ứng dụng và sinh viên ở bậc đại học. 
Tuy nhiên các giáo trình của ngành học này chưa đáp ứng dược nhu cầu của 
sinh viên các trường đại học, đặc biệt đối với sinh viên khu vực miền Trung. 
Vì vậy, chúng tôi biên soạn giáo trình “Trí tuệ nhân tạo”, một môn cơ sở 
chuyên ngành trong chương trình đào tạo Cử nhân Tin học, ngoài mục đích 
xây dựng nhiều giáo trình trên một khung chương trình đào tạo, mà còn giúp 
cho sinh viên có tài liệu học tập phù hợp với hoàn cảnh thực tế của Đại học 
Huế. 
Trong cuốn sách này, sinh viên được làm quen với một số kiến thức cơ bản 
nhất về các phương pháp tìm kiếm lời giải và các phương pháp xử lý tri thức. 
Ngoài ra, cuốn sách cũng giới thiệu một số chương trình cài đặt, nhằm giúp 
sinh viên có thể hiểu một cách tường tận các giải thuật, đồng thời tin tưởng 
rằng các giải thuật này có thể áp dung thực tế và cài đặt được trên máy tính 
một cách dễ dàng. 
Các nội dung trình bày trong cuốn sách đã từng được giảng cho sinh viên 
ngành Công nghệ Thông tin tại Đại học Huế trong những năm vừa qua. 
Cuốn sách ra đời dưới sự giúp đỡ về mặt vật chất cũng như tinh thần của Đại 
học Huế, Trường Đại học Khoa học và đặc biệt là Ban chủ nhiệm Khoa Công 
nghệ Thông tin và các đồng nghiệp thuộc Bộ môn Khoa học Máy tính. Chúng 
tôi xin gửi tới họ lòng biết ơn. Xin chân thành cám ơn các bạn bè đã cổ cũ và 
gíup cho cuốn sách sớm được hoàn thành. 
Mặc dù đã hết sức cố gắng, tuy nhiên cuốn sách cũng không tránh khỏi những 
thiếu sót. Chúng tôi rất mong được sự góp ý của các độc giả, đặc biệt đối với 
các đồng nghiệp và sinh viên để cuốn sách ngày càng hoàn thiện. 
 Huế, tháng 7 năm 2004 
 Tác giả 
Tài liệu tham khảo 
1. Bạch Hưng Khang, Hoàng Kiếm 
Trí tuệ nhân tạo: Các phương pháp và ứng dụng. Nhà xuất bản Khoa học 
và Kỹ thuật, 1989. 
2. Đinh Mạnh Tường 
Giáo trình Trí tuệ nhân tạo, Đại học Quốc gia Hà nội. 
3. Nguyễn Thanh Thuỷ 
Trí tuệ nhân tạo: Các phương pháp giải quyết vấn đề và kỹ thuật xử lý tri 
thức. Nhà xuất bản Giáo dục, 1996. 
4. N. Nilson 
Artificial Intelligence. Ed. McGrawhill, 1971 
5. Patrick Henry Winston 
Artificial Intelligence. Ed. Addison Wesley, 1992. 
. 
Mục lục 
Chương 0. Mở đầu 2 
1. Tổng quan về Khoa học Trí ruệ nhân tạo 2 
2. Lịch sử phát triển của Trí tuệ nhân tạo 5 
3. Một số vấn đề Trí tuệ nhân tạo quan tâm 8 
4. Các khái niêm cơ bản 10 
Chương 1. Biểu diễn bài toán trong không gian trạng thái 12 
1. Đặt vấn đề 12 
2. Mô tả trạng thái 12 
3. Toán tử chuyển trạng thái 14 
4. Không gian trạng thái của bài toán 17 
5. Biểu diễn không gian trạng thái dưới dạng đồ thị 18 
6. Bài tập 21 
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 23 
1. Phương pháp tìm kiếm theo chiều rộng 23 
2. Phương pháp tìm kiếm theo chiều sâu 30 
3. Phương pháp tìm kiếm sâu dần 34 
4. Phương pháp tìm kiếm tốt nhất đầu tiên 36 
5. Tìm kiếm đường đi có giá thành cực tiểu - Thuật toán AT 39 
6. Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A* 43 
7. Phương pháp tìm kiếm leo đồi 46 
8. Phương pháp sinh và thử 49 
9. Phương pháp thoả mãn ràng buộc 51 
10. Cài đặt một số giải thuật. 53 
11. Bài tập 72 
Chương 3 
Phân rã bài toán – Tìm kiếm lời giải trên đồ thị Và/Hoặc 90 
1. Đặt vấn đề 90 
2. Đồ thị Và/Hoặc 92 
3. Các phương pháp tìm kiếm lời giải trên đồ thị Và/Hoặc 94 
4. Cây tìm kiếm và các đấu thủ 104 
Chương 4. 
Biểu diễn bài toán bằng logic và các phương pháp chứng minh 107 
1. Biểu diễn vấn đề hờ logic hình thức 108 
2. Một số giải thuật chứng minh 130 
3. Ví dụ và bài tập 138 
Chương 5. Tri thức và các phương pháp suy diễn 148 
1. Tri thức và dữ liệu 148 
2. Các dạng mô tả tri thức 149 
3. Suy diễn trên luật sản xuất 152 
Tài liệu tham khảo 163 
  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. 
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 
  3
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. 
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ữ 
  4
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. 
- 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 
  5
độ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ệ 
t ... ,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; 
 kc: word; 
 end; 
Var 
 S, A: array[1..50] of cung; 
 B: array[1..50] of boolean; 
  68
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 
 with S[Top] do 
 begin 
 i:= dau; 
 j:= cuoi; 
 d:= kc; 
 end; 
  69
 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 
 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; 
  70
 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); 
end; 
Procedure Duongdi(i,j: byte); 
Var 
 k,d: byte; 
Begin 
 if Dendich(i,j) then 
 begin 
  71
 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; 
Begin {leo doi} 
 Khoitao; 
 Duongdi(i0,j0); 
end; 
  72
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: 
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 
1 
2
2
3
6
5
4
5
6
8
3
34 
7
0263
2058
503
68307
3704
40
  73
- Phương pháp duyệt rộng 
n t(n) open  close 
1 
2 
3 
6 
4 dich dừng 
2 
1, 3, 6 
2, 4, 5, 6 
2, 3, 5 
1 
2 
3, 6 
6, 4, 5 
4, 5 
1 
1, 2 
1, 2, 3 
1, 2, 3, 6 
Đườ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 
2 
6 
5 
4 dich dừng 
2 
1, 3, 6 
2, 3, 5 
3, 4, 6 
1 
2 
3, 6 
3, 5 
3, 4 
1 
1, 2 
1, 2, 6 
1, 2, 6, 5 
Đườ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 
1 
2 
6 
5 
3 
4 DICH 
dừng 
2 
1, 3, 6 
2, 3, 5 
3, 4, 6 
2, 4, 5, 6 
10 
24 
311, 67 
311, 59 
311, 414 
414 
1 
1, 2 
1, 2, 6 
1, 2, 6, 5 
 1, 2, 6, 5, 3 
Vậy đường đi ngắn nhất: 1 2 6 5 4 với chi phí 14 
  74
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,4) 
(3,0) 
(3,4) 
(3,1) 
(0,3) 
(0,1) 
(3,3) 
(1,0) 
(2,4) 
(0,4), (3,0) 
(0,0), (3,4), (3,1) 
(0,0), (3,4), (0,3) 
(0,4), (3,0) 
(0,1), (3,0), (3,4), 
(0,4) (0,0), (0,4), 
(3,3), (3,0) 
(0,0), (3,1), (0,4), 
(1,0) 
(0,3), (3,0), (2,4) 
(0,0), (3,0), (1,4), 
(0,1) 
(0,0) 
(0,4), (3,0) 
(3,0), (3,4), 
(3,1) 
(3,4), (3,1), 
(0,3) 
(3,1), (0,3) 
(0,3), (0,1) 
(0,1), (3,3) 
(3,3), (1,0) 
(1,0), (2,4) 
(2,4), (1,4), 
(0,0) 
(0,0), (0,4) 
(0,0),(0,4),(3,0) 
(0,0),(0,4),(3,0), (3,4) 
(0,0),(0,4),(3,0), (3,4), (3,1) 
(0,0),(0,4),(3,0), (3,4), (3,1), (0,3) 
(0,0),(0,4),(3,0), (3,4), (3,1), (0,3), 
(0,1) 
(0,0),(0,4),(3,0), (3,4), (3,1), (0,3), 
(0,1), (3,3) 
(0,0),(0,4),(3,0), (3,4), (3,1), (0,3), 
(0,1), (3,3), (1,0) 
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) 
  75
- 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). 
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. 
  76
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. 
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ị. 
  77
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à 
 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 
  78
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 
 + 
 ROADS 
 ROBERT DANGER 
  79
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; 
procedure nhap; 
var 
f: text; 
 s: string[20]; 
  80
 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; 
procedure khoitao; 
var 
i: byte; 
begin 
 for i:=1 to n do 
  81
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 
 if b[k] and (kc(k,j) <= m) then 
 begin 
 c:=c+1; 
 q[c]:=k; 
 b[k]:= false; 
 tr[k]:=j; 
 end; 
  82
 end; 
end; 
procedure inketqua; 
var 
i:byte; 
begin 
 write('duong di ghe dao it nhat nhu sau: '); 
 write(d1); 
 i:=d1; 
 so:=0; 
 while id2 do 
 begin 
 write('-->',tr[i]); 
 so:=so+1; 
 i:=tr[i]; 
 end; 
 writeln; 
 writeln('duong di tren ghe qua ',so-1,' dao'); 
end; 
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) 
  83
 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; 
 dt: word; 
 huong: string[4]; 
procedure nhap; 
var 
f: text; 
 i,j: size; 
begin 
 clrscr; 
  84
 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; 
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; 
  85
 while d<=c do 
 begin 
 k:= qh[d]; 
 l:= qc[d]; 
 d:=d+1; 
 if A[k,l]>=8 then 
 S[k,l]:=A[k,l]-8 
 else 
 if (k<m) and (ph[k+1,l]=0) then 
 begin 
 c:=c+1; 
 qh[c]:=k+1; 
 qc[c]:=1; 
 ph[k+1,l]:=so; 
 end; 
 if A[k,l]>=4 then 
 A[k,l]:=A[k,l]-4 
 else 
 if (l<n) and (ph[k,l+1] = 0) then 
 begin 
 c:=c+1; 
 qh[c]:=k; 
 qc[c]:=l+1; 
 ph[k,l+1]:=so; 
 end; 
 if A[k,l]>=2 then 
 A[k,l]:= A[k,l]-2 
 else 
 if (k>1) and (ph[k-1,l] = 0) then 
  86
 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; 
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); 
  87
 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]; 
 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 
  88
 for j:=1 to n do 
 begin 
 if i< m then 
 if ph[i,j] 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 
 if ph[i,j] ph[i,j+1] then 
 begin 
 tg:= S[ph[i,j]] + S[ph[i,j+1]]; 
 if tg >= max then 
 begin 
 hang:=i; 
 cot:=j; 
 huong:= 'dong'; 
 max:= tg; 
 end; 
 end; 
 end; 
end; 
  89
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; 
 khoitao; 
 demphong; 
 smax; 
 phatuong; 
 inkq; 
END.