Bài tập Cơ sở Trí tuệ nhân tạo - Chương 1: Các phương pháp tìm kiếm với nội dung như nguyên lý Heuristic; nguyên lý thứ tự; bài toán gia công trên hai máy và thuật toán Johnson; thuật giải tô màu; thuật toán Vương Hạo và thuật toán Robinsơn . | Bài tập Cơ sở Trí tuệ nhân tạo - Chương 1 Các phương pháp tìm kiếm Bài tập cơ sỏ trí tuệ nhân tạo - SGU2009 Trang 1 CHƯƠNG 1. CÁC PHƯƠNG PHÁP TÌM KIẾM Nguyên lý Heuristic Thuật giải tham lam Với những bài toán mà không gian trạng thái có thể phát sinh cực lớn thì việc dùng phương pháp vét cạn là điều không thể. Nguyên lý tham lam lấy tiêu chuẩn tối ưu toàn cục để làm tiêu chuẩn chọn lựa hành động trong phạm vi cục bộ. Một số ví dụ có thể áp dụng nguyên lý này như các bài toán có mô hình toán học là bài toán người bán hàng bài toán tô màu đồ thị Hơn nữa nếu có một chiến lược tham lam hợp lý thì phương pháp này sẽ tìm được lời giải tối ưu chẳng hạn thuật toán Kruskal thuật toán Prim. Lược đồ của phương pháp tham lam void Greedy A S A là tập các ứng cử viên S là tập nghiệm S φ while A φ x select A chọn phần tử tốt nhất trong A A A - x if S x chấp nhận được S S x Bài toán hành trình người bán hàng Có n thành phố được đánh số từ 1 đến n một người bán hàng xuất phát từ một thành phố muốn đi qua các thành phố khác mỗi thành phố một lần rồi quay về thành phố xuất phát. Giả thiết biết được chi phí đi từ thành phố i đến thành phố j là c i j . Hãy tìm một hành trình cho người bán hàng sao cho tổng chi phí theo hành trình này là thấp nhất. Bài tập cơ sỏ trí tuệ nhân tạo - SGU2009 Trang 2 Thuật giải GTS1 Greedy Traveling Saleman Input số thành phố là n đỉnh xuất phát u và ma trận chi phí c Output tour thứ tự các thành phố đi qua cost chí phí ứng với tour tìm được v u tour u cost 0 for i 1 to n đặt w là thành phố kề sau thành phố v. tour tour w cost cost c v w v w tour tour u cost cost c v u Ví dụ Cho đồ thị có ma trận chi phí như sau 20 42 31 6 24 10 17 6 35 18 25 5 27 14 9 12 9 24 30 12 14 7 21 15 38 40 15 16 5 20 Sử dụng giải thuật GTS1 để tìm hành trình bắt đầu tại các đỉnh v1 1 v2 3 v3 4 v4 5 Hướng dẫn giải GTS1 v1 1 5 2 4 6 3 1 Cost v1 6 7 6 12 16 25 72. Tương tự tính được GTS1 v2 3 2 4 1 5 6 3 Cost v2 5 6 12 6 38 16 83. GTS1 v3 4 2 1 5 3 6 4 Cost v3 9 10 6 21 9 5 .
