Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
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
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
Báo cáo đồ án môn: Trí tuệ nhân tạo
Giáo viên: Ngô Hữu Phúc
Sinh Viên: Nguyễn Thế Định – Tin học 5A
Đồ án số 15: Không gian trạng thái được mô tả là bản đồ giao thông của 1 xã, phường nào
đó. Hãy xây dựng chương trình cho phép tìm kiếm đường đi từ 1 điểm trên bản đồ đến 1
điểm khác trên bản đồ theo phương pháp tìm kiếm Nhành và cận
I. Cơ sở lý thuyết:
1.Bài toán tìm kiếm
Bài toán tìm kiếm có thể hiểu 1 cách tổng quát là: Trong 1 tập hợp rất nhiều
đối tượng tìm một đối tượng thỏa mãn một số yêu cầu nào đó. Ví dụ như các trò
chơi, ví dụ như cờ caro, cờ vua cũng có thể xem là 1 bài toán tìm kiếm, hoặc tìm
đường đi cũng là 1 bài toán tím kiếm khá cơ bản và được tập trung nghiên cứu trong
môn:” Nhập môn Trí tuệ Nhân tạo “
Kỹ thuật tìm kiếm được chia ra làm 3 loại:
- Kỹ thuật tìm kiếm mù: Trong bài toán này, chúng ta hoàn toàn
không biết gì về các đối tượng để hướng dẫn tìm kiếm mà chỉ đơn thuần là
xem xét tất cả các đối tượng của 1 hệ thống để phát hiện ra đối tượng cần
tìm. Một số kỹ thuật tìm kiếm mù: Tìm kiếm theo chiều rộng (Breadth-first
search) và tìm kiếm theo chiều sâu (depth-first search)
- Kỹ thuật tìm kiếm có kinh nghiệm (Tìm kiếm với hàm Heuristic):
Hàm Heuristic là hàm đánh giá được xây dựng nhờ vào kinh nghiệm và sự

- Thuật toán được biểu diễn thông qua cây sau:
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A

Cài đặt thuật toán:
Procedure Hill_Climbing_Search;
Begin
Bước 1: Khởi tạo danh sách L chỉ chứa trạng thái đầu;
Bước 2: Loop do
1. If L rỗng then { thông báo thất bại; stop; }
2. Loại trạng thái u đầu danh sách L;
3. If u là trạng thái kết thúc then { thông báo thành công; stop; }
4. For mỗi trạng thái v kề u đặt v vào L sao cho các phần tử được đưa vào đầu
danh sách L có đánh giá giảm dần;
Bước 3: End;
b. Thuật toán nhánh và cận
Trong thuật toán này, tại mỗi bước phát triển trạng thái u, chọn lấy trang thái v trong
số các trạng thái kề với u sao cho f(v) đạt min
Làm tương tự cho tới khi:
- V là đích, hoặc
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
- V ko có đỉnh kề, hoặc
- V có f(v) lớn hơn độ dài đường đi hiện thời
Khi đó, không phát triển đỉnh v nữa mà quay về cha của v để tìm trạng thái tốt nhất
trong các trạng thái chưa xét
Ví dụ về thuật toán Nhánh và cận:
Xét không gian trạng thái trên, tìm đường đi ngắn nhất từ A đến B
Đầu vào: A là trang thái ban đầu, B là trạng thái đích
Thực hiện thuật toán:

- Hàm đánh giá h(u) là đánh giá thấp
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
- Độ dài các cung không nhỏ hơn 1 số dương nào đó
Từ những cơ sở lý thuyết trên, em đã xây dựng chương trình:” Tìm đường đi ngắn nhất “
dùng thuật toán Nhánh và cận:
II. Đồ án:
1. Giao diện của chương trình:
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
- Giao diên chương trình gồm có:
• 2 ô combobox dùng để lựa chọn điểm xuất phát và đich đến
• 3 label để hiển thị: độ dài tối ưu, đường đi tối ưu và 1 đường đi khác trong
quá trình duyệt
• 1 ô picturebox dùng để hiển thị bản đồ giao thông
• 2 buttton: 1 button tìm đường để bắt đầu quá trình tìm kiếm sau khi đã chọn
điểm xuất phát và đich đến, 1 button thoát để thoát khỏi chương trình
• 32 button dùng để đánh dấu các mốc trên bản đồ
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
2. Các bước xây dựng chương trình
a. Cấu trúc dữ liệu:
Yêu cầu của bài toán:: Không gian trạng thái được mô tả là bản đồ giao
thông của 1 xã, phường nào đó. Hãy xây dựng chương trình cho phép tìm kiếm
đường đi từ 1 điểm trên bản đồ đến 1 điểm khác trên bản đồ theo phương pháp tìm
kiếm Nhành và cận
Đầu vào: 1 bản đồ giao thông
Không gian trạng thái đang xét là 1 bản đồ giao thông:
- Các đường có mũi tên là đường 1 chiều, chiều đúng của đường là theo chiều
mũi tên

vitribtn(1, 12) = 507
vitribtn(2, 12) = 242
vitribtn(1, 13) = 122
vitribtn(2, 13) = 202
vitribtn(1, 14) = 175
vitribtn(2, 14) = 222
vitribtn(1, 15) = 269
vitribtn(2, 15) = 252
vitribtn(1, 16) = 314
vitribtn(2, 16) = 266
vitribtn(1, 17) = 384
vitribtn(2, 17) = 289
vitribtn(1, 18) = 531
vitribtn(2, 18) = 273
vitribtn(1, 19) = 529
vitribtn(2, 19) = 327
vitribtn(1, 20) = 306
vitribtn(2, 20) = 291
vitribtn(1, 21) = 226
vitribtn(2, 21) = 314
vitribtn(1, 22) = 287
vitribtn(2, 22) = 336
vitribtn(1, 23) = 416
vitribtn(2, 23) = 366
vitribtn(1, 24) = 529
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
vitribtn(2, 24) = 390
vitribtn(1, 25) = 69
vitribtn(2, 25) = 336

duong2chieu(A,B) = 0.
Ví dụ: Vậy nếu duong2chieu(A,B) = 1 và duong2chieu(B,A) = 1 thì đường AB là
đường 2 chiều. Nếu duong2chieu(A,B) = 1 nhưng duong2chieu(B,A) = 0 thì đường A
đến B là đường 1 chiều, chỉ đi được từ A đến B và ko đi được từ B đến A
Việc gán vào mảng duong2chieu(50,50) này đồng thời cũng biến bản đồ ta có thành
1 đồ thì không gian trạng thái với các nút và đường đi giữa chúng
Trong bài toán cụ thể này, mảng duong2chieu có giá trị như sau:
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
duong2chieu(2, 29) = 1
duong2chieu(29, 2) = 1
duong2chieu(32, 28) = 1
duong2chieu(7, 32) = 1
duong2chieu(32, 29) = 1
duong2chieu(29, 32) = 1
duong2chieu(30, 13) = 1
duong2chieu(30, 28) = 1
duong2chieu(28, 30) = 1
duong2chieu(4, 29) = 1
duong2chieu(29, 4) = 1
duong2chieu(1, 29) = 1
duong2chieu(29, 1) = 1
duong2chieu(7, 28) = 1
duong2chieu(1, 28) = 1
duong2chieu(28, 1) = 1
duong2chieu(4, 2) = 1
duong2chieu(2, 4) = 1
duong2chieu(4, 8) = 1
duong2chieu(8, 4) = 1
duong2chieu(8, 7) = 1

duong2chieu(14, 21) = 1
duong2chieu(21, 14) = 1
duong2chieu(13, 25) = 1
duong2chieu(25, 13) = 1
duong2chieu(9, 15) = 1
duong2chieu(15, 9) = 1
duong2chieu(15, 16) = 1
duong2chieu(16, 17) = 1
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
duong2chieu(17, 19) = 1
duong2chieu(16, 20) = 1
duong2chieu(20, 16) = 1
duong2chieu(17, 20) = 1
duong2chieu(20, 17) = 1
duong2chieu(21, 15) = 1
duong2chieu(26, 21) = 1
duong2chieu(25, 26) = 1
duong2chieu(26, 25) = 1
duong2chieu(27, 26) = 1
duong2chieu(20, 22) = 1
duong2chieu(22, 20) = 1
duong2chieu(23, 22) = 1
duong2chieu(22, 27) = 1
duong2chieu(27, 22) = 1
duong2chieu(24, 23) = 1
duong2chieu(18, 31) = 1
duong2chieu(31, 16) = 1
duong2chieu(17, 31) = 1
duong2chieu(31, 17) = 1

Math.Sqrt((ox2 - ox1) * (ox2 - ox1) + (oy2 - oy1) * (oy2 - oy1)))
Hàm trả về giá trị khoảng cách giữa A và B theo kiểu double
Hàm duyệt trạng thái con:
Public Sub dttcon(ByVal cha As Integer, ByVal gcha As Double)
nhocha = cha
demmc = 0
Dim kcconcha As Double
For i = 1 To 32
If duong2chieu(cha, i) = 1 Then
mangcon(0, demmc, cha) = i ' Gán nút con i vào mảng con
kcconcha = tinhkc(vitribtn(1, cha), vitribtn(2, cha),
vitribtn(1, i), vitribtn(2, i)) ' Khoảng cách giữa nút con i và nút cha
mangcon(1, i, cha) = gcha + kcconcha 'Giá trị hàm G(i) hiện
tại = G(cha) + kc từ nút con i đến cha
mangcon(2, i, cha) = tinhkc(vitribtn(1, i), vitribtn(2, i),
vitribtn(1, dich), vitribtn(2, dich)) ' h(i) - Giá trị ước lượng từ nút con
i đến đích
demmc += 1
End If
Next
' Nếu số nút con > 1 thì xắp xếp các nút giảm dần theo giá trị f
Dim a, b, fa, fb As Double
If demmc > 1 Then
For i = 0 To demmc - 1
For j = i + 1 To demmc - 1
a = mangcon(0, i, cha)
b = mangcon(0, j, cha)
fa = mangcon(1, a, cha) + mangcon(2, a, cha)
fb = mangcon(1, b, cha) + mangcon(2, b, cha)
If fa < fb Then

Mang(2, i, cha) lưu lại giá trị h(u)
Biến nhocha dùng để lưu lại cha nút i
Sau khi đã tìm ra các con i của nút cha,
Nếu số con từ 2 trở lên, ta dùng thuật toán xắp xếp nổi bọt để xắp xếp các con i tìm được
theo thứ tự giảm dần của giá trị f(i)
Nếu nút cha nhập vào ko có con, Ta trả về giá trị ktracon = false
Thuật toán Nhánh và cận
Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
Sau khi đã xây dựng xong hàm duyệt trạng thái con (dttcon) ta bắt đầu đi vào thuật toán
tìm kiếm Nhánh và cận được thực hiện khi click button Tìm đường (btntimduong)
' Sự kiện khi click vào nút tìm đường
Private Sub btntimduong_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles btntimduong.Click
khoitao()
Dim nutdangxet, nutcha, sonutdiqua, nhokqtoiuu, nhovitri, soduongdi
As Integer
Dim quangduong, cost, costphu, nhotam As Double
Mangduongdi(1, 50) = New Integer
mangvidu(1, 50) = New Integer
soduongdi = 0
sonutdiqua = 1
cost = 100000
quangduong = 0
Try
dich = Convert.ToDouble(ComboBox2.Text)
start = Convert.ToDouble(ComboBox1.Text)
stackduyet.Push(start)
stackduyet.Push(start)
Mangduongdi(0, 0) = start
Mangduongdi(1, 0) = start

Giáo viên hướng dấn : Ngô Hữu Phúc Sinh viên : Nguyễn Thế Định – Tin học 5A
nhotam = sonutdiqua
For i = 0 To sonutdiqua
mangvidu(0, i) = Mangduongdi(0, i)
mangvidu(1, i) = Mangduongdi(1, i)
Next
'
GoTo lap
End If
Else
If quangduong < cost Then
dttcon(nutdangxet, mangcon(1, nutdangxet, nutcha))
' Nếu nút duyệt ko có con -> Bỏ qua
If ktracon = True Then
GoTo lap
End If
For i = 0 To sonutdiqua
If sonutdiqua > 2 Then
If nutdangxet = Mangduongdi(0, i) And
nutcha = Mangduongdi(1, i) Then
For j = i To sonutdiqua
Mangduongdi(0, j) = 0
Mangduongdi(1, j) = 0
Next
GoTo lap
End If
End If
Next
'Gán vào mảng tạm đường đi hiện tại
For i = 0 To sonutdiqua

Next
Label6.Text += Convert.ToString(dich)
' Hiển thị đường đi khác trong quá trình duyet:
If soduongdi > 1 Then
For i = 1 To nhotam
Label8.Text +=Convert.ToString(mangvidu(0, i)) + " >"
Next
Label8.Text = Label8.Text + Convert.ToString(dich) + " =
" + Convert.ToString(costphu * 2)
Else
Label8.Text = "Ko tim thay duong khi nao khac trong qua
trinh duyet"
End If
Catch ex As Exception
MsgBox("Nhập lại giá trị trong combobox")
End Try
End Sub
III Kết quá thu được từ chương trình tìm đường sử dụng thuật toán Nhánh và cận:
Khuôn khổ của đồ án này chỉ giới hạn trong việc minh họa cho thuật toán Nhánh và cận,
chứ chưa hướng tới việc áp dụng trong thực tế
Nếu muốn áp dụng cho thực tế thì sẽ cần nhiều thời gian và quá trình tìm hiểu hơn, sau khi
kết thúc môn học này, em mong thầy có thể giúp đỡ em để em hoàn thành chương trình 1
cách hoàn thiện hơn
Em xin cám ơn !
IV.Tài liệu tham khảo:
-Slide và bải giảng của thầy Ngô Hữu Phúc
-Và 1 số tài liệu khác