tailieunhanh - Giáo trình Trí tuệ Nhân tạo part 5

Giả sử đường đi này “thoát ra” khỏi cây tìm kiếm tại đỉnh lá n (Xem hình ). Có thể xẩy ra hai khả năng: n trùng với G1 hoặc không. Nếu n là G1 thì vì G được chọn để phát triển trước G1, nên f(G) f(G1), do đó g(G) g(G1) = l. Nếu n G1 thì do h(u) là hàm đánh giá thấp, nên f(n) = g(n) + h(n) l. Mặt khác, cũng do G được chọn để phát triển trước n, nên f(G) f(n), do đó, g(G) l . | kết thúc G1 với độ dài l. Giả sử đường đi này thoát ra khỏi cây tìm kiếm tại đỉnh lá n Xem hình . Có thể xẩy ra hai khả năng n trùng với G1 hoặc không. Nếu n là G1 thì vì G được chọn để phát triển trước G1 nên f G f G1 do đó g G g G1 l. Nếu n G1 thì do h u là hàm đánh giá thấp nên f n g n h n l. Mặt khác cũng do G được chọn để phát triển trước n nên f G f n do đó g G l. Như vậy ta đã chứng minh được rằng độ dài của đường đi mà thuật toán tìm ra g G không dài hơn độ dài l của đường đi tối ưu. Vậy nó là độ dài đường đi tối ưu. Trong trường hợp hàm đánh giá h u 0 với mọi u thuật toán A chính là thuật toán tìm kiếm tốt nhất đầu tiên với hàm đánh giá g u mà ta đã nói đến. Thuật toán A đã được chứng tỏ là thuật toán hiệu quả nhất trong số các thuật toán đầy đủ và tối ưu cho vấn đề tìm kiếm đường đi ngắn nhất. Thuật toán tìm kiếm nhánh-và-cận. Thuật toán nhánh_và_cận là thuật toán sử dụng tìm kiếm leo đồi với hàm đánh giá f u . Trong thuật toán này tại mỗi bước khi phát triển trạng thái u thì ta sẽ chọn trạng thái tốt nhất v f v nhỏ nhất trong số các trạng thái kề u đề phát triển ở bước sau. Đi xuống cho tới khi gặp trạng thái v là đích hoặc gặp trạng thái v không có đỉnh kề hoặc gặp trạng thái v mà f v lớn hơn độ dài đường đi tối ưu tạm thời tức là đường đi đầy đủ ngắn nhất trong số các đường đi đầy đủ mà ta đã tìm ra. Trong các trường hợp này ta không phát triển đỉnh v nữa hay nói cách khác ta cất đi các nhánh cây xuất phát từ v và quay lên cha của v đề tiếp tục đi xuống trạng thái tốt nhất trong các trạng thái còn lại chưa được phát triển. Ví dụ Chúng ta lại xét không gian trạng thái trong hình . Phát triển đỉnh A ta nhận được các đỉnh con C D E và F f C 24 f D 13 f E 21 f F 27. Trong số này D là tốt nhất phát triển D sinh ra các đỉnh con H và E f H 25 f E 19. Đi xuống phát triển E sinh ra các đỉnh con là K và I f K 17 f I 18. Đi xuống phát triển K sinh ra đỉnh B với f B g B 21. Đi xuống B vì B là đỉnh đích vậy ta tìm được đường đi tối ưu tạm thời với độ .

• Kỹ thuật lập trình
• giáo trình Trí tuệ Nhân tạo
• bài giảng Trí tuệ Nhân tạo
• tài liệu Trí tuệ Nhân tạo
• đề cương Trí tuệ Nhân tạo
• lý thuyết Trí tuệ Nhân tạo
• trí tuệ nhân tạo
• phương pháo tư duy
• kỹ năng tư duy
• trí tuệ con người
• tư duy sáng tạo
• kiến thức trí tuệ
• giáo trình
• kinh tế chính trị học
• học thuyết kinh tế
• sách kinh tế học
• tài liệu học đại học
• tổng quan về trí tuệ nhân tạo
• nghiên cứu trí tuệ nhân tạo
• Bài tập trí tuệ nhân tạo
• Giải thuật tìm kiếm
• Tìm kiếm hệ thống
• đề cương bài giảng
• sách trí tuệ nhân tạo
• xử lý ngôn ngữ tự nhiên
• ứng dụng trí tuệ nhân tạo
• sản phẩm trí tuệ nhân tạo
• Kỹ thuật lập trình
• Khoa học trí tuệ nhân tạo
• Trí tuệ nhân tạo quan tâm
• Không gian trạng thái trí tuệ nhân tạo
• phương pháp giải quyết vấn đề cơ bản
• điều khiển tốc độ động cơ
• trí thông minh nhân tạo
• kỹ thuật công nghệ
• Tri tuệ nhân tạo
• nghiên cứu Tri tuệ nhân tạo
• hệ thống Tri tuệ nhân tạo
• thiết kế Tri tuệ nhân tạo
• tìm hiểu Tri tuệ nhân tạo
• Nhập môn trí tuệ nhân tạo
• Biểu diễn tri thức
• Trí tuệ nhân tạo hiện đại
• Artificial Intelligence
• Phương pháp tìm kiếm lời giải
• Phương pháp tìm kiếm heuristic
• sản phẩm trí tuệ
• tri thức
• phương pháp biểu diễn tri thức