Bài giảng môn Trí tuệ nhân tạo | Trường Đại học Kinh Doanh và Công Nghệ Hà Nội

lOMoAR cPSD| 58457166
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KINH DOANH VÀ CÔNG NGHỆ -----------o0o----------- BÀI GIẢNG TRÍ TU N HÂN T O
Giảng viên: ThS. Phan Thành Vinh HÀ NỘI - 2021 lOMoAR cPSD| 58457166
Chương 1 - TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO
1.1. Lịch sử hình thành và phát triển
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. 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. lOMoAR cPSD| 58457166
• 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.
• 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ờ). lOMoAR cPSD| 58457166
• 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.
1.2. Khái niệm về trí tuệ nhân tạo (TTNT)
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 1- Xác định tập đích (goals).
22- 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. lOMoAR cPSD| 58457166
Trí tuệ nhân tạo
Định nghĩa về AI đã có tới tám cuốn sách đề cập. Những định nghĩa đó đưa ra
trên hai nhận định chính:
- Thứ nhất: quan tâm chủ yếu đến quá trình tư duy và lập luận
- Thứ hai: vấn đề ít được quan tâm hơn, đó là hoạt động.
Khái niệm trí tuệ nhân tạo (Artificial Intelligence- viết tắt là AI) được hiểu tuỳ
theo cách nhìn từng người, chưa có định nghĩa nào được thừa nhận chung. Hiểu một
cách đơn giản, trí tuệ nhân tạo là một lĩnh vực của khoa học và công nghệ nhằm làm
cho máy có những khả năng trí tuệ của con người như: biết suy nghĩ và lập luận để
giải quyết vấn đề, biết giao tiếp do hiểu ngôn ngữ và tiếng nói, biết học và tự thích nghi, …
Một số định nghĩa khác nhau về trí tuệ nhân tạo:
Bellman (1978) định nghĩa: trí tuệ nhân tạo là tự động hoá các hoạt động
phù hợp với suy nghĩ con người, chẳng hạn các hoạt động ra quyết định, giải bài toán..
Rich và Knight (1991) cho rằng trí tuệ nhân tạo là lĩnh vực nghiên cứu để
làm cho máy tính làm được những việc mà con người đang làm tốt hơn.
Winston (1992) cho rằng trí tuệ nhân tạo là lĩnh vực nghiên cứu các tính
toán để máy có thể nhận thức, lập luận và tác động.
M.Minsky: Nghiªn cøu nh»m m« pháng b»ng m¸y tÝnh vÒ hµnh vi th«ng minh cña con ngêi
Những định nghĩa về AI được chia thành 4 nhóm:
Hệ thống tư duy như con người
Hệ thống tư duy có lập luận
Hệ thống hoạt động như con người
Hệ thống hoạt động có lập luận 1.3. Lĩnh vực liên quan đến trí tuệ nhân
tạo Tâm lý học nhận thức. lOMoAR cPSD| 58457166 Thần kinh học.
Lý thuyết về hệ thống (cybernetics). Toán Logic và Logic học. Sinh học tiến hoá.
Khoa học về hành vi bầy đàn. Tổ chức học. Thống kê học.
1.4. Một số lĩnh vực ứng dụng của trí tuệ nhân tạo
Các phương pháp tìm kiếm lời giải Hệ chuyên gia
Xử lý ngôn ngữ tự nhiên Lý thuyết nhận dạng
Lập kế hoạch và Người máy (Robot) Máy học
Các mô hình thần kinh (Mạng Neuron và giải thuật di truyền) Một số ứng dụng cụ thể:
Nhận dạng chữ viết
Nhận dạng chữ viết ứng dụng trong lĩnh vực nhận dạng chữ in hoặc chữ viết
tay và lưu thành văn bản điện tử. Ở Việt Nam, phần mềm VnDOCR do Phòng Nhận
dạng & Công nghệ tri thức, Viện Công nghệ Thông tin xây dựng có thể nhận dạng
trực tiếp tài liệu bằng cách quét thông qua máy scanner thành các tệp ảnh, chuyển đổi
thành các tệp có định dạng *.doc, *.xls, *.txt, *.rtf, giúp người sử dụng không phải gõ
lại tài liệu vào máy. Tương tự với phần mềm nhận dạng chữ viết trong thư viện, người
ta cũng có thể dễ dàng chuyển hàng ngàn đầu sách thành văn bản điện tử một cách nhanh chóng.
Nhận dạng tiếng nói
Nhận dạng tiếng nói đóng vai trò quan trọng trong giao tiếp giữa người và máy.
Nó giúp máy móc hiểu và thực hiện các hiệu lệnh của con người. Một ứng dụng trong lOMoAR cPSD| 58457166
lĩnh vực này là hãng sản xuất xe hơi BMW (Đức) đang tiến hành phát triển một công
nghệ mới cho phép các tài xế có thể soạn email, tin nhắn bằng giọng nói trong khi
đang lái xe. Một ứng dụng khác là phần mềm lồng phụ đề vào các chương trình truyền
hình. Đây là một công việc khá buồn tẻ và đòi hỏi phải có những người ghi tốc ký
chuyên nghiệp. Nhờ có những tiến bộ trong công nghệ nhận dạng tiếng nói, các nhà
cung cấp dịch vụ truyền hình gần đây đã gia tăng đáng kể số lượng các chương trình
được lồng phụ đề của họ.
Dịch tự động
Dịch tự động là công việc thực hiện dịch một ngôn ngữ sang một hoặc nhiều
ngôn ngữ khác, không có sự can thiệp của con người trong quá trình dịch. Tuy nhiên,
để làm cho máy hiểu được ngôn ngữ là một trong những vấn đề khó nhất của trí tuệ
nhân tạo. Thí dụ câu: “ông già đi nhanh quá” cũng có nhiều cách hiểu khác nhau: với
cách phân tách từ và cụm từ thành ông già/đi/nhanh quá và ông/già đi/nhanh quá…
thì việc dịch câu kiểu như thế này từ tiếng Việt sang tiếng Anh đòi hỏi máy không
những phải hiểu đúng nghĩa câu tiếng Việt mà còn phải tạo ra được câu tiếng Anh
tương ứng. Các phần mềm dịch tự động hiện nay còn phải tiếp tục nghiên cứu nhiều
hơn nữa để có được những hệ dịch tốt.
Tìm kiếm thông tin
Thông tin trên mạng hàng ngày được gia tăng theo cấp số nhân. Việc tìm kiếm
thông tin mà người dùng quan tâm bây giờ là tìm đúng thông tin mình cần và phải
đáng tin cậy. Theo thống kê, có đến hơn 90% số lượng người Việt Nam lên mạng
internet để thực hiện việc tìm kiếm thông tin. Các máy tìm kiếm (search engine) hiện
nay chủ yếu thực hiện tìm kiếm dựa theo từ khóa. Thí dụ, Google hay Yahoo chỉ phân
tích nội dung một cách đơn giản dựa trên tần suất của từ khoá, thứ hạng của trang và
một số tiêu chí đánh giá khác. Kết quả là rất nhiều tìm kiếm không nhận được câu trả
lời phù hợp, thậm chí bị dẫn tới một liên kết không liên quan gì do thủ thuật đánh lừa
nhằm giới thiệu sản phẩm hoặc lại nhận được quá nhiều tài liệu không phải thứ ta
mong muốn, trong khi đó lại không tìm ra tài liệu cần tìm. lOMoAR cPSD| 58457166
Hiện nay, các nhà nghiên cứu đang cải tiến các công cụ tìm kiếm trực tuyến để
một ngày nào đó, nó có thể hiểu và trả lời cả những câu hỏi cụ thể, thí dụ như “giá
tour du lịch rẻ nhất từ Hà Nội đi Đà Lạt trong ba ngày của tháng này là bao
nhiêu?”...Tuy vậy, thực tế cho đến bây giờ chưa có máy tìm kiếm nào có thể làm hài
lòng người dùng kiểu như vậy.
Khai phá dữ liệu và phát hiện tri thức
Đây là lĩnh vực cho phép xử lý từ rất nhiều dữ liệu khác nhau để phát hiện ra
tri thức mới. Ngoài ra, ứng dụng trong lĩnh vực này cũng cần phải biết trả lời câu hỏi
của người sử dụng chúng từ việc tổng hợp dữ liệu thay vì máy móc chỉ đáp trả những
gì có sẵn trong bộ nhớ. Thực tế để làm được điều này rất khó, nó gần như là mô phỏng
quá trình học tập, khám phá khoa học của con người. Ngoài ra, dữ liệu thường có số
lượng rất lớn, với nhiều kiểu (số, văn bản, hình ảnh, âm thanh, video, …) và không
ngừng thay đổi. Để tìm ra tri thức thì các chương trình phải đối mặt với vấn đề độ
phức tạp tính toán,… Đây là lĩnh vực vẫn còn đang trong giai đoạn đầu phát triển.
Lái xe tự động
Theo Sebastian Thrun, Giáo sư ngành máy tính và kỹ thuật điện của Đại học
Carnegie Mellon: ưu điểm lớn nhất của xe tự lái là khả năng loại bỏ sai sót của con
người - nguyên nhân dẫn đến 95% số vụ tử vong mỗi năm tại Mỹ do tai nạn giao
thông. “Chúng tôi có thể giảm bớt 50% số vụ tai nạn do nguyên nhân này,” ông
Sebastian Thrun khẳng định.
Chế tạo được ôtô tự lái và an toàn cao cũng là một mục tiêu được Cục nghiên
cứu các dự án công nghệ cao Bộ quốc phòng Mỹ DARPA (Defense Advanced
Research Projects Agency) khởi xướng và hỗ trợ dưới dạng một cuộc thi mang tên
“thách thức lớn của DARPA” (DARPA grand challenge).
Chúng ta hy vọng sẽ đến một ngày, những chiếc ôtô chạy trên đường không cần
người lái. Chỉ nói nơi muốn đến, xe sẽ đưa ta đi và đi an toàn. lOMoAR cPSD| 58457166 Robot
Nhiều đề án nghiên cứu về robot thông minh và các lĩnh vực liên quan được
ứng dụng trong đời sống. Các đề án này hướng đến các sáng tạo công nghệ có nhiều
ý nghĩa trong văn hóa, xã hội và công nghiệp, đòi hỏi phải tích hợp nhiều công nghệ,
như nguyên lý các tác tử, biểu diễn tri thức về không gian, nhận biết chiến lược, lập
luận thời gian thực, nhận dạng và xử lý các chuỗi hình ảnh liên tục trong thời gian
thực, … Một trong những ứng dụng đó là đề án RoboCup: tổ chức thi đấu bóng đá
giữa các đội robot. Mục tiêu hướng đến của đề án này là đến năm 2050, sẽ chế tạo
được một đội robot có thể thắng đội bóng đá vô địch thế giới.
Ứng dụng quan trọng khác của lĩnh vực này là chế tạo robot đối phó và dò tìm
nạn nhân trong các thảm họa. Trong sự cố hư hỏng tại nhà máy điện hạt nhân xảy ra
sau trận động đất và sóng thần ngày 11 tháng 3 ở Nhật vừa qua, người ta gửi robot có
tên Quince để hoạt động tại những khu vực khó tiếp cận do độ phóng xạ cao của nhà
máy Fukushima. Được điều khiển từ xa, Quince có thể làm việc trong nhiều giờ đồng
hồ để chụp hình và đo độ phóng xạ trong những tòa nhà bị lây nhiễm chất phóng xạ,
nơi mà các kỹ thuật viên không thể vào bên trong.
1.5. Những vấn đề cốt lõi của TTNT
Biểu diễn (representation).
Lập luận (reasoning). Học (learning).
Tương tác (interaction). lOMoAR cPSD| 58457166
Chương 2 KHÔNG GIAN TRẠNG THÁI VÀ CÁC PHƯƠNG PHÁP TÌM KIẾM
2.1. Thuật giải heuristics 2.1.1. Khái niệm
Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải
bài toán với các đặc tính sau:
Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)
Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng
đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.
Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy
nghĩ và hành động của con người.
Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta
thường dựa vào một số nguyên lý cơ bản như sau:
Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi
không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc
thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn
cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng
bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.
Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý
của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.
Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta
thường dùng các hàm Heuristic. Đó là các hàm đánh già thô, giá trị của hàm phụ lOMoAR cPSD| 58457166
thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể
chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.
2.1.2. Bài toán hành trình ngắn nhất - ứng dụng nguyên lý tham lam (Greedy)
Bài toán: Hãy tìm một hành trình cho một người giao hàng đi qua n điểm khác
nhau, mỗi điểm đi qua một lần và trở về điểm xuất phát sao cho tổng chiều dài đoạn
đường cần đi là ngắn nhất. Giả sử rằng có con đường nối trực tiếp từ giữa hai điểm bất kỳ.
Tất nhiên ta có thể giải bài toán này bằng cách liệt kê tất cả con đường có thể đi,
tính chiều dài của mỗi con đường đó rồi tìm con đường có chiều dài ngắn nhất. Tuy
nhiên, cách giải này lại có độ phức tạp 0(n!) (một hành trình là một hoán vị của n
điểm, do đó, tổng số hành trình là số lượng hoán vị của một tập n phần tử là n!). Do
đó, khi số đại lý tăng thì số con đường phải xét sẽ tăng lên rất nhanh.
Một cách giải đơn giản hơn nhiều và thường cho kết quả tương đối tốt là dùng
một thuật giải Heuristic ứng dụng nguyên lý Greedy. Tư tưởng của thuật giải như sau:
Từ điểm khởi đầu, ta liệt kê tất cả quãng đường từ điểm xuất phát cho đến n
đại lý rồi chọn đi theo con đường ngắn nhất.
Khi đã đi đến một đại lý, chọn đi đến đại lý kế tiếp cũng theo nguyên tắc trên.
Nghĩa là liệt kê tất cả con đường từ đại lý ta đang đứng đến những đại lý chưa
đi đến. Chọn con đường ngắn nhất. Lặp lại quá trình này cho đến lúc không còn đại lý nào để đi.
Bạn có thể quan sát hình sau để thấy được quá trình chọn lựa. Theo nguyên lý
Greedy, ta lấy tiêu chuẩn hành trình ngắn nhất của bài toán làm tiêu chuẩn cho chọn
lựa cục bộ. Ta hy vọng rằng, khi đi trên n đoạn đường ngắn nhất thì cuối cùng ta sẽ
có một hành trình ngắn nhất. Điều này không phải lúc nào cũng đúng. Với điều kiện lOMoAR cPSD| 58457166
trong hình tiếp theo thì thuật giải cho chúng ta một hành trình có chiều dài là 14 trong
khi hành trình tối ưu là 13. Kết quả của thuật giải Heuristic trong trường hợp này chỉ
lệch 1 đơn vị so với kết quả tối ưu. Trong khi đó, độ phức tạp của thuật giải Heuristic này chỉ là 0(n2).
Hình : Giải bài toán sử dụng nguyên lý Greedy
Tất nhiên, thuật giải theo kiểu Heuristic đôi lúc lại đưa ra kết quả không tốt, thậm chí
rất tệ như trường hợp ở hình sau. lOMoAR cPSD| 58457166
2.1.3. Bài toán phân việc - ứng dụng của nguyên lý thứ tự
Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2, … Jm. Công ty
có n máy gia công lần lượt là P1, P2, … Pn. Mọi chi tiết đều có thể được gia công trên
bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việ sẽ tiếp tục
cho đến lúc hoàn thành, không thể bị cắt ngang. Để gia công một việc J1 trên một máy
bất kỳ ta cần dùng một thời gian tương ứng là t1. Nhiệm vụ của công ty là phải làm
sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất.
Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 công việc với
thời gian là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. ta có một phương án phân công (L) như hình sau:
Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5
trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên máy P3 ta gia lOMoAR cPSD| 58457166
công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu
tiên mình … Sơ đồ phân việc theo hình ở trên được gọi là lược đồ GANTT. Theo lược
đồ này, ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách
cảm tính ta thấy rằng phương án (L) vừa thực hiện là một phương án không tốt. Các
máy P1 và P2 có quá nhiều thời gian rãnh.
Thuật toán tìm phương án tối ưu L0 cho bài toán này theo kiểu vét cạn có độ
phức tạp cỡ O(mn) (với m là số máy và n là số công việc). Bây giờ ta xét đến một
thuật giải Heuristic rất đơn giản (độ phức tạp O(n)) để giải bài toán này.
Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.
Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất.
Với tư tưởng như vậy, ta sẽ có một phương án L* như sau:
Rõ ràng phương án L* vừa thực hiện cũng chính là phương án tối ưu của trường
hợp này vì thời gian hoàn thành là 8, đúng bằng thời gian của công việc J3. Ta hy vọng
rằng một giải Heuristic đơn giản như vậy sẽ là một thuật giải tối ưu. Nhưng tiếc thay,
ta dễ dàng đưa ra được một trường hợp mà thuật giải Heuristic không đưa ra được kết quả tối ưu. lOMoAR cPSD| 58457166
Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra
và T0 là thời gian tối ưu thì người ta đã chứng minh được rằng , M là số máy
Với kết quả này, ta có thể xác lập được sai số mà chúng ta phải gánh chịu nếu
dùng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn với số máy là 2 (M=2) ta có
, và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công
thức này, số máy càng lớn thì sai số càng lớn.
Trong trường hợp M lớn thì tỷ số 1/M xem như bằng 0 . Như vậy, sai số tối đa
mà ta phải chịu là T*  4/3 T0, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra
được những trường hợp mà sai số đúng bằng giá trị cực đại, dù trong trường hợp xấu
nhất. Thuật giải Heuristic trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt.
2.2. Khái niệm về không gian trạng thái
4 Khô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. lOMoAR cPSD| 58457166
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ử
2.3. Biểu diễn không gian 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).
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. 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:
4 T = { (x,y) / 0 <= x <= m; 0 <= y <= n } 5 S = (0,0)
6 G = { (x,k) hoặc (k,y) / 0 <= x <= m; 0 <= y <= n}
7 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<= aij <= 8 và aij <> akl với i<> j hoặc k <> 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} lOMoAR cPSD| 58457166
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.
Ví dụ 4. Không gian trạng thái triển khai trong Tic-tac-toe
2.4. Các chiến lược tìm kiếm mù
2.4.1. Tìm kiếếm theo chiếuề rộng (BFS): Breadth-first search a.Tư tưởng
Xuất từ một đỉnh v bất kỳ của đồ thị G, chúng ta thực hiện như sau:
Bước 1: đánh dấu đã duyệt cho một đỉnh v bất kỳ.
Bước 2: chọn đỉnh v đã được duyệt nhưng có đỉnh kề chưa được duyệt. Việc chọn đỉnh
v được xét ưu tiên cho các đỉnh được đánh dấu duyệt sớm. Bước 3: thực hiện đánh
dấu đã duyệt với tất cả các đỉnh w kề với v, Bước 4: làm lại bước 2 cho đến khi tất cả
các đỉnh được duyệt. lOMoAR cPSD| 58457166 b. Thuật toán procedure BFS(v)
(* tìm kiếm theo chiều rộng bắt đầu từ đỉnh v, các biến Chuaxet, Ke là biến cục bộ*) Begin QUEUE: = ;
QUEUE v;( * ket qua nap vao queue*) Chuaxet[v] := false ; While QUEUE < > do
Begin p QUEUE :; (* lay phan tu QUEUE :*) Tham_dinh(p) ; For u ke(v) do If Chuaxet[u] them Begin QUEUE u; Chuaxet[u]:=false; End; End; End;
Khi đó, tìm kiếm theo chiều rộng trên đồ thị được thực hiện nhờ thuật toán sau: Begin ( * Initialization*)
For f V do Chuaxet[v] :=true ; For v V do lOMoAR cPSD| 58457166 If Chuaxet[v] then BFS(v) ; End; c. Ví dụ 1
Thực hiện duyệt đồ thị theo chiều rộng trên đồ thị G dưới đây: Bảng duyệt Ví dụ 2 Bảng duyệt
2.4.1. Tìm kiếm theo chiều sâu (DFS): Depth – First Search a. Tư tưởng
Xuất từ một đỉnh v bất kỳ của đồ thị G, chúng ta thực hiện như sau:
Bước 1: đánh dấu v đã được duyệt. lOMoAR cPSD| 58457166
Bước 2: thực hiện đánh dấu đã duyệt với mỗi đỉnh w chưa duyệt kề với v, Bước
3: làm lại bước 2 cho đến khi tất cả các đỉnh được duyệt.
b. Thuật toánprocedure DFS(v)
(* tìm kiếm theo chiều sâu bắt đầu từ đỉnh v, các biến
Chuaxet, Ke là biến toàn cục*) Begin Tham_dinh(v); Chuaxet[v]:=false; For u Ke(v) do If Chuaxet[u] then DFS(u) ; End;(*dinh v da duyet xong*)
Khi đó, tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán sau: Begin ( * Initialization*)
For v V do Chuaxet[v] :=true ; For v V do If Chuaxet[v] then DFS(v) ; End; c. Ví dụ
Thực hiện duyệt đồ thị theo chiều sâu trên đồ thị G dưới đây:
Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm
kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng
các đỉnh là: A, B, D, F, E ,C, G.
Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa
được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D. Từ
D không thể tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm F, từ F đến thăm