Download miễn phí Giáo trình Thuật toán thuật giải
Danh sách các trạng thái kế tiếp của Ti : danh sách này lưu trữ các trạng thái kế
tiếp Tk của Ti sao cho chi phí đến Tk thông qua Ti từ trạng thái ban đầu là thấp nhất.
Thực chất thì danh sách này có thể được tính ra từ thuộc tính Cha của các trạng thái
được lưu trữ. Tuy nhiên, việc tính toán này có thể mất nhiều thời gian (khi tập OPEN,
CLOSE được mở rộng) nên người ta thường lưu trữ ra một danh sách riêng. Trong
thuật toán sau đây, chúng ta sẽ không đề cập đến việc lưu trữ danh sách này. Sau
khi hiểu rõ thuật toán, bạn đọc có thể dễ dàng điềuchỉnh lại thuật toán để lưu trữ
thêm thuộc tính này.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
chuyển trạng thái đã chọn cho tìm kiếm BFS cục bộ cho đến khi một lượng bộ nhớ M0
lại được dùng hết và trạng thái con mới trong OPEN lại tiếp tục được xem như nút
con của nút "bành trướng"...Nếu việc "bành trướng" bằng BFS thất bại thì ta quay lui
lại và chọn nút con tốt thứ hai của tập OPEN trước đó, rồi lại tiếp tục bành trướng
bằng BFS...
Hình : Chiến lược lai BFS-MC trong đó, BFS được áp dụng cục bộ và chiều sâu được
áp dụng toàn cục.
Có một cách phối hợp nổi tiếng khác được gọi là tìm kiếm theo giai đoạn được thực
hiện như sau. Thay vì lưu trữ trong bộ nhớ toàn bộ cây tìm kiếm được sinh ra bởi
BFS, ta chỉ giữ lại cây con có triển vọng nhất. Khi một lượng bộ nhớ M0 được dùng
hết, ta sẽ đánh dấu một tập con các trạng thái trong OPEN (những trạng thái có giá
trị hàm f thấp nhất) để giữ lại; những đường đi tốt nhất qua những trạng thái này
cũng sẽ được ghi nhớ và tất cả phần còn lại của cây bị loại bỏ. Quá trình tìm kiếm
sau đó sẽ tiếp tục theo BFS cho tới khi một lượng bộ nhớ M0 lại được dùng hết và cứ
thế. Chiến lược này có thể được xem như là một sự lai ghép giữa BF và leo đèo.
Trong đó, leo đèo thuần túy loại bỏ tất cả nhưng chỉ giữ lại phương án tốt nhất còn
tìm kiếm theo giai đoạn loại bỏ tất cả nhưng chỉ giữ lại tập các phương án tốt nhất.
41
A. TỔNG QUAN TRÍ TUỆ NHÂN TẠO
I. MỞ ĐẦU
Chế tạo được những cỗ máy thông minh như con người (thậm chí thông minh hơn
con người) là một ước mơ cháy bỏng của loài người từ hàng ngàn năm nay. Hẳn bạn
đọc còn nhớ đến nhà khoa học Alan Turing cùng những đóng góp to lớn của ông
trong lĩnh vực trí tuệ nhân tạo. Năng lực máy tính ngày càng mạnh mẽ là một điều
kiện hết sức thuận lợi cho trí tuệ nhân tạo. Điều này cho phép những chương trình
máy tính áp dụng các thuật giải trí tuệ nhân tạo có khả năng phản ứng nhanh và
hiệu quả hơn trước. Sự kiện máy tính Deep Blue đánh bại kiện tướng cờ vua thế giới
Casparov là một minh chứng hùng hồn cho một bước tiến dài trong công cuộc nghiên
cứu về trí tuệ nhân tạo. Tuycó thể đánh bại được Casparov nhưng Deep Blue là một
cỗ máy chỉ biết đánh cờ ! Nó thậm chí không có được trí thông minh sơ đẳng của một
đứa bé biết lên ba như nhận diện được những người thân, khả năng quan sát nhận
biết thế giới, tình cảm thương, ghét, ... Ngành trí tuệ nhân tạo đã có những bước tiến
đáng kể, nhưng một trí tuệ nhân tạo thực sự vẫn chỉ có trong những bộ phim khoa
học giả tưởng của Hollywood. Vậy thì tại sao chúng ta vẫn nghiên cứu về trí tuệ nhân
tạo? Điều này cũng tương tự như ước mơ chế tạo vàng của các nhà giả kim thuật
thời Trung Cổ, tuy chưa thành công nhưng chính quá trình nghiên cứu đã làm sáng tỏ
nhiều vấn đề.
Mặc dù mục tiêu tối thượng của ngành TTNT là xây dựng một chiếc máy có năng lực
tư duy tương tự như con người nhưng khả năng hiện tại của tất cả các sản phẩm
TTNT vẫn còn rất khiêm tốn so với mục tiêu đã đề ra. Tuy vậy, ngành khoa học mới
mẻ này vẫn đang tiến bộ mỗi ngày và đang tỏ ra ngày càng hữu dụng trong một số
công việc đòi hỏi trí thông minh của con người. Hình ảnh sau sẽ giúp bạn hình dung
được tình hình của ngành trí tuệ nhân tạo.
Trước khi bước vào tìm hiểu về trí tuệ nhân tạo, chúng ta hãy nhắc lại một định
nghĩa được nhiều nhà khoa học chấp nhận.
Mục tiêu của ngành khoa học trí tuệ nhân tạo ?
Tạo ra những chiếc máy tính có khả năng nhận thức, suy luận và phản ứng.
Nhận thức được hiểu là khả năng quan sát, học hỏi, hiểu biết cũng như những kinh
nghiệm về thế giới xung quanh. Quá trình nhận thức giúp con người có tri thức. Suy
luận là khả năng vận dụng những tri thức sẵn có để phản ứng với những tình huống
42
hay những vấn đề - bài toán gặp phải trong cuộc sống. Nhận thức và suy luận để từ
đó đưa ra những phản ứng thích hợp là ba hành vi có thể nói là đặc trưng cho trí tuệ
của con người. (Dĩ nhiên còn một yếu tố nữa là tình cảm. Nhưng chúng ta sẽ không
đề cập đến ở đây!). Do đó, cũng không có gì ngạc nhiên khi muốn tạo ra một chiếc
máy tính thông minh, ta cần trang bị cho nó những khả năng này. Cả ba khả
năng này đều cần đến một yếu tố cơ bản là tri thức.
Dưới góc nhìn của tập sách này, xây dựng trí tuệ nhân tạo là tìm cách biểu diễn tri
thức, tìm cách vận dụng tri thức để giải quyết vấn đề và tìm cách bổ sung tri
thức bằng cách "phát hiện" tri thức từ các thông tin sẵn có (máy học).
43
II. THÔNG TIN, DỮ LIỆU VÀ TRI THỨC
Tri thức là một khái niệm rất trừu tượng. Do đó, chúng ta sẽ không cố gắng đưa ra
một định nghĩa hình thức chính xác ở đây. Thay vào đó, chúng ta hãy cùng nhau cảm
nhận khái niệm "tri thức" bằng cách so sánh nó với hai khái niệm khác là thông tin
và dữ liệu.
Nhà bác học nổi tiếng Karan Sing đã từng nói rằng "Chúng ta đang ngập chìm trong
biển thông tin nhưng lại đang khát tri thức". Câu nói này làm nổi bật sự khác biệt
về lượng lẫn về chất giữa hai khái niệm thông tin và tri thức.
Trong ngữ cảnh của ngành khoa học máy tính, người ta quan niệm rằng dữ liệu là
các con số, chữ cái, hình ảnh, âm thanh... mà máy tính có thể tiếp nhận và xử lý.
Bản thân dữ liệu thường không có ý nghĩa đối với con người. Còn thông tin là tất cả
những gì mà con người có thể cảm nhận được một cách trực tiếp thông qua các giác
quan của mình (khứu giác, vị giác, thính giác, xúc giác, thị giác và giác quan thứ 6)
hay gián tiếp thông qua các phương tiện kỹ thuật như tivi, radio, cassette,... Thông
tin đối với con người luôn có một ý nghĩa nhất định nào đó. Với phương tiện máy tính
(mà cụ thể là các thiết bị đầu ra), con người sẽ tiếp thu được một phần dữ liệu có ý
nghĩa đối với mình. Nếu so về lượng, dữ liệu thường nhiều hơn thông tin.
Cũng có thể quan niệm thông tin là quan hệ giữa các dữ liệu. Các dữ liệu được sắp
xếp theo một thứ tự hay được tập hợp lại theo một quan hệ nào đó sẽ chứa đựng
thông tin. Nếu những quan hệ này được chỉ ra một cách rõ ràng thì đó là các tri thức.
Chẳng hạn :
Trong toán học :
Bản thân từng con số riêng lẻ như 1, 1, 3, 5, 2, 7, 11, ... là các dữ liệu. Tuy nhiên,
khi đặt chúng lại với nhau theo trật tự như dưới đây thì giữa chúng đã bắt đầu có
một mối liên hệ
Dữ liệu : 1, 1, 2, 3, 5, 8, 13, 21, 34, ....
Mối liên hệ này có thể được biểu diễn bằng công thức sau : Un = Un-1 + Un-2.
Công thức nêu trên chính là tri thức.
Trong vật lý :
Bản sau đây cho chúng ta biết số đo về điện trở (R), điện thế (U) và cường độ dòng
điện (I) trong một mạch điện.
I U R
5 10 2
2.5 20 8
44
4 12 3
7.3 14.6 2
Bản thân những con số trong các cột của bản trên không có mấy ý nghĩa nếu ta tách
rời chúng ta. Nhưng khi đặt kế nhau, chúng đã cho thấy có một sự liên hệ nào đó. Và
mối liên hệ này có thể được diễn tả bằng công thức đơn giản sau :
Công thức này là tri thức.
Trong cuộc sống hàng ngày :
Hằng ng...
Tags: giáo trình Thuật toán