1 MỘT SỐ BÀI TOÁN NỔI TIẾNG TRONG TRÍ TUỆ NHÂN TẠO I. Bài toán người đưa thư sử dụng giải thuật Heuristic

1. Phát biểu bài toán:
Bài toán: Để tiết kiệm thời gian đi đưa thư trong một địa phương. Người đưa thư phải đi qua
tất cả các điểm cần phát thư rồi trở về vị trí ban đầu với đường đi ngắn nhất.
Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số dương, tìm đường đi
ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu.
2. Hạn chế khi sử dụng thuật toán tối ưu:
Đồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là thuật toán tìm đường đi
ngắn nhất cho chu trình Haminton. Do đó thuật toán tối ưu sẽ có độ phức tạp là O( n!) à
Không thể thực hiện thuật toán.
-> cần Tìm một thuật giải Heuristic cho bài toán này.
3. Sử dụng thuật toán Heuristic cho bài toán người đưa thư:
- Theo kinh nghiệm của con người trong thực tế thì khi ta đi trên những đoạn đường ngắn
nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất à sử dụng nguyên lý tham lam.
- Thuật giải bài toán sử dụng nguyên lý tham lam:

- Ví dụ về thuật giải trên:
Với một đồ thị trọng số dương như hình bên. Nếu ta
xuất phát từ đỉnh sổ 1, thì đỉnh tiếp theo phải đến là 2 (
vì cạnh 1-2 có trọng số nhỏ nhất so với các đỉnh chưa
2

đến của 1), như vậy tiếp theo ta sẽ đến các đỉnh theo thứ tự là 5, 3, 4, và trở về 1.
Như vậy đường đi ngắn nhất theo giải thuật trình bày trên tìm được là:

- Giao diện chương trình: console Aplication.
4 Khi thực thi, chương trình sẽ yêu cầu chọn nhập ma trận đồ thị bằng tay hay bằng file
“graph.txt”. Ví dụ như hình trên chọn nhập ma trận bằng file txt. Ta nhập tiếp đỉnh bắt đầu
(ở đây nhập 1), thì chương trình sẽ cho ra đáp án cho ví dụ trên:
Đường đi là: 1 – 2 – 5 – 3 – 4 – 1
Chi phí cho đường đi này theo giải thuật Heuristic là: 14.
Nếu như chọn cách nhập ma trận bằng tay thì ta phải nhập từng giá trị của ma trận vào.
- Nhấn ESC để thoát khỏi chương trình, Phím bất kỳ để tiếp tục chương trình với cách duyệt
từ đỉnh khác.
5. Đánh giá thuật giải Heuristic của bài toán:
- Ưu điểm: Thuật giải Heuristic cho bài toán người đưa thư có độ phức tạp O(n
2
) tốt hơn rất
nhiều so với thuật toán tối ưu ( có độ phức tạp O( n!) ).
- Nhược điểm: thuật giải có những hạn chế, chưa cho ra lời giải chính xác.
5

-> Kết luận: Thuật giải Heuristic cho bài toán người đưa thư tuy chưa đưa ra được lời giải
chính xác cho bài toán, nhưng nó cho ra một lời giải có thể chấp nhận được với độ phức tạp
thấp hơn nhiều so với thuật toán tối ưu.
6

II. Lan truyền kích hoạt trên mạng ngữ nghĩa – spreading
activation in semantic network.
Posted on 15/12/2010by thanhcuong1990
1. Đôi điều cần biết về về giải thuật lan truyền kích hoạt(spreading activation)
- Lan truyền kích hoạt (spreading activation) là một phương pháp để tìm kiếm các mạng

- Khi một nút đã kích hoạt nó có thể kích hoạt lại một lần nữa, mặc dù các biến thể của thuật
toán cơ bản cho phép bỏ qua việc lặp đi lặp lại và vòng qua đồ thị.
- Các nút nhận được giá trị kích hoạt mới có vượt quá ngưỡng kích hoạt F được đánh dấu để
kích hoạt vào chu trình kích hoạt tiếp theo.
- Nếu kích hoạt bắt nguồn từ nhiều hơn một nút, một biến của thuật toán sẽ cho phép đánh
dấu các kích hoạt đã đi qua để phân biệt với các con đường chưa được kích hoạt trên đồ thị.
- Thủ tục chấm dứt khi một trong hai không có thêm các nút để kích hoạt trong trường hợp
các dấu hiệu chuyển từ nhiều nguồn gốc, khi có nhiều hơn một con đường xuất phát từ một
nút. Các biến sử dụng trong thuật toán cho phép lặp đi, lặp lại hoặc sa thải nút hoặc dòng
kích hoạt trong đồ thị, chấm dứt sau khi một trạng thái kích hoạt ổn định, đối với một số
trường, được đạt tới, hoặc số lần lặp vượt quá mức tối đa.
3. Ví dụ:
8 Trong ví dụ này, nút gốc của kích hoạt lan truyền là node 1 với giá trị kích hoạt ban đầu là
1(100%). Mỗi liên kết có trọng số là 0.9. Các yếu tố suy biến là 0.85. Có 4 chu kỳ lan truyền
kích hoạt xảy ra (thể hiện qua 4 màu của đồ thị trên). Màu sắc và độ bão hòa chỉ ra các giá
trị kích hoạt khác nhau.
9

III. Giải bài toán tam giác sử dụng mạng ngữ nghĩa – Solution
for triangle using semantic network
Posted on 16/12/2010by thanhcuong1990
Bài viết này mô tả bài toán giải tam giác bằng mạng ngữ nghĩa (chương trình nhỏ) kèm
theo chương trình demo viết trên Visual studio 2010 (C#). Tài liệu tham khảo hơi nhiều chỗ
nên hiện giờ chưa nhớ hết. Bài này chỉ demo 5 công thức trong tam giác được lấy từ ví dụ
của giáo trình trường Đại học công nghệ thông tin – xuất bản năm 2007.
1. Sơ lược về bài toán tam giác bằng mạng ngữ nghĩa.
Có 22 yếu tố liên quan đến cạnh và góc của tam giác. Để xác định một tam giác thì ta phải


Bắt đầu : đỉnh a, b, acủa đồ thị được kích hoạt.
- Công thức (1) được kích hoạt (vìa, b,a được kích hoạt). Từ công thức (1) tính được cạnh b.
Đỉnh b được kích hoạt.
- Công thức (4) được kích hoạt (vì a, b). Từ công thức (4) tính được góc d
- Công thức (2) được kích hoạt (vì 3 đỉnh b,d,b được kích hoạt). Từ công thức (2) tính được
cạnh c. Đỉnh cđược kích hoạt.
- Công thức (3) được kích hoạt (vì 3 đỉnh a, b, c được kích hoạt) . Từ công thức (3) tính được
diện tích S. Đỉnh S được kích hoạt.
- Công thức (5) được kích hoạt (vì 2 đỉnh S, c được kích hoạt). Từ công thức (5) tính được
hC. Đỉnh hC được kích hoạt.
- Giá trị hC đã được tính.
Thuật toán kết thúc.
11

3. Xây dựng chương trình giải bài toán tam giác bằng mạng ngữ nghĩa theo ví dụ
trên.
Chương trình được xây dựng trên môi trường visual studio 2010, ngôn ngữ C#

Giao diện chương trình demo ví dụ trên.
Về mặt chương trình, ta có thể cài đặt mạng ngữ nghĩa giải bài toán tam giác bằng một mảng
hai chiều A trong đó:
Cột : ứng với công thức. Mỗi cột ứng với một công thức tam giác khác nhau (đỉnh hình chữ
nhật).
Dòng: ứng với yếu tố tam giác. Mỗi dòng ứng với một yếu tố tam giác khác nhau (đỉnh hình
tròn).
Phần tử A[i, j] = -1 nghĩa là trong công thức ứng với cột j có yếu tố tam giác ứng với cột i.
Ngược lại A[i,j] = 0.
// Khai báo biến.
private float[,] a = new float[8, 5];

(3)
(4)
(5)
a
-1
0
0
-1
0
b
-1
-1
0
-1
0
d
0
-1
0
-1
0
a
-1
0
-1
0
0
b
-1
-1

a
1
0
0
1
0
b
1
1
0
1
0
d
0
-1
0
-1
0
a
1
0
1
1
0
b
-1
-1
-1
0
0

0
b
1
1
0
1
0
d
0
-1
0
-1
0
a
1
0
1
1
0
b
1
1
1
0
0
c
0
-1
-1
0

1
0
1
0
d
0
1
0
1
0
a
1
0
1
1
0
b
1
1
1
0
0
c
0
-1
-1
0
-1
S
0

0
1
0
1
0
A
1
0
1
1
0
B
1
1
1
0
0
15

C
0
1
1
0
1
S
0
0
-1
0

1
0
a
1
0
1
1
0
b
1
1
1
0
0
c
0
1
1
0
1
S
0
0
1
0
1
hC
0
0
0