BÁO CÁO CHUYÊN ĐỀ
THUẬT TOÁN NHÁNH CẬN BRANCH-AND-BOUND
Advanced Algorithm Design and Analysis
GVHD: PHAN Anh-Cang, PhD.
HV: Nguyễn Quan Khánh
Nội dung: Đường đi người giao hàng - Traveling Salesman Problem
1. Mô tả, giải thích
2. Phân tích, đánh giá
3. Áp dụng trong thực tế
4. Cài đặt
2
Cho trước một tập hợp các thành phố và khoảng cách giữa mỗi cặp thành phố, mỗi thành phố đều có đường đi đến các thành phố còn lại, tìm chuyến đi ngắn nhất có thể đến mỗi thành phố đúng một lần và quay trở lại điểm xuất phát.
3
Phân nhánh - Xây dựng cây
1. Nút gốc: Xuất phát từ một thành phố (bậc 0)
2. Nút gốc có n-1 nút con (bậc 1)
3. Mỗi nút con bậc 1 có n-2 nút con (bậc 2)
4
Công thức tính cận dưới - tìm min
1. Nút gốc: Cận dưới = n * độ dài cạnh nhỏ nhất
2. Nút có bậc i: Cận dưới = TGT + (n-i) * độ dài cạnh nhỏ nhất trong số các cạnh chưa sử dụng
- n: tổng số cạnh của một chu trình
- TGT: tổng giá trị của phương án thành phần đến nút đang xét
5
2. Phân tích, đánh giá
6
TGT = 0
CD = 4*10 = 40
0
TGT = 10
CD = 10+3*15 = 55
TGT = 20
CD = 20+3*15 = 65
TGT = 15
CD = 15+3*15 = 45
3
1
2
10
20
15
3
2
TGT = 35
CD = 35+2*20 = 75
TGT = 45
CD = 45+2*20 = 85
35
25
TGT = 45
CD = 45+2*20 = 85
TGT = 50
CD = 50+2*20 = 90
1
2
25
30
TGT = 65
CD = 65+1*25 = 90
0-1-3-2-0=65+15= 80
2
30
TGT = 80
CD = 80+1*25 = 105
0-3-1-2-0=80+15=
95
2
35
TGT = 85
CD = 85+1*25 = 110
0-3-2-1-0=85+10=
95
1
35
TGT = 45
CD = 45+2*20 = 85
TGT = 50
CD = 50+2*20 = 90
3
1
30
35
TGT = 70
CD = 70+1*25 = 95
0-2-3-1-0=70+10=
80
1
25
3. Áp dụng trong thực tế
7
4. Cài đặt
8