Thuật Toán Và Thuật Giải 11

Còn một kiểu kết hợp phức tạp hơn nữa. Trong đó, BFS được thực hiện cục bộ và chiều sâu được thực hiện toàn cục. Ta bắt đầu tìm kiếm theo BFS cho tới khi một sự lượng bộ nhớ xác định M0 được dùng hết. Tại điểm này, chúng ta xem tất cả những trạng thái trong OPEN như những trạng thái con trực tiếp của trạng thái ban đầu và chuyển giao chúng cho tìm kiếm chiều sâu.
Nội dung trích xuất từ tài liệu:
Thuật Toán Và Thuật Giải 11Còn một kiểu kết hợp phức tạp hơn nữa. Trong đó, BFS được thực hiện cục bộ và chiềusâu được thực hiện toàn cục. Ta bắt đầu tìm kiếm theo BFS cho tới khi một sự lượng bộnhớ xác định M0 được dùng hết. Tại điểm này, chúng ta xem tất cả những trạng thái trongOPEN như những trạng thái con trực tiếp của trạng thái ban đầu và chuyển giao chúngcho tìm kiếm chiều sâu. Tìm kiếm chiều sâu sẽ chọn trạng thái tốt nhất trong những trạngthái con này và bành trướng nó dùng BFS, nghĩa là nó chuyển trạng thái đã chọn chotì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áicon 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ệcbà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ậpOPEN 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ệnnhư 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ẽ đánhdấ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ấtcả 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ớikhi 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 xemnhư 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.A. TỔNG QUAN TRÍ TUỆ NHÂN TẠOI. MỞ ĐẦUChế tạo được những cỗ máy thông minh như con người (thậm chí thông minh hơn conngườ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ònnhớ đế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ợicho 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ậtgiả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ínhDeep Blue đánh bại kiện tướng cờ vua thế giới Casparov là một minh chứng hùng hồncho 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ườithâ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ântạ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ó trongnhững bộ phim khoa học giả tưởng của Hollywood. Vậy thì tại sao chúng ta vẫn nghiêncứ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àmsá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ẫncò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ỏitrí 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ủangà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 kinhnghiệ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ậnlà 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 hay nhữngvấ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ữngphả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ầnphải 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ằngcách phát hiện tri thức từ các thông tin sẵn có (máy học).II. THÔNG TIN, DỮ LIỆU VÀ TRI THỨCTri 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 ...