Giáo trình trí tuệ nhân tạo
Trí tuệ nhân tạo là môn cơ sở chuyên ngành trong chương trình đào tạo kỹ sư và cử nhân Tin học. Mục đích của môn học này là trang bị cho sinh viên những kiến thức cơ bản nhất về các phương pháp giải quyết vấn đề và các kỹ thuật xử lý tri thức. Trên cơ sở các kiến thức tiếp thu được học sinh có thể đi sâu tìm hiểu về các chuyên đề khác như hệ chuyên gia, hệ hỗ trợ ra quyết định, phần mềm dạy học thông minh......
…………..o0o…………..
GIÁO TRÌNH TRÍ TUỆ NHÂN TẠO
NÓI ĐẦU
Trí tuệ nhân tạo là môn cơ sở chuyên ngành trong chương trình đào tạo kỹ sư
và cử nhân Tin học. Mục đích của môn học này là trang bị cho sinh viên những
kiến thức cơ bản nhất về các phương pháp giải quyết vấn đề và các kỹ thuật xử
lý tri thức. Trên cơ sở các kiến thức tiếp thu được học sinh có thể đi sâu tìm hiểu
về các chuyên đề khác như hệ chuyên gia, hệ hỗ trợ ra quyết định, phần mềm
dạy học thông minh...
Nội dung giáo trình được trình bày thành ba chương:
Chương 1: Nội dung chương này trình bày các khái niệm cơ bản về khoa học
Trí tuệ nhân tạo.
Chương 2: Đây là chương trọng tâm của giáo trình. Ở đây chúng tôi giới
thiệu các phương pháp biểu diễn vấn đề, các kỹ thuật tìm kiếm lời giải.
Chương 3. Trình bày các kỹ thuật biểu diễn tri thức và xử lý tri thức. Vì thời
lượng của môn học quá ít nên trong chương này chúng tôi chỉ trình bày những
nét hết sức cơ bản và không đi sâu vào các vấn đề cụ thể.
Giáo trình này được biên soạn để làm tài liệu giảng dạy cho giáo viên và học
tập cho sinh viên đồng thời là tài liệu tham khảo cho những ai quan tâm đến Trí
tuệ nhân tạo.
Trong quá trình biên soạn tác giả đã nhận được ý kiến đóng góp và động viên
của bạn bè, đồng nghiệp và đặc biệt là các cán bộ có kinh nghiệm trong khoa
CNTT Đại học Vinh và ĐHBK Hà nội về lĩnh vực này. Nhân đây tác giả muốn
bày tỏ lòng biết ơn tới TS Nguyễn Thanh Thuỷ (ĐHBK Hà nội) người đã giúp
đỡ tác giả trong suốt quá trình biên soạn giáo trình này.
Để hoàn thành tập giáo trình này, mặc dù đã cố gắng rất nhiều nhưng tác giả
tin rằng vẫn không tránh khỏi các sai sót và hạn chế. Hy vọng rằng tác giả sẽ
tiếp tục nhận được các ý kiến góp ý quý báu của bạn đọc và đồng nghiệp.
2
Vinh, tháng 7 năm 2000
Tác giả
Chương I
TỔNG QUAN VỀ TÌNH HÌNH NGHIÊN CỨU
VÀ ỨNG DỤNG CỦA TRÍ TUỆ NHÂN TẠO
1.1. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
Những năm gần đây, ta thường gặp các thuật ngữ: Máy tính thông minh, máy
tính thế hệ thứ 5, trí tuệ nhân tạo, hệ chuyên gia... Sự xuất hiện của các ngôn
ngữ lập trình: LISP (List Processing), PROLOG đã mở đường cho việc xây
dựng và áp dụng vào thực tế hàng loạt các chương trình có khả năng xử lý
"thông minh".
Trước đây, thuật ngữ trí tuệ nhân tạo (TTNT) thường được hiểu như là các
máy có khả năng "suy nghĩ", có khả năng cạnh tranh với bộ óc con người.
Ý tưởng về mô hình các máy thông minh đã được đưa ra hàng trăm năm trước
đây, song mãi đến năm 1930, vấn đề này mới được nghiên cứu một cách nghiêm
túc, sau khi Allen Turing công bố các kết quả đầu tiên.
Phát hiện của Turing:
- Xây dựng máy tính dựa trên các phép toán cơ sở của logic như AND, OR,
NOT.
- Máy tính được điều khiển bởi các chương trình lưu ở bộ nhớ trong.
Năm 1956: Chương trình dẫn xuất kết luận trong hệ hình thức được công bố.
Năm 1959: Chương trình chứng minh các định lý hình học phẳng và chương
trình giải quyết bài toán tổng quát GPS (General Problem Solving ) được đưa ra.
Năm 1960: Mcathy đưa ra ngôn ngữ lập trình LISP.
Thuật ngữ TTNT do Marvin Minsky (của MIT- Massachussets Institute of
Technology) đưa ra năm 1961. Đến đây các nghiên cứu về trí tuệ nhân tạo bắt
3
đầu phát triển mạnh. Trong thời gian này, các chương trình tính tích phân, chơi
cờ, chứng minh định lý toán học cũng được công bố.
Năm 1961: Chương trình tính tích phân bất định.
Năm 1963: Các chương trình Heuristics (suy nghiệm, phát hiện), chương trình
chứng minh định lý hình học không gian có tên "Tương tự", chương trình chơi
cờ của Samuel.
Năm 1964: Chương trình giải phương trình đại số sơ cấp, chương trình trợ
giúp ELIZA (phân tích tâm lý).
Năm 1966: Chương trình phân tích và tổng hợp tiếng nói.
Năm 1968: Chương trình nhận dạng hình ảnh, Robot chế tạo dựa theo đồ án
mắt- tay, chương trình học nói.
Hạn chế của giai đoạn này là khả năng của máy tính bị hạn chế về cả bộ nhớ
và thời gian thực hiện. Sang những năm 70, máy tính phát triển đáng kể về chất
(bộ nhớ, tốc độ), song TTNT chưa có thành công đáng kể vì trong quá trình tìm
kiếm lời giải bài toán thường gặp phải sự bùng nổ tổ hợp.
Cuối những năm 70 các nhà nghiên cứu đã đạt được những thành công đáng
kể trong các lĩnh vực:
- Xử lý ngôn ngữ tự nhiên
- Biểu diễn tri thức
- Lý thuyết giải quyết vấn đề
- Hệ chuyên gia.
Năm 1972, ngôn ngữ Prolog ra đời là một sự kiện quan trọng trong sự phát
triển của khoa học TTNT.
Năm 1981, ngôn ngữ Prolog được chọn làm ngôn ngữ cơ sở trong dự án xây
dựng máy tính thế hệ thứ 5 của Nhật. Điều này đã làm thay đổi khá nhiều tình
hình phát triển TTNT ở Mỹ và Châu Âu.
4
Cuối những năm 80, đầu những năm 90 có khá nhiều sản phẩm dân dụng
trình độ cao sử dụng TTNT như: máy giặt, máy ảnh.
Những năm 90, một số lĩnh vực trí tuệ nhân tạo được phát triển mạnh như:
+ Các hệ thống nhận dạng và xử lý hình ảnh
+ Mạng Neuron
+ Kỹ thuật xử lý tri thức, dữ liệu hỗn hợp
+ Hệ hỗ trợ ra quyết định dựa trên tri thức
+ Biểu diễn tri thức và dữ liệu hướng đối tượng
+ Kỹ thuật Multimedia (đa phương tiện), Hypertext (siêu văn bản).
1.2. NHỮNG TIỀN ĐỀ CƠ BẢN CỦA TTNT
Những tiền đề ban đầu cho sự ra đời của TTNT là những nghiên cứu lý thuyết
sâu sắc của các chuyên gia về: Logic hình thức, tâm lý học nhận thức và điều
khiển học. Tuy vậy những tiến bộ trong kỹ thuật vi điện tử cũng là một yếu tố
tạo tiền đề cho sự thành công của các chương trình TTNT.
Những tiền đề hình thành và các hướng nghiên cứu, ứng dụng cơ bản và các
hướng phát triển chính của trí tuệ nhân tạo được thể hiện bởi sơ đồ sau:
Điều khiển
học
Logic hình
Xử lý NN
thức
tự nhiên
Trí tuệ nhân
Tâm lý học Các hệ xử tạo Người
nhận thức lý ký hiệu (Artificial máy
Intelligence)
Xử lý danh Hệ chyên
sách gia
Các kỹ thuật và môi Kỹ thuật vi điện
trường lập trình tử hiện đại
nâng cao
5
Các hệ thông máy
tính phát triển
1.3. CÁC KHÁI NIỆM CƠ BẢN CỦA KHOA HỌC TTNT
1.3.1 Trí tuệ của con người (Human Intelligence)
Hiện nay chưa có định nghĩa thống nhất về trí tuệ con người. Sau đây là một
số định nghĩa được chú ý nhiều nhất:
A.Turing:
"Trí tuệ là những gì có thể đánh giá được thông qua các phép kiểm tra (test)
thông minh".
Từ điển bách khoa toàn thư Webster:
"Trí tuệ là khả năng:
1. Phản ánh một cách thích hợp lại 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.
2. Hiểu rõ những mối liên hệ qua lại giữ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ục đích nào đó".
Các chuyên gia tâm lý học nhận thức chỉ ra rằng hoạt động trí tuệ của con
người bao gồm 4 thao tác:
1. Xác định tập các đích (goals) cần đạt tới.
2. Thu tập sự kiện (facts) và các luật suy diễn (interence) để đạt tới các đích
đặt ra.
3. Thu gọn quá trình suy luận nhằm xác định nhanh chóng tập những luật suy
diễn có thể sử dụng được để đạt tới một đích trung gian nào đó.
6
4. Áp dụng các cơ chế suy diễn cụ thể, dựa trên các thao tác thu gọn quá trình
suy luận và các sự kiện trung gian mới được tạo ra để dẫn dắt từ những sự kiện
ban đầu đi tới những đích đặt ra.
Ví dụ 1.1.
* Thao tác1. Cần xác định cách đi tốt nhất từ nhà tới cơ quan.
* Thao tác2.
+ Các sự kiện: Thời tiết, sức khoẻ, ngày nghỉ hay làm việc, loại phương tiện,
khoảng cách, giá cả từng loại phương tiện, thời gian, tình hình kinh tế, giá cả
nhiên liệu,...
+ Các luật suy diễn: Giả sử ta thu nạp được các luật suy diễn sau:
Luật 1: Nếu hôm đó là ngày nghỉ Thì không phải đi làm
Luật 2: Nếu thời tiết xấu Thì công viên không có người
Luật 3: Nếu thời tiết xấu Thì nên đi đường nhựa
Luật 4: Nếu thời tiết đẹp Thì đi đường tắt
Luật 5: Nếu tình hình chính trị xấu Thì tình hình kinh tế xấu
Luật 6: Nếu giá cả tăng Thì tình hình kinh tế xấu
Luật 7: Nếu thời tiết xấu và đi bằng xe Thì đi bằng xe buýt
Luật 8: Nếu thời tiết đẹp và đi bằng xe Thì đi xe đạp
Luật 9: Nếu đường xa Thì đi bằng xe
Luật 10: Nếu đường gần Thì đi bộ
Luật 11: Nếu đi đường nhựa Thì đi bằng xe.
* Thao tác 3: Giả sử hôm đó thời tiết xấu, khi đó cơ chế thu gọn quá trình suy
luận cho phép chỉ xét các luật liên quan tới thời tiết xấu (luật 2, 3, 7) hoặc chỉ
các luật có liên quan tới đích đặt ra (luật 1, 3, 4, 7, 8, 9, 10, 11).
* Thao tác 4: Chú ý tới các luật thoả mãn điều kiện "thời tiết xấu", chỉ có luật
2, 3. Tuy nhiên chỉ có luật 3 được lưu lại và ta có sự kiện khẳng định mới là "đi
đường nhựa". Sự kiện này được nạp thêm vào tập các sự kiện đã biết. Tiếp tục
7
quá trình, ta đi đến kết luận để đi từ nhà tới cơ quan, nếu thời tiết xấu, nên đi
bằng xe buýt (xem sơ đồ trên).
1.3.2. Trí tuệ máy (Machine Intellgence)
Trí tuệ máy chưa có định nghĩa, song có một số dấu hiệu quan trọng để
đánh giá trí tuệ máy là:
1. Khả năng học.
2. Khả năng mô phỏng các hành vi sáng tạo của con người, nghĩa là có thể
giải quyết một bài toán sáng tạo nào đó giống như một chuyên gia (chương trình
chơi cờ).
3. Khả năng trừu tượng hoá, khái 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 với tình huống mới trong đó gồm có khả năng thu nạp
tri thức và dữ liệu.
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, danh
sách.
7. Khả năng sử dụng các tri thức, Heuristics.
8. Khả năng xử lý các thông tin không đầy đủ, không chính xác.
1.3.3. Vai trò của TTNT trong CNTT
Khoa học TTNT có nhiệm vụ:
- Nghiên cứu các kỹ thuật làm cho máy tính có thể "suy nghĩ một cách thông
minh" .
- 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 nhờ tìm kiếm trong không gian bài toán hay phân rã bài toán con, do vậy nó
chia nhỏ quá trình suy nghĩ này thành những bước cơ bản.
- Tạo nên cách tiếp cận đơn giản và có cấu trúc để xây dựng các chương trình
ra quyết định phức hợp đòi hỏi phải dựa trên những tri thức nhất định.
8
- TTNT làm cho máy tính có khả năng suy nghĩ. Có thể mô phỏng quá trình
học của con người, trên cơ sở đó thu nạp được những thông tin mới phục vụ cho
quá trình suy diễn sau đó.
Sự ra đời và phát triễn của trí tuệ nhân tạo tạo nên những bước nhảy vọt về
chất trong kỹ thuật và kỹ nghệ xử lý thông tin. Nó 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ờ.
Những đặc điểm của công nghệ xử lý thông tin mới dựa trên nền tảng TTNT
bao gồm:
1. Nhờ những công cụ hình thức hoá, các tri thức thủ tục và tri thức mô tả có
thể biểu diễn được trong máy tính, quá trình giải quyết bài toán được tiến hành
hữu hiệu hơn.
2. Các hệ thống TTNT có tính thích nghi cao, mềm dẻo đối với các lớp bài
toán thuộc nhiều lĩnh vực khác nhau.
3. Các hệ thống trí tuệ nhân tạo hoạt động dựa trên tri thức và các Heuristics,
trong khi đó các hệ thống xử lý thông tin truyền thống dựa trên các thuật giải.
4. Việc bảo trì các hệ thống TTNT do các kỹ sư xử lý tri thức đảm nhận, trong
khi đó việc bảo trì các chương trình do các lập trình viên chịu trách nhiệm.
Ta có thể so sánh kỹ thuật lập trình truyền thống và kỹ thuật xử lý ký hiệu
trong TTNT như sau:
Lập trình truyền thống Xử lý ký hiệu
- Định hướng xử lý các dữ liệu - Định hướng xử lý các ký hiệu tượng trưng.
(số, văn bản).
- CSDL được đánh địa chỉ số. - Cơ sở tri thức được cấu trúc theo theo các ký hiệu.
- Xử lý theo thuật toán. - Xử lý theo các thuật giải Heuristic, cơ chế lập luận.
- Xử lý tuần tự hay theo mẻ. - Xử lý theo chế độ tương tác cao (hội thoại ngôn ngữ
tự nhiên).
9
- Không giải thích trong quá - Có thể giải thích hành vi hệ thống trong quá trình
trình thực hiện. thực hiện.
1.3.4. Các kỹ thuật TTNT
Các kỹ thuật TTNT thường thiên về xử lý các ký hiệu tượng trưng, vì vậy nó
thường khá phức tạp khi cài đặt cụ thể. Hơn nữa nó đòi hỏi phải sử dụng những
tri thức chuyên môn thuộc vào các lĩnh vực khác nhau. Những tri thức này có
các đặc điểm sau:
- Khối lượng tri thức cần để giải quyết bài toán có thể rất lớn.
- Khó có thể đặc trưng hoá và biểu diễn tri thức chuyên gia một cách chính
xác.
- Tri thức đối với bài toán thường xuyên bị thay đổi.
Do vậy các đặc tính quan trọng của kỹ thuật TTNT:
- Đạt được mức tổng quát.
- Dễ hiểu đối với các chuyên gia con người cung cấp tri thức cho hệ thống.
- Dễ sửa đổi, dễ hiệu chỉnh lỗi và dễ đưa vào những thay đổi cần thiết.
- Dễ sử dụng trong nhiều tình huống khác nhau, kể cả khi các tri thức không
chính xác và đầy đủ.
- Dễ thu hẹp khả năng cần xét để đi tới lời giải cuối cùng.
Với các yêu cầu trên ta có các phương pháp và kỹ thuật trí tuệ nhân tạo cơ
bản sau:
- Các phương pháp biểu diễn tri thức và kỹ nghệ xử lý tri thức
- Các phương pháp giải quyết vấn đề
- Các phương pháp Heuristics
- Các phương pháp học
- Các ngôn ngữ TTNT.
Ngoài ra, các kỹ thuật của tin học truyền thống như: Xử lý danh sách, đệ quy,
quay lui, sử dụng cú pháp hình thức cũng có liên quan trực tiếp đến TTNT.
10
1.3.5. Các thành phần trong hệ thống TTNT
Mỗi hệ thống TTNH gồm hai thành phần cơ bản sau:
+ Các phương pháp biểu diễn vấn đề, các phương pháp biểu diễn tri thức
+ Các phương pháp tìm kiếm trong không gian bài toán, các chiến lược suy
diễn.
Hai thành phần này có quan hệ chặt chẽ với nhau. Thể hiện ở chỗ việc lựa
chọn phương pháp biểu diễn tri thức sẽ quyết định phương pháp giải quyết vấn
đề tương ứng có thể áp dụng. Ngược lại, phương pháp tìm kiếm sẽ có hiệu quả
nếu phương pháp biểu diễn tri thức thích hợp.
Dựa trên các thành phần của các hệ thống TTNT, có thể chia các hệ thống
TTNT thành các loại sau:
1. Các hệ thống tìm kiếm thông tin, các hệ thống hỏi đáp thông minh cho
phép hội thoại giữa những người sử dụng đầu cuối không chuyên tin, với cơ sở
tri thức và cơ sỡ dữ liệu thông qua ngôn ngữ chuyên ngành gần với ngôn ngữ tự
nhiên.
2. Các hệ thống suy diễn- tính toán cho phép giải quyết những bài toán phức
tạp dựa trên các mô hình toán học và tri thức chuyên gia.
3. Các hệ chuyên gia cho phép sử dụng các tri thức chuyên gia trong các lĩnh
vực tri thức tản mạn.
1.3.6. Các cách tiếp cận trong TTNT
Từ đầu, các công trình nghiên cứu về TTNT được chia thành 2 hướng cơ bản:
+ Hướng phỏng sinh học: Mô phỏng hoàn toàn các hoạt động của bộ não, các
tính chất tâm sinh lý của nó, trên cơ sở đó tái tạo trong máy tính hoặc các thiết bị
kỹ thuật những khía cạnh khác nhau của TTNT.
+ Hướng phỏng vật lý: Định hướng vào các khía cạnh thực hành trong đó máy
tính là công cụ thử nghiệm các chương trình cho phép đạt tới kết quả giống như
hoạt động sáng tạo của con người.
11
Tuy nhiên, trong những năm gần đây hai hướng nghiên cứu này đã xích lại
gần nhau.
Bốn cách tiếp cận khác nhau trong TTNT:
- Tạo lập các mạng thông minh
- Tái tạo quá trình tiến hoá nhân tạo
- Lập trình Heuristics
- Biểu diễn và xử lý tri thức.
Ở đây ta hiểu Mạng thông minh nhân tạo bao gồm một số lượng lớn các phần
tử đơn giản (máy tính hoặc thiết bị vật lý khác) và mối liên hệ giữa chúng.
Chẳng hạn mạng neuron nhân tạo nhằm tái tạo những phương thức tổ chức và
cơ chế hoạt động của các neuron trong bộ não người. Ưu điểm của mạng neuron
là khả năng thích nghi và khả năng học. Khó khăn của nó là khó tạo ra được 1010
neuron như bộ não người.
Tái tạo quá trình tiến hoá nhân tạo là cách tiếp cận hướng tới xây dựng các hệ
thống chương trình có khả năng mô phỏng quá trình tiến hoá tự nhiên thông qua
hai hoạt động cơ bản là đột biến và lựa chọn.
Các nghiên cứu về lập trình Heuristics có những mục đích:
• Giải thích bản chất của trí tuệ tự nhiên
• Sử dụng "trí tuệ máy" để giải quyết các bài toán sáng tạo khó.
Biểu diễn và xử lý tri thức là cách tiếp cận dựa trên những đặc tả chính của
bài toán đặt ra. Cách tiếp cận này thường sử dụng trong các hệ chuyên gia.
1.4. CÁC LĨNH VỰC NGHIÊN CỨU VÀ ỨNG DỤNG CƠ BẢN CỦA TTNT
Có thể phân chia các lĩnh vực nghiên cứu và ứng dụng quan trọng trong
TTNT theo bốn hướng cơ bản sau:
1. Mô hình hoá trên máy tính các chức năng khác nhau trong quá trình sáng
tạo: Các trò chơi, chứng minh định lý tự động, tổng hợp các chương trình, phân
tích và tổng hợp các tác phẩm nghệ thuật,...
12
2. Nâng cao khả năng trí tuệ "bên ngoài" của máy tính, bao gồm các nghiên
cứu cơ bản và ứng dụng, gắn liền với các giao tiếp, hội thoại bằng cách sử dụng
các kỹ thuật tìm kiếm và suy diễn.
3. Nâng cao trí tuệ "bên trong" của máy tính trên cơ sở chế tạo các máy tính
thế hệ mới với các kiến trúc vật lý mới dựa trên các nguyên lý của TTNT.
4. Chế tạo người máy thông minh, có khả năng thực hiện các thao tác phức
tạp, biết" suy nghĩ" và "hành động" để đạt được đích đặt ra.
1.4.1. Các lĩnh vực nghiên cứu cơ bản của TTNT
1. Lý thuyết giải quyết vấn đề và các kỹ thuật suy diễn thông minh
Các phương pháp giải quyết vấn đề bao gồm:
- Phương pháp biểu diễn bài toán trong không gian trạng thái
- Phương pháp quy bài toán về các bài toán con
- Phương pháp GPS
- Phương pháp hình thức sử dụng cách tiếp cận logic.
2. Lý thuyết tìm kiếm Heuristics
Bao gồm các phương pháp và kỹ thuật tìm kiếm, sử dụng các tri thức nảy
sinh từ bản thân bài toán để rút ngắn quá trình giải, nhanh chóng thu được kết
quả.
3. Lý thuyết biểu diễn tri thức và kỹ thuật xử lý tri thức
Bốn phương pháp biểu diễn tri thức:
- Dùng logic mệnh đề, logic vị từ
- Dùng các hệ sản xuất
- Dùng frame
- Dùng mạng ngữ nghĩa.
4. Lý thuyết nhận dạng
Phát triển theo các hướng tiếp cận:
- Lý thuyết thống kê về nhận dạng
13
- Lý thuyết cấu trúc về nhận dạng
- Lý thuyết đại số về nhận dạng
- Lý thuyết Heuristics về nhận dạng.
* Hiện nay, vấn đề nhận dạng thông tin hình ảnh và tiếng nói đang là một
thách thức đối với các chuyên gia TTNT.
* Cách tiếp cận sử dụng mạng Neuron nhân tạo đang có nhiều hứa hẹn.
5. Các ngôn ngữ trí tuệ nhân tạo
- Ngôn ngữ LISP (List Processing) - 1960
- PROLOG (Programinig for Logics) - 1972
- CLIPS - 1980.
1.4.2. Các ứng dụng cơ bản của TTNT
Các ứng dựng cơ bản của TTNT bao gồm các lĩnh vực:
1. Kỹ thuật người máy
2. Các chương trình trò chơi
3. Xử lý ngôn ngữ tự nhiên
4. Các hệ thống xử lý tri thức và dữ liệu tích hợp.
1.4.3. Những nghiên cứu hiện đại xung quanh TTNT
Những năm gần đây các nghiên cứu TTNT tập trung vào các lĩnh vực sau:
- Lập trình logic, xử lý phép phủ định trong lập luận
- Các phương pháp học, thu nạp tri thức
- Giải thuật di truyền
- Mạng neuron
- Các hệ hỗ trợ quyết định dựa trên tri thức.
1.5. NHỮNG VẤN ĐỀ CHƯA ĐƯỢC GIẢI QUYẾT TRONG TTNT
Hai vấn đề thách thức còn mở đối với các nhà nghiên cứu TTNT trong giai
đoạn hiện nay là:
14
1. Trí tuệ nhân tạo có mô phỏng được phần lớn hoạt động của bộ não con
người?
2. Liệu có tồn tại những khía cạnh trí tuệ con người về nguyên tắc là không
mô phỏng được trên máy tính?
Với các thành tựu đạt được cho thấy rằng các dự án xây dựng máy tính có khả
năng suy nghĩ là có tính thực tiễn, song trong nhiều lĩnh vực máy tính còn thua
xa so với hoạt động của hệ thần kinh con người.
1.5.1. Sự khác nhau cơ bản trong hoạt động giữa máy tính và bộ não người
Sự khác nhau cơ bản trong hoạt động giữa máy tính và bộ não người được thể
hiện rõ nét nhất ở các điểm sau:
- Khả năng xử lý song song: Khả năng xử lý song song của bộ não rất lớn,
máy tính chưa thể đạt đến được.
Khả năng diễn giải: Con người có khả năng xem xét cùng một vấn đề theo
nhiều phương pháp khác nhau, để từ đó diễn giải theo cách dể hiểu nhất. Các hệ
thống TTNT tạo không thể mô phỏng được điều này.
- Xử lý các đại lượng rời rạc và liên tục: Bộ não xử lý thông tin liên tục một
cách dễ dàng như là một hoạt động bản năng. Nó dễ dàng kết hợp việc xử lý
thông tin liên tục với thao tác xử lý thông tin rời rạc. Đối với Máy tính, xử lý
thông tin liên tục còn là một thách đố ghê gớm.
- Khả năng học: Đối với con người, khả năng học như là bản năng của bộ
não. Con người có thể tiếp thu các tri thức từ thế giới bên ngoài, có khả năng
học khi thông tin về thế giới xung quanh không đầy đủ, không chính xác, phụ
thuộc vào tình huống. Máy tính chưa có những khả năng này.
- Khả năng tự tổ chức: Khả năng tự tổ chức, điều chỉnh hành vi là điểm nổi
bật trong hoạt động của bộ não con người. Nó cùng với khả năng học tạo nên
khả năng thích nghi làm cho con người có thể hoà nhập với nhiều tình huống
15
khác nhau. Với máy tính, để thực hiện được khả năng này đòi hỏi phải có những
đột biến trong chế tạo phần cứng. Đến nay chưa đáp ứng được.
1.5.2. Những vấn đề đặt ra trong tương lai
1. Nghiên cứu và thử nghiệm mạng neuron, các hệ thống TTNT 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.
2. 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ới
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, thu thập và
xử lý thông tin hình ảnh và tiếng nói.
3. 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 các bài toán phát
biểu không đầy đủ, không chính xác, các bài toán phụ thuộc không gian, thời
gian đòi hỏi xử lý tích hợp các tri thức và dữ liệu
16
Chương II
CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ
2.1. GIẢI QUYẾT VẤN ĐỀ VÀ KHOA HỌC TTNT
Từ đây cho hết giáo trình này các thuật ngữ "vấn đề" và "bài toán" được
dùng tương đương.
Có thể xem lịch sử phát triển của TTNT gắn liền với sự bùng nổ các kỹ thuật
giải quyết vấn đề, từ các kỹ thuật Heuristics đến các kỹ thuật xử lý tri thức (xem
hình vẽ 2.1). Nhiều hoạt động trong thực tiễn của con người (tính toán, quản lý,
trò chơi, giải đáp câu đố,...) đều đòi hỏi sự tham gia của trí tuệ.
Bài toán
Phát biểu bài toán-Xác định phương pháp biểu diễn bài toán
Sản sinh không gian bài toán
Công
Xác định lời nghệ
Đ giải nhờ các lập
Bài toán có thể giải nhờ thuật toán đa thức ngôn ngữ lập trình
truyền
trình
thống
S
Xác định các tri thức đặc biệt để rút gọn không gian tìm kiếm
Xây dựng các phương pháp biểu diễn tri thức và suy diễn
Cài đặt hệ thống, lựa chọn ngôn ngữ, công cụ phù hợp
Các hệ giải quyết vấn đề dựa vào tri thức
Hình 2.1. Những khía cạnh khác nhau của trí tuệ nhân tạo
17
Máy tính trở thành công cụ đắc lực giúp con người trong công việc xử lý
thông tin và giải quyết các nhiệm vụ ở mức độ trí tuệ ngày càng cao. Theo một
nghĩa nào đó các máy tính hiện nay đã được trang bị trí tuệ nhân tạo. Trong một
số lĩnh vực, máy tính vượt quá khả năng của con người. Tuy nhiên, có những bài
toán con người giải quyết đơn giản thì máy tính chưa làm được.
Cốt lõi của mọi hoạt động trí tuệ diễn ra trong máy tính cũng như bộ não con
người là sự vận dụng linh hoạt các kỹ thuật giải quyết vấn đề. Trong chương
này, chúng ta quan tâm đến các phương pháp giải quyết bài toán dựa trên một
cách biểu diễn bằng mô hình hoá bài toán nào đó.
2.2. GIẢI QUYẾT VẤN ĐỀ CỦA CON NGƯỜI
Cách giải quyết vấn đề của con người là mô hình thực tiễn quan trọng để các
chuyên gia TTNT tìm cách mô phỏng lại trên máy tính quá trình giải quyết bài
toán. Có hai bộ phận nghiên cứu quá trình giải quyết vấn đề của con người:
+ Khoa học về nhận thức: Nghiên cứu quá trình tổ chức, lưu trữ, truy nhập,
xử lý và thu nạp tri thức trong bộ não người.
+ Tâm lý học nhận thức và khoa học điều khiển: Tạo ra các mô hình tổ chức
bộ não.
2.2.1. Quá trình xử lý thông tin của con người
Mô hình xử lý thông tin trong bộ não gồm 3 hệ thống con sau:
- Hệ thống cảm nhận (perception subsystem)
- Hệ thống nhận thức (cognitive subsystem)
- Hệ thống hoạt động(action subsystem).
Ta có thể mô tả quá trình xử lý thông tin của con người như sau:
HỆ THỐNG XỬ LÝ THÔNG TIN CỦA CON NGƯỜI
Kích Hệ thống thụ cảm Hệ thống hành động Trả
Hệ thống nhận thức
Cơ Bộ nhớ Bộ nhớ dài hạn Bộ nhớ Cơ quan
thích Bộ nhớ làm việc đệm hành lời
quan đệm
thụ cảm động
Bộ xử lý nhận thức
Hình 2.2. Tổng quan về hệ thống xử lý thông tin của con người
18
2.2.2. Giải quyết vấn đề của con người
Giải quyết vấn đề của con người là một trường hợp riêng của quá trình xử lý
thông tin trong bộ não. Thực chất, đó là việc tìm cách đi từ tình huống ban đầu
nào đó đến đích. Giải quyết vấn đề là một hoạt động đặc biệt của hệ thần kinh
cần tới quá trình suy nghĩ, tìm kiếm trong không gian lời giải bộ phận để đi đến
lời giải cuối cùng.
Tuy nhiên, cần lưu ý rằng không phải mọi hoạt động xử lý thông tin đều là
giải quyết vấn đề.
Các chiến lược giải quyết vấn đề của con người:
+ Ước lượng mức độ phức tạp của vấn đề đặt ra:
- Nếu đơn giản, giải quyết ngay bằng các thao tác cơ sở.
- Nếu phức tạp, các cơ quan não tìm cách hiểu chi tiết nội dung của vấn đề để
mã hoá, tìm phương pháp phù hợp.
+ Nới lỏng một vài ràng buộc của bài toán.
+ Phương pháp chia thành các bài toán con: Từ bài toán phức tạp, con người
chia thành các bài toán nhỏ, ít phức tạp cho đến khi gặp các bài toán sơ cấp, giải
quyết được ngay.
+ Tổng quát hoá bài toán : Chuyển các thông tin bên ngoài thành các kí hiệu
làm cho bài toán dễ giải hơn. Quá trình này tạo ra một mô hình trí tuệ của bài
toán, mô hình này thường được gọi không gian bài toán.
* Không gian bài toán bao gồm:
- Các dạng mẫu kí hiệu, mỗi dạng biểu diễn một trạng thái hay một tình
huống bài toán.
- Các mối liên kết giữa các dạng mẫu ký hiệu, mỗi mối liên kết tương ứng với
các phép biến đổi từ dạng này sang dạng khác.
2.3. PHÂN LOẠI VẤN ĐỀ, CÁC ĐẶC TRƯNG CƠ BẢN CỦA VẤN ĐỀ
Trước khi xem xét việc phân loại vấn đề, ta xét các bài toán sau:
Bài toán 2.1. Bài toán trò chơi n2-1 số (n∈N, n>2).
19
Trong bảng ô vuông n hàng, n cột, mỗi ô chứa 1 số nằm trong phạm vi từ 1
đến n2-1 sao cho không có 2 ô có cùng giá trị. Có một ô trong bảng bị bỏ trống.
Xuất phát từ một cách 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, xuống dưới (nếu có thể ) để đưa về dạng
sau:
1 2 3 1 2 3 4
4 5 6 5 6 7 8
7 8 9 10 11 12
13 14 15
a) b)
Hình 2.3. Hình trạng đích trong trò chơi n2-1 số
a) n=3 b) n= 4
Bài toán 2.2. Bài toán tháp Hà Nội.
Cho 3 cọc 1, 2, 3. Ở cọc 1 ban đầu có n đĩa sắp theo thứ tự nhỏ dần từ dưới
lên trên. Hãy tìm cách chuyển n đĩa đó sang cọc 3 với điều kiện:
- Mỗi lần chỉ chuyển 1 đĩa
- Chỉ sử dụng cọc trung gian 2
- Trong mỗi cọc, ở mỗi bước không cho phép đĩa to nằm trên đĩa nhỏ.
1 2 3 1 2 3
A
A
B
B
C
C
Hình 2.4. Bài toán tháp Hà Nội với n=3
Bài toán 2.3. Đố chữ
Hãy thay các chữ cái bằng các chữ số từ 0 đến 9 sao cho không có 2 chữ cái
được thay bởi cùng 1 số và thoả mãn:
20
