Bài giảng Phân tích và thiết kế thuật toán - Phạm Thế Bảo - Chương 11: Tìm kiếm cục bộ (Local Search)

14/04/2008
1
TÌM KIẾM CỤC BỘ 
(ĐNA PHƯƠNG)
(LOCAL SEARCH)
Phạm Thế Bảo
Khoa Toán – Tin học 
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung
• Thường được áp dụng để giải các bài toán tìm lời giải
tối ưu.
• Phương pháp:
– Xuất phát từ một phương án nào đó.
– Áp dụng một phép biến đổi lên phương án hiện hành để
được một phương án mới tốt hơn.
– Lặp lại việc áp dụng phép biến đổi lên phương án hiện
hành cho đến khi không còn có thể cải thiện phương án
được nữa.
• Thông thường một phép biến đổi chỉ thay đổi một bộ
phận nào đó của phương án hiện hành để được một
phương án mới, nên gọi là phép biến đổi địa phươngÆ
kỹ thuật tìm kiếm địa phương.
Phạm Thế Bảo
14/04/2008
2
Bài toán cây phủ tối thiểu
• Cho G=(E,V) là một đồ thị vô hướng liên thông,
V={đỉnh} và E={cạnh}, các cạnh đều có trọng số.
Cây T có tập hợp các nút là V được gọi là cây phủ
(spanning tree) của đồ thị G.
• Cây phủ tối thiểu, chính là một cây phủ của G mà
tổng độ dài (trọng số) các cạnh là bé nhất.
• Ứng dụng:
Thiết kế mạng lưới giao thông– .
– Mạng máy tính.
– Đường dây điện.
– …
Phạm Thế Bảo
• Ví dụ: cho đồ thị có 5 đỉnh, và độ dài như hình.
Các cạnh được sắp thứ tự: ad, ab, be, bc, ac, cd,
bd, de, ae ,ce.
Cây xuất phát với giá trị là 20
Thêm cạnh ad=2 (nhỏ nhất),
b
a
c
3
4
3 6
4
bỏ cạnh cd=5 Æ ta có cây
mới có giá trị.
d
e
2 8
7
6
5
Đồ thị G
b
a
c
4
4
Tổng giá trị bằng 20
b
4
Phạm Thế Bảo
d
e
7
5
a
c
d
e
4
7
2
Tổng giá trị bằng
14/04/2008
3
• Lại thêm cạnh ab=3,
bỏ cạnh bc=4 Æ cây
mới giá trị bằng 16.
• Thêm cạnh be=3, bỏ
h 7 Æ â
b
a
c
4
7
2
3
Tổng giá trị bằng 16
cạn ae= c y
mới có giá trị.
• Áp dụng tiếp tục sẽ
không cải thiện Æ
dừng.
d
e
b
a
c
4
3
Tổng giá trị bằng
Phạm Thế Bảo
d
e
3
2Cây tối
thiểu
Bài toán người giao hàng
• Phương pháp:
ấ– Xu t phát từ một chu trình nào đó.
– Bỏ đi hai cạnh có độ dài lớn nhất không kề nhau.
Nối các đỉnh còn lại với nhau sao cho vẫn tạo ra
một chu trình đủ.
– Tiếp tục quá trình biến đổi trên cho đến khi nào
không cải thiện được nữa thì dừng.
Phạm Thế Bảo
14/04/2008
4
• Ví dụ: Xét bài toán TSP có 5 đỉnh như hình vẽ.
‰Xét một phương án ban 
đầu: chu trình (a b c d e 
a) có giá trị là 25
b
a
3
4
4
 . c
d
e
3
2
6
8
7
6
5
b
a
c
3
7
5
4
Phạm Thế Bảo
Đồ thị G
d
e 6
Phương án ban đầu
• Bỏ hai cạnh lớn nhất
không kề nhau là ae và
cd. Nối a với d và e
với c Æ chu trình mới
(a b c e d a), giá trị là
23
b
a
c
3
2
8
4
.
• Bỏ tiếp ce và ab. Nối a
với c và b với eÆ chu
trình mới (a c b e d a),
giá trị là 19.
ế Æ
e
d 6
Phương án thứ hai
c
a
b
3 4
• Ti p tục giá trị tăng
Æ dừng
Phạm Thế Bảo
e
d
2
6
3
Phương án thứ ba
Kết quả