BÀI TOÁN NGƯỜI DU LỊCH
Giáo viên: TS. Nguyễn Văn Hiệu Email: nvhieuqt@dut.udn.vn
Nội dung
• Phát biểu bài toán • Phân tích • Ý tưởng • Thuật giải của bài toán
– Thủ tục rút gọn để tính cận dưới – Thủ tục phân nhánh – Thủ tục chọn cận phân nhánh – Thủ tục chọn hai cạnh cuối cùng
Bài toán
• Hãy tìm hành trình
Có n thành phố ký hiệu: T1, T2,…, Tn Cij là chi phí từ thành phố Ti
(chu trình) với chi phí nhỏ nhất
đến Tj
Xuất phát từ một thành phố nào đó đi qua tất cả các thành phố mỗi thành phố đúng một lần, rồi quay trở lại thành phố xuất phát.
Phân tích
Nhận xét:
Đồ thị ứng dụng có thể
• Xét đồ thị có trọng: G = (V, E)
Mỗi thành phố là một
có hướng hoặc vô hướng; đỉnh của đồ thị
Mỗi đường đi giữa các thành phố là một cạnh nối giữa các đỉnh của đồ thị
Các cặp đinh không có đường đi gán trọng số ∞,
Tạo nên một chu trình ( đỉnh xuất phát trùng với đỉnh kết thúc)
Phân tích
• Xét đồ thị có trọng: G = (V, E)
Mỗi thành phố là một
Mỗi đường đi giữa các thành phố là một cạnh nối giữa các đỉnh của đồ thị
đỉnh của đồ thị
Đường đi tìm được: x1, x2, …, xn, x1 với xi là đỉnh, (xi, xi+1) là cạnh Bài toán người du lịch: f(x1…xn)=c[x1,x2]+…+c[xn, x1] min
Ý tưởng
Thực hiện quá trình
phân nhánh
Tính giá trị cận Tập tất cả các hành trình
Thủ tục cứ tiếp tục
dưới trên mỗi tập
cho đến lúc nhận
Tập hành trình không chứa (i,j)
đầy đủ
Tập hành trình chứ (i,j) được một hành trình
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
2. Thủ tục chọn cạnh phân nhánh
3. Thủ tục phân nhánh
4. Thủ tục chọn hai cạnh cuối cùng
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
lịch sẽ chứa đúng một phần tử của mỗi dòng và đúng một phần tử của mỗi cột của ma trận chi phí.
Cơ sở lý luận Hành trình của người du
Nhận xét
Cơ sở lý luận Nếu trừ bớt mỗi phần tử của một cột của ma trận chi phí đi cùng một số b, thì độ dài tất cả các hành trình cũng sẽ giảm đi b.
Hành trình tối ưu sẽ không bị thay đổi
Nếu trừ bớt mỗi phần tử của một dòng của ma trận chi phí đi cùng một số a , thì độ dài tất cả các hành trình cũng sẽ giảm đi a.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
tục rút gọn;
Khái niệm Thủ tục này được gọi là thủ
Ma trận thu được gọi là ma
trận rút gọn;
không âm;
Mỗi hàng chứa ít nhất một
phần tử 0;
hoặc mỗi cột gọi là hằng số rút gon;
Mỗi cột chứa ít nhất một
phần tử 0;
Thủ tục Từ ma trận chi phí tiến hành bớt đi các phần tử của mỗi dòng và của mỗi cột đi một hằng số: Các phần tử của ma trận Hàng số trừ ở mỗi dòng
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
Các phần tử của ma trận
Nhận xét Ma trận rút gọn:
không âm;
Mỗi hàng chứa ít nhất một
Input: ma trận chi phí C Output:
phần tử 0;
Mỗi cột chứa ít nhất một
phần tử 0;
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
Tìm phần tử nhỏ nhất của
dòng: ví dụ là r
Trừ tất cả các phần tử trên
Input: ma trận chi phí C Output: a. Rút gọn dòng Khởi tạo: Sum = 0 Ứng với mỗi dòng:
dòng bởi phần tử r
Sum = Sum + r
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
3
a. Rút gọn trên dòng
4
16
Input: ma trận chi phí C Output:
7
25
3
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
3
a. Rút gọn trên dòng
4
16
Input: ma trận chi phí C Output:
7
25
3
Sum = 58
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
Sum = 58
b. Rút gọn trên cột
Input: ma trận chi phí C Output:
8
15
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
Sum = 58
b. Rút gọn trên cột
Input: ma trận chi phí C Output:
8
15
Sum = 81
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
Thủ tục
thủ tục rút gọn hàng) Ứng với mỗi cột:
b. Rút gọn cột Khởi tạo: Sum = Sum (từ
Tìm phần tử nhỏ nhất của cột:
ví dụ c;
Trừ tất cả các phần tử trên cột
Input: Ma trận chi phí C Output:
bởi phần tử c Sum = Sum + c
ma trận rút gọn; tổng hằng số rút gọn.
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
2. Thủ tục chọn cạnh phân nhánh
3. Thủ tục phân nhánh
4. Thủ tục chọn hai cạnh cuối cùng
Thuật giải
2. Thủ tục chọn cạnh phân nhánh
Thủ tục
Ý tưởng Chọn cạnh phân nhánh (r,s) sao cho cận dưới của tập phân nhánh không chứ cạnh(r,s) tăng lớn nhất Input: Ma trận rút gọn Output: Cạnh phân nhánh (r,s)
Thuật giải
2. Thủ tục chọn cạnh phân nhánh
Thủ tục
=1,…,n) tính Xác định:
Thủ tục Khởi tạo: 𝛼 := −∞ Với mỗi cặp i, j với Cij = 0 (i,j
Input: Ma trận rút gọn Output: Cạnh phân nhánh (r,s)
• minr = min {Ci h :h ≠ j} (tính giá trị nhỏ nhất trên hàng i) • mins = min{Ch j :h ≠ j} (tính giá trị nhỏ nhất trên cột j)
Nếu 𝜶 < minr + mins, • 𝜶 := minr + mins, • r = i, s = j;
Thuật giải
2. Thủ tục chọn cạnh phân nhánh
r = 6, s = 3
Thủ tục Thủ tục
𝛼 = 48
Input: Ma trận rút gọn Output: Cạnh phân nhánh (r,s)
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
2. Thủ tục chọn cạnh phân nhánh
3. Thủ tục phân nhánh
4. Thủ tục chọn hai cạnh cuối cùng
Thuật giải
3. Thủ tục phân nhánh
r = 6, s = 3
Giả sử ở bước 2 đã
P
(81)P1
chọn cạnh (r,s) để phân
(6,3)
nhánh thì đặt:
P2
P1 -hành trình đi qua (r,s)
P2 không đi qua (r,s)
Thủ tục
Thuật giải
3. Thủ tục phân nhánh
rút gọn)
Giảm cấp ma trận: Loại hàng r, Loại cột s.
a. Thủ tục trên P1 Cận dưới là sum (giá trị từ thủ tục
Ngăn cấm tạo hành trình con: Cấm (s, r) gán:Csr = ∞ Nếu (r,s) là cạnh phân nhánh thứ hai trở đi thì phải xét các cạnh đã chọn nối trước và sau cạnh (r,s) thành dãy nối tiếp các cạnh như:
(i,j) …(r,s)…(k,h) thì cấm (h,j) tức Ch i = ∞
a. Thủ tục trên P1 Rút gọn ma trận chi phí Và tính cận dưới: sum += tổng hằng số rút gọn => Tiếp tục thực hiện thủ tục phân nhánh theo nhánh này
Thuật giải
3. Thủ tục phân nhánh
a. Thủ tục trên P1
Thuật giải
3. Thủ tục phân nhánh
Thủ tục
Giả sử ở bước 2 đã
rút gọn)
chọn cạnh (r,s) để phân
Cấm cạnh (r,s) bằng Cr s = ∞ Thực hiện thủ tục rút gọn ma
nhánh thì đặt:
trận chi phí Tính cận dưới:
P1 là hành trình đi qua (r,s)
P2 không đi qua (r,s)
b. Thủ tục trên P2 Cận dưới là sum (giá trị từ thủ tục
sum += tổng hằng số rút gọn => Tiếp tục thực hiện phân nhánh theo nhánh này
Thuật giải
3. Thủ tục phân nhánh
b. Thủ tục trên P2
Thuật giải
1. Thủ tục rút gọn để tính cận dưới
2. Thủ tục chọn cạnh phân nhánh
3. Thủ tục phân nhánh
4. Thủ tục chọn hai cạnh cuối cùng
Thuật giải
4. Thủ tục chọn hai cạnh cuối cùng
Thủ tục
Thủ tục Sau khi đã chọn n-2 cạnh, chúng ta phải chọn tiếp hai cạnh còn lại.
Lúc này ma trận rút gọn bậc hai có 1 trong hai dạng:
Ví dụ minh họa
ĐS
P
(81)P1
(6,3)
(81)P11
(4,6)
(84)P111
(2,1)
(129) P2
(113)P12
(1,4)
(101)P112
(104)P1111
(112)P1112
(5,1)
(127)P1122
(103)P1121
(1,4)
(114)P11212
(104)P11211
