Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan

Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan trình bày các nội dung về các thuật giải tô màu đồ thị, các thuật giải tìm kiếm trên đồ thị, biểu diễn và xử lý tri thức, phân lớp. Mời bạn đọc tham khảo tài liệu để hiểu rõ hơn về các nội dung trên.
Nội dung trích xuất từ tài liệu:
Bài giảng Trí tuệ nhân tạo - ThS. Nguyễn Thị Thúy Loan Cách đánh giá TRÍ TUỆ NHÂN TẠO  Thực hành: 30%  Bài tập: 20% ThS. Nguyễn Thị Thúy Loan  Lý thuyết: 50% 6/8/2010 Nguyễn Thị Thúy Loan 2 Tài liệu tham khảo [1]. Bài giảng của Nguyễn Thị Thúy Loan NỘI DUNG [2]. Trí tuệ nhân tạo, Đỗ Trung Tuấn, NXB Giáo dục, 1998.  Các thuật giải tô màu đồ thị. [3]. Bạch Hưng Khang – Hoàng Kiếm, Trí tuệ nhân  Các thuật giải tìm kiếm trên đồ thị. tạo, NXB KHKT - 1989. [4]. Lập trình C cho TTNT, 3C soft (dịch), NXB Đại  Biểu diễn và xử lý tri thức. học và Trung học chuyên nghiệp Hà nội –  Phân lớp. 1990. [5]. Trang web http://ocw.mit.edu/OcwWeb/Electrical- Engineering-and-Computer-Science/index.htm6/8/2010 Nguyễn Thị Thúy Loan 3 6/8/2010 Nguyễn Thị Thúy Loan 4 Chương I Bài toán  Cho một đồ thị gồm n đỉnh. Quan hệ giữa CÁC THUẬT GIẢI TÔ đỉnh i và đỉnh j, kí hiệu Qhij, là 1 nếu đỉnh i MÀU ĐỒ THỊ có nối với đỉnh j và 0 nếu ngược lại.  Bài toán đặt ra là làm thế nào để tô màu đồ thị sao cho không tồn tại hai đỉnh có quan hệ ThS. Nguyễn Thị Thúy Loan với nhau được tô chung một màu với số màu cần tô là ít nhất? 6 6/8/2010 Nguyễn Thị Thúy Loan 6 Ví dụ Thuật giải tô màu “Tối ưu” Bước 1: [Tô màu] Tô màu i (i bắt đầu xét từ 1) cho đỉnh a b c có bậc lớn nhất. e Bước 2: [Hạ bậc & cấm tô] d h 2.1. Bậc của đỉnh được tô màu i thì bậc:=0. p 2.2. Bậc của đỉnh có quan hệ với đỉnh được tô màu i thì bậc:= bâc – 1. Tô 3 màu Ít nhất chưa? 2.3. Cấm tô màu i cho đỉnh có quan hệ với đỉnh được tô màu i. Bước 3: Lặp lại bước 1 cho đến khi tất cả các đỉnh đều 7 8 được tô màu.6/8/2010 Nguyễn Thị Thúy Loan 7 6/8/2010 Nguyễn Thị Thúy Loan 8 Minh họa Ví dụ Một công ty có 8 đài phát thanh A, B, C, D, E, F, G, H có khoảng cách (km) được cho trong ma trận sau: A B C D E F G H A 0 100 50 30 200 150 40 120 B 0 30 80 120 50 200 150 a C 0 120 100 30 80 50 b c D 0 50 120 150 30 ...