Bộ đề tổng hợp môn Trí tuệ nhân tạo pptx

Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4

Đề 1

Câu 1.(3đ)

Trình bày sự khác nhau giữa thuật toán và thuật giải Heuristics. Hãy nêu 1 ví dụ về

thuật giải Heuristics

Câu 2.(7đ)

a. Trình bày thuật giải Robinson.

b. Áp dụng thuật giải Robinson, chứng minh bài toán sau:

¬p ∨ q , (s ∨ ¬ q) ∧ (r ∨ ¬s) , p ∧ u ⇒ r, u

c. Hãy xây dựng cây định danh và tìm luật theo phương pháp vector đặc trưng của

Quinlan để xác định một loại quả độc hay không độc theo bảng số liệu sau.

Tên Vị Màu Vỏ Độc

A Ngọt Đỏ Nhẵn không

B Cay Đỏ Nhẵn không

C Chua Vàng Có gai Không

D Cay Vàng có gai Độc

E Ngọt Tím Có gai Không

F Chua Vàng Nhẵn Không

G Ngọt Tím Nhẵn Không

H Cay Tím có gai Độc

Đề 2 (có giải) trang 13)

Câu 1(3 đ)

Trình bày khái niệm hàm heuristics.: Xây dựng hàm đánh giá h cho bài toán ở bảng

1 để giải bài toán TACI sau:

3 2 6 1 2 3

1 5 4 8 4

7 8 7 6 5

Ti TG

Bảng 1

Câu 2(7 đ)

a. Trình bày thuật giải A*.

b. Giải bài toán tìm đường đi ngắn nhất từ A đến B trong đồ thị không gian trạng

thái ở Hình 1 theo thuật giải A*. (Giá trị cạnh các đỉnh là hàm đánh giá h(T), cạnh các

cung là độ dài cung).

[email protected] - k2cn4.n-stars.org – 4rum K2CN4 1

0

E

K

C

H

D

I

E

K

G

H

B

A

I

F

G

N

22

16

25 24

30

20

12

14

13

17

9

20

11

9

17

10

16

5

7

6

18

12 15

10

8

13

12 12

8

10 Hình 1

Bé §Ò Tæng Hîp - M«n TrÝ TuÖ Nh©n T¹o – K2CN4

Đề 3

Câu 1 (3đ)

a. Trình bày thuật giải Vương Hạo.

b. Áp dụng thuật toán Vương hạo, chứng minh bài toán sau:

p ∨ ¬q , (¬s ∨ ¬q) ∧ (r ∨s) , ¬p ∧ u ⇒ r ∨ u

Câu 2 : (7đ)

a. Trình bày thuật giải A KT

.

b. Dùng thuật toán A KT để giải bài toán TACI sau:

Trạng thái ban đầu Trạng thái kết thúc

Đề 4

Câu 1: (4đ)

Có 6 đội bóng thi đấu vòng tròn (lượt đi). Biết rằng :

- Đội A đã đấu với dội B và đội D.

- Đội C đã đấu với dội D và đội F

- Đội D đã đấu với dội A và đội F.

- Đội B đã đấu với dội E và đội F.

A B C D E F

A AB AC AD AE AF

B BC BD BE BF

C CD CE CF

D DE DF

E EF

F

Mỗi đội chỉ có được thi đấu 1 trận trong 1 tuần.

Chỉ có 2 đội thamgia 1 trận đấu.

Hãy xếp lịch thi đấu sao cho số tuần diễn ra các trận đấu còn lại là ít nhất ? (Dùng thuật

toán tô màu)

Câu 2: (6đ) Cho bảng quan sát :

STT Quang cảnh Nhiệt độ Gió Picnic

1 Nắng Cao Nhẹ Không

2 Mưa Thấp Mạnh Không

3 Râm mát TB Nhẹ Được

4 Nắng TB Mạnh Không

5 Mưa Cao Mạnh Không

6 Râm mát Thấp Mạnh Được

[email protected] - k2cn4.n-stars.org – 4rum K2CN4

L E Y

O U

Q D N

L E

Q U Y

D O N

2