BÀI TOÁN
TÌM C P ĐI M G N NH TẶ Ể Ầ Ấ
Nhóm 3:
Huỳnh Minh Trí
Nguyễn Ngọc Nga
Trương Mỹ Thu Thảo
Nguyễn Thị Hồng Yến
GV hướng dẫn:
PGS, TS. Trần Cao Đệ

Gi i thi uớ ệ
Gi i thi u v hai thu t toán đ gi i quy t yêu c u “Tìm c p đi m ng n nh t trong m t ph ng”. ớ ệ ề ậ ể ả ế ầ ặ ể ắ ấ ặ ẳ
Ý t ng, tính đ ph c t p, th c nghi m trên cùng m t b d li uưở ộ ứ ạ ự ệ ộ ộ ữ ệ
So sánh th i gian th c hi n ờ ự ệ
K t lu n thu t toán t i u : Brute forte ho c Plane sweep.ế ậ ậ ố ư ặ

Kho ng cách gi a hai đi mả ữ ể
1
x
2
x
2
y
1
y
( )
11
, yx
( )
22

K THU T TR T PH NGỸ Ậ ƯỢ Ẳ
S p x p các đi m tăng d n theo xắ ế ể ầ
Dùng đ ng th ng th ng đ ng tr t t trái sang ph iườ ẳ ẳ ứ ượ ừ ả
–
C p đi m g n nh t trong t p h p các đi m đã quét qua (a,b) v i kho ng cách d(a,b)ặ ể ầ ấ ậ ợ ể ớ ả
–
M t t đi n S ch a các đi m đã quét qua theo th t t a đ y.ộ ự ể ứ ể ứ ự ọ ộ
–
Lo i b kh i S các đi m r th a: x(p)-x(r) > dạ ỏ ỏ ể ỏ
–
Tìm đi m q trong S sao cho d(p,q)<d. C p nh t l i a=p, b=q và d=d(p,q)ể ậ ậ ạ
–
Insert p vào S.

Tr t t trái sang ph iượ ừ ả

Tìm c p đi m g n nh tặ ể ầ ấ
Cho n (n>=2) đi m trong m t ph ng 2 chi u đ c l u tr trong m t m ng a v i m i đi m th i có t a đ (x,y).ể ặ ẳ ề ượ ư ữ ộ ả ớ ỗ ể ứ ọ ộ
Tìm m t c p đi m (p, q) g n nhau nh t b ng cách dùng thu t toán ộ ặ ể ầ ấ ằ ậ Brute forte và, Plane sweep.

Tìm c p đi m g n nh t ặ ể ầ ấ
V i hai đ nh b t kỳ a(xa , ya), b(xb , yb) trong t p n đ nh thì kho ng cách gi a chúng làớ ỉ ấ ậ ỉ ả ữ
22
)()(
abab
yyxx −+−

Ý tưởng:
-
Khởi tạo vị trí đỉnh đầu tiên i=1; Khoảng nhỏ nhất dmin=∞;

Gi i thu t Plane sweepả ậ

Gi i thu t Plane sweepả ậ
Đ u tiên tr t t nút 1 qua ph i g p nút 2 thì đo n 12 tìm th y đ u tiên là đo n g n nh t.ầ ượ ừ ả ặ ạ ấ ầ ạ ầ ấ
Ti p theo tr t t i nút 3 thì đo n 12 c ng là đo n g n nh t t ng t nút 4 và nút 5. ế ượ ớ ạ ủ ạ ầ ấ ươ ự
Hình ch nh t có chi u ngang d và hình tròn có bán kính d v n ch a thay đ i. C th ti p t c tr t hình ch nh t v i bán d m i (d’) sang ữ ậ ề ẫ ư ổ ứ ế ế ụ ượ ữ ậ ớ ớ
đi m 7 …ể

Gi i thu t Plane sweepả ậ
Nh ng đ n nút 6 thi trong ph n giao gi a hình ch nh t và hình tròn tâm nút 6 có ch a 2 đi m là 4 và 5. Khi đó gi i thu t so sánh chi u dài gi a ư ế ầ ữ ữ ậ ứ ể ả ậ ề ữ
nút 64 v i d và nút 65 v i d. Xét th y kho ng cách gi a 2 nút 6, 5 nh h n d nên c p nh t l i d là d’ và lo i b nút 1,2 ra, c p nh t l i nút 5,6. Nút ớ ớ ấ ả ữ ỏ ơ ậ ậ ạ ạ ỏ ậ ậ ạ
3 không xét vì n m ngoài vùng giao.ằ

Đ ph c t pộ ứ ạ
S p x p các đi m theo O(n logn)ắ ế ể
Thêm/xóa
m t ph n t vào/t S là O(logn)ộ ầ ử ừ
Th c hi n tìm ki m ph m vi trong S là O(logn)ự ệ ế ạ
Th c hi n tìm ki m khi quét qua n đi m O(nlogn)ự ệ ế ể
⇒
T ng th i gian th c hi n O(nlogn)ổ ờ ự ệ

Rõ ràng chúng ta thấy chương trình sẽ
tốn nhiều thời gian là lúc xét trong
phần giao nói trên (có nút 4 và 5) nếu
có nhiều nút thì phải duyệt hết các nút
này. Nếu trong tất cả các phần giao
không có nút nào thì trượt đến nút
cuối cùng sẽ tốn thời gian là O(n).
Độ phức tạp

hình ch nh t đ u tiên (x u nh t >n).ữ ậ ầ ấ ấ

Demo và code (Pascal):

Demo

Code (xem ph l c đính kèm)ụ ụ

K t Lu nế ậ
»
Tùy theo b trí các đi m trên m t ph ng mà ố ể ặ ẳ
gi i thu t ch y nhanh hay ch mả ậ ạ ậ
»
Gi i thu t này và các gi i thu t nói trên s ả ậ ả ậ ở ẽ
có th i gian ch y khác nhau tùy theo b trí ờ ạ ố
các đi m. ể
»
Nh v y rõ ràng gi i thu t Plane sweep t i ư ậ ả ậ ố
u h n Brute forteư ơ

K t Lu nế ậ
»
Tuy nhiên chúng ta cũng nên l u ý vi c t ư ệ ổ
ch c l u tr d li u nh th nào cho hi u ứ ư ữ ữ ệ ư ế ệ
qu đ gi m đi s ph c t p t vi c xây ả ể ả ự ứ ạ ừ ệ
d ng không gian l u tr và vi c tìm ki m.ự ư ữ ệ ế
»
M t khác, d li u nhi u hay ít thì các gi i ặ ữ ệ ề ả
thu t cũng có th ch y v i th i gian khác ậ ể ạ ớ ờ
nhau. Ví d nh t ch c tìm ki m theo cây ụ ư ổ ứ ế