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ápdụng để giải các bài toán tìm lờigiải
tốiưu.
•
Phương
pháp
:
Phương
pháp
:
–Xuất phát từmộtphương án nào đó.
–Áp dụng một phép biếnđổilênphương án hiệnhànhđể
đượcmộtphương án mớitốthơn.
–Lặplạiviệcápdụng phép biếnđổilênphương án hiện
hành cho đến khi không còn có thểcảithiệnphương án
đượcnữa.
•
Thông
thường
một
biến
đổi
chỉ
thay
đổi
một
bộ
•
Thông
thường
một
biến
đổi
chỉ
thay
đổi
một
bộ
phậnnàođócủaphương án hiệnhànhđể đượcmột
phương án mới, nên gọi là phép biếnđổiđịaphương Æ
kỹthuật tìm kiếmđịaphương.
Phạm Thế Bảo
14/04/2008
2
Bài toán cây phủtốithiể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ố
.
V{
đỉnh
}
và
E{
cạnh
},
các
cạnh
đều
có
trọng
số
.
Cây T có tậphợp các nút là V đượcgọi là cây phủ
(spanning tree) củađồ thịG.
•Cây phủtốithiểu, chính là một cây phủcủaGmà
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
–
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 đượcsắpthứ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 c
d
=5 Æta có cây
mới có giá trị.
d
e
3
2
6
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
72
4
Tổng giá trịbằng
14/04/2008
3
•Lạithêmcạ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
72
3Tổng giá trịbằng 16
cạn
h
ae=
7
Æ
c
â
y
mới có giá trị.
•Áp dụng tiếptụcsẽ
không cảithiệnÆ
dừn
g
.
d
e
b
a
c
4
3Tổng giá trịbằng
g
Phạm Thế Bảo
c
d
e
3
2
Cây tối
thiểu
Bài toán ngườigiaohàng
•Phương pháp:
ấ
–
Xu
ất
phá
t
từmộ
t
chu trình nào đó.
–Bỏđihaicạnh có độ dài lớnnhất không kềnhau.
Nối các đỉnh còn lạivới nhau sao cho vẫntạora
một chu trình đủ.
–Tiếptục quá trình biếnđổitrênchođến khi nào
không cảithiệnđượcnữathì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ộtphương án ban
đầu: chu trình (a b c d e
a)
có
giá
trị
là
25
b
a
3
4
4
a)
có
giá
trị
là
25
.c
d
e
3
2
6
8
7
6
5
b
a
c
3
7
5
4
Phạm Thế Bảo
d
Đồ thịG
d
e6
5
Phương án ban đầu
•Bỏhai cạnh lớnnhất
không kềnhau là ae và
cd. Nốiavớidvàe
vớicÆchu trình mới
(a b c e d a), giá trịlà
23
b
a
c
3
2
8
4
23
.
•Bỏtiếpcevàab.Nốia
vớicvàbvớieÆchu
trình mới(acbeda),
giá trịlà 19.
ế
Æ
e
d6
Phương án thứhai
c
a
b
34
•Ti
ế
ptục
Æ
giá trịtăng
Ædừng
Phạm Thế Bảo
e
d
2
6
3
Phương án thứba
Kếtquả