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.

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â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

4
7
2
3
Tổ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
3
Tổng giá trị bằng
g
Phạm Thế Bảo
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

giá trị là 19.
ế
Æ
e
d
6
Phương án thứ hai
c
a
b
3
4
• 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ả