HỌC VIỆN KỸ THUẬT QUÂN SỰ
KHOA CÔNG NGHỆ THÔNG TIN
BÁO CÁO MÔN HỌC
TRÍ TUỆ NHÂN TẠO
Giáo viên hướng dẫn: Ngô Hữu Phúc
HÀ NỘI 3/2010
Báo cáo môn trí tuệ nhân tạo
I-Đề tài:
Mô tả không gian trạng thái bài toán người đưa thư(Travelling Saleman
Problem – PST) và dùng giải thuật Local Search để giải quyết.
II-Mô tả bài toán:
- Bài toán người đưa thư là một bài toán cổ điển, thuộc tối ưu rời rạc hay tổ
hợp. Đây là một minh họa điển hình cho lớp bài toán trong lý thuyết độ
phức tạp tính toán.
- Nội dung: Có một người giao hàng cần đi giao hàng tại n thành phố. Xuất
phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và
trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ
một thành phố đến các thành phố khác là xác định được. Hãy tìm một chu
trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài
các cạnh là nhỏ nhất.
III-Giao diện chính của chương trình:
Chương trình được thiết kế trên Visual Basic 2005 sử dụng ngôn ngữ
VB.Net.
Bao gồm:
- Picturebox: để biểu diễn không gian trạng thái của bài toán
- Textbox: để nhập vào số thành phố
- Nút khởi tạo: khởi tạo các trọng số (khoảng cách giữa 2 thành phố)
- Nút Generate để vẽ không gian trạng thái của bài toàn dựa vào số thành
phố nhập vào.
- Combobox: chọn điểm (thành phố)xuất phát.
- Chạy: chạy thuật toán local search để tìm đường đi ngắn nhất cho bài

không quay lại thành phố vừa đi qua.
- Tiếp tục xét giá trị của mảng a(s, j) (với s = j) và lặp lại quá trình trên.
Nhưng lần này khi xóa thì sẽ xóa cả mảng a (s, j) và mảng a(j,s).
- TH1: Nếu trong quá trình xét mà xác định được điểm tiếp theo chính là
điểm xuất phát thì sẽ kiểm tra xem đã đi đủ số thành phố cần đi qua chưa.
Nếu chưa thì sẽ quay lại đỉnh vừa rồi và xét tiếp trừ điểm xuất phát ra.
Ngược lại nếu đã đủ số thành phố cần đi qua thì dừng thuật toán.
- TH2: Nếu điểm tiếp theo chỉ có còn điểm xuất phát mà số thành phố đi qua
chưa đủ thì đó là bài toán không có lời giải. Dừng thuật toán.
- TH3: Hoặc sau khi đến thành phố thứ n (không phải thành phố xuất phát)
mà không còn đường đi tiếp thì đấy cũng là bài toán không có lời giải.
Dừng thuật toán.
- Từ đầu thuật toán sẽ có 1 biến đếm để đếm độ dài quãng đường đã đi
qua.
VI – Code:
a. Nút khởi tạo:
- Số thành phố nhập vào nhỏ hơn 2 thì báo lỗi
If tp <= 2 Then
MsgBox("So thanh pho nhap vao phai lon hon 2")
Exit Sub
Else
- Gán giá trị cho các phần tử trong 2 mảng a(i,j) và a1(i,j)
For i = 1 To tp
For j = 1 To tp
a(i, j) = max
a1(i, j) = max
Next
Next
- Nhập khoảng cách giữa các thành phố vào nửa ma trận chéo trên của
a(i,j)

If (a(i, j) <> max) Then
g.DrawLine(pen, point(i), point(j))
End If
Next
Next
- Add tọa độ các point vào combobox (mỗi point sẽ là 1 phần tử của
combobox)
For i = 1 To tp
ComboBox1.Items.Add(point(i))
Next
c. Nút Chạy:
- Lấy chỉ số của phần tử mà combobox đang được chỉ định
Dim index As Integer = ComboBox1.SelectedIndex + 1
- Đổ giá trị trong mảng a(i,j) vào mảng a1(i,j) để lưu lại các giá trị khởi tạo
ban đầu
For i = 1 To tp
For j = 1 To tp
a1(i, j) = a(i, j)
a1(j, i) = a(j, i)
Next
Next
- Tìm đoạn đường ngắn nhất xuất phát từ điểm ban đầu
For i = 1 To tp
If (a1(index, i) < min) Then
min = a1(index, i)
End If
Next
dodai += min
For i = 1 To tp
If a1(index, i) = min Then

- TH2: tìm được điểm xuất phát sau khi đi hết các TP
If dem = tp - 1 Then
dem += 1
duongdi(j + 2) = i
Exit For
- TH3: Về điểm xuất phát nhưng chưa qua hết các TP. Quay lại đỉnh trước
đó và bỏ qua đỉnh xuất phát ở lần xét tiếp theo
Else
a1(index, t2) = max
a1(t2, index) = a1(index, t2)
t = t2
j -= 1
dodai -= min
Continue For
End If
Else
- Sau khi tìm được đỉnh đến tiếp theo thì xóa hết các thông tin của đỉnh
trước đấy trong mảng a1(i,j) để đảm bảo không bị quay lại.
dem += 1
duongdi(j + 2) = i
For i = 1 To tp
a1(t2, i) = max
a1(i, t2) = max
Next
Continue For
End If
Next

- Thông báo thứ tự các thành phố đã đi qua và tổng độ dài của đoạn đường
For i = 1 To tp

mang tính chất mô phỏng thuật toán nên còn rất nhiều hạn chế về mặt lâp
trình.
Giao diện vẫn còn phức tạp.
Chương trình khi chạy tốn bộ nhớ
- Cuối cùng do còn thiếu kinh nghiệm về lập trình cũng như sự hạn chế về
mặt thuật toán nên chương trình chỉ có thể mô tả được một cách đơn giản
nhất của thuật toán. Mong thầy bỏ qua và tiếp tục hướng dẫn em.