Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Các giải thuật hình học - Trần Cao Đệ

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Các giải thuật hình học - Trần Cao Đệ

1. Tổ chức dữ liệu tìm kiếm 2 chiều theo phạm vi ⚫ Tổ chức dữ liệu lưu trữ ⚫ Mỗi nút của cấu trúc tự điển chứa các phần chính (cây T) lưu trữ tử (x,y) – Một phần tử có tọa độ – Cấu trúc chính : Cây x(v), y(v) và giá trị TKNP (cân bằng) theo x. element(v), VÀ Kí hiệu T – Cây tìm kiếm một chiều – Cấu trúc phụ: gắn vào theo y, kí hiệu T(v) chứa mỗi nút của cấu trúc các phần tử như cây con chính là một cây TKNP của T gốc v với các khóa (cân bằng) theo y. kí là tọa độ y. hiệu T(v) là cây gắn với nút v. 11
2. Ví dụ minh họa cây tìm kiếm 2 chiều theo phạm vi ⚫ Các phần tử (30,20), (15,40), (35,2), (5,33), (20,50) 20 30 2 40 40 33 50 15 35 50 33 2 5 20 33 50 Cấu trúc chính là một cây TKNP (cân bằng) theo tọa độ x 12
3. Xây dựng cây TK 2 chiều ⚫ Cây tìm kiếm hai chiều theo phạm vi chứa n nút cần dùng không gian O(nlogn) và có thể xây dựng trong thời gian O(nlogn) – Cấu trúc chính dùng O(n) không gian – Cấu trúc phụ dùng không gian tỷ lệ với số nút lưu trữ. Một nút v trên cây T có thể có O(logn) tiền bối → v được copy O(logn) lần → Không gian lưu trữ O(nlogn) – Thời gian xây dựng cũng là O(nlogn). 13
4. Tìm kiếm 2 chiều theo phạm vi FindAllInRange(x1,x2,y1,y2) ⚫ Tìm một xe mô tô giá ⚫ Các nút biên chia làm 3 25tr→40tr, tiêu thụ xăng 40- nhóm 50km/lít. – Nút giữa: giao của P1 và ⚫ Giải thuật P2 – Tìm trên cấu trúc chính – Nút trái: nút thuộc P1 [x1,x2] nhưng không thuộc P2 – Khi tìm thấy một nút trong v, tìm đệ qui trên cấu trúc – Nút phải: thuộc P2 nhưng phụ [y1,y2] không thuộc P1. ⚫ Nút phân phối (allocation ⚫ Với mỗi nút phân phối: tìm node) : nút trong+nút con trên cấu trúc phụ [y1,y2]. của nút biên. 14
5. Ví dụ minh họa Nút phân phối Nút biên
6. Giải thuật tìm kiếm ⚫ 2DTreeRangeSearch(x1,x2,y1,y2,v,t) – Input: cho các khóa x1,x2,y1,y2 và cấu trúc chính T; v là nút trên T; t là kiểu của nút – Output: tập hợp các nút v mà các nút thuộc cây con gốc v có tọa độ thỏa mãn x1 ≤ x ≤ x2 và y1 ≤ y ≤ y2 16
7. 2DTreeRangeSearch(x1,x2,y1,y2,v,t){ If T.isExternal(v) return ; If (x1 ≤ x(v) ≤ x2 ) { if (y1 ≤ y(v) ≤ y2 ) M=[element(v)] else M= ; if (t==“left”){ L=2DTreeRangeSearch(x1,x2,y1,y2,T.leftChild(v),”left”) R=1DTreeRangeSearch(y1,y2,T.rightChild(v)) } else if (t==“right”){ L=1DTreeRangeSearch(y1,y2,T.leftChild(v)) R=2DTreeRangeSearch(x1,x2,y1,y2,T.rightChild(v),”right”) } else { //t==“middle” L=2DTreeRangeSearch(x1,x2,y1,y2,T.leftChild(v),”left”) R=2DTreeRangeSearch(x1,x2,y1,y2,T.rightChild(v),”right”) } }
8. else { //của if đầu tiên M= ; if (x(v) x2 L=2DTreeRangeSearch(x1,x2,y1,y2,T.leftChild(v),t); R= ; } } Return L U M U R; Gọi lần đầu tiên: 2DTreeRangeSearch(x1,x2,y1,y2,T.root(),”middle”);
9. Hiệu quả của giải thuật ⚫ Giải thuật tìm kiếm 2 chiều theo phạm vi chứa n phần tử lấy thời gian O(log2n+s) với s là số phần tử trả về sau tìm kiếm. ⚫ Chứng minh: xem trang 554-Goodrich – O(logn) nút biên – Mỗi nút phân phối (allocation) v duyệt 1 chiều mất O(lognv+sv), nv là số nút trên cây Tv (cấu trúc phụ) – Có O(logn) nút allocation → Thời gian O(log2n+s) 19
10. Cây tứ phân (Quadtrees) ⚫ Trong các bài toán xử lí ảnh r – Xử lí các điểm có tọa độ hạn chế (2048x2048) – Các điểm tập trung r3 r2 r4 r1 ⚫ Xét các điểm trong mặt phẳng (x,y) ⚫ Cây tứ phân là cây – mỗi nút trong ứng với một vùng hình vuông R – Các nút con của một nút tương ứng với 4 hình vuông con ở 4 góc của R. – Các nút được phân chia một cách đệ qui để mỗi vùng chứa 1 điểm. Vùng chứa 1 điểm coi như là một nút ngoài. 20
11. Ví dụ d b a c e k m l i j f g h Nút trong Nút ngoài 21
12. Hiệu quả cây tứ phân ⚫ Nếu có hai điểm rất gần nhau thì thời gian xây dựng cây sẽ rất lâu ⚫ Thiết kế một biên (bound) D, chiều sâu giới hạn. ⚫ Thời gian xây dựng cây tứ phân cho n điểm trong mặt phẳng là O(D*n), D là chiều sâu giới hạn của cây. 22
13. Tìm kiếm trên cây tứ phân ⚫ Tập S các điểm – Nếu R  A: tất cả các nút lá của cây gốc r đều là kết ⚫ Giả sử câu truy vấn là hình quả. chữ nhật A – Nếu R  A ≠ : tìm kiếm ⚫ Kết quả tìm kiếm là tất cả đệ qui trên mỗi con v của các điểm thuộc S nằm trong nút r. A. ⚫ Thời gian tìm kiếm là O(D*n), với n là số nút ⚫ Tìm kiếm ngoài. – Bắt đầu từ gốc r của cây. – Giải thuật tìm kiếm có thời – Nếu vùng R (tương ứng với gian > thời gian của giải r)  A =  : dừng thuật tìm brute forte! – Trong thực hành thì TK trên cây tứ phân nhanh hơn tìm kiếm brute forte! 23
14. k-d-Trees ⚫ Cây tứ phân không thể ⚫ Cây k-d: là cây nhị tổng quát hóa cho phân được xây dựng nhiều chiều. khá tương tự với cách – KG 3 chiều mỗi nút có 8 xây dựng cây tứ phân. nút con; – Mỗi nút tương ứng với – KG d chiều, mỗi nút có một vùng hình chữ nhật d 2 nút con. – Phân chia không gian chứa các điểm thành các hình chữ nhật, mỗi hình chứa 1 điểm. 24
15. Hai loại cây k-d ⚫ Dựa trên vùng (region ⚫ Dựa trên điểm (point- based) based) – Chia vùng HCN thành – Chia theo phân phối hai HCN theo trục dài điểm. Mỗi HCN chứa nhất. Nếu có nhiều trục phân nửa số điểm dài bằng nhau thì chia xoay vòng theo các trục. 25
16. e g c p j f n l h a k m i b o d
17. Tìm kiếm gần nhất (nearest neigbor searching) ⚫ Cho một điểm p, ⚫ truy vấn: tìm điểm gần p nhất: – Tìm kiếm (từ nút gốc) nút ngoài v tương ứng với vùng R nhỏ nhất chứa p. – Các điểm thuộc R và thuộc các vùng tương ứng với nút anh em của v đều được so sánh để tìm điểm q gần nhất hiện tại. – Định nghĩa hình tròn s(p,pq) – Duyệt cây tìm các vùng giao với s khác rỗng – Trong khi duyệt nếu tìm thấy điểm q’ gần p hơn q, thay q=q’. 27
18. Hiệu quả tìm kiếm ⚫ Tìm kiếm điểm gần nhất – Trong trường hợp xấu nhất: O(n) – Trung bình: O(logn) ⚫ Nhiều cải tiến giải thuật rất có ý nghĩa. 28
19. Kỹ thuật trượt phẳng (Plane sweep technique) ⚫ Kỹ thuật trượt/quét phẳng áp dụng vào nhiều bài toán hình học. Ý tưởng: 1 chiều hóa bài toán 2 chiều 29
20. Giao đoạn thẳng trực giao ⚫ Bài toán tổng quát: Cho n ⚫ Chuyển từ 2D sang 1D: đoạn thẳng, tìm giao của tất – Mỗi đọan thẳng thẳng đứng cả các cặp đoạn thẳng v, xét đường thẳng l(v) đi – Brute forte: xét n(n-1)/2 ngang qua v. cặp, thời gian O(n2) – Xét đường l với các đoạn ⚫ Bài toán hạn chế: cho n thẳng nằm ngang → 1D đoạn thẳng trực giao, nghĩa hóa (v,y), v cố định là các đoạn song song với ⚫ Gọi S(v) là tập hợp các điểm ox hoặc oy. là giao của l(v) và các đoạn thẳng nằm ngang. Thì việc tìm giao điểm của v và các đoạn nằm ngang tương đương với việc tìm kiếm 1 chiều theo y. 30
21. Giải thuật trượt phẳng ⚫ Cho trượt đường thẳng l thẳng đứng từ trái sang phải. ⚫ Khi trượt, lưu các đoạn đang có giao điểm với l vào tự điển S (tổ chức có thứ tự theo tọa độ y) ⚫ Các sự kiện và hành động: Sự kiện Hành động Gặp đầu trái của đoạn ngang h Thêm h vào tự điển S Gặp đầu phải của đoạn ngang h Loại h khỏi tự điển S Gặp đoạn thẳng thẳng đứng v Thực hiện tìm kiếm theo phạm vi trên S với phạm vi là tọa độ y 31 của hai đầu điểm v
22. Hiệu quả ⚫ Thời gian thực hiện trượt phẳng để tìm giao điểm của n đoan thẳng trực giao cho trước là O(nlogn+s), với s là số giao điểm. 32
23. Tìm một cặp điểm gần nhất ⚫ Cho tập gồm n điểm ⚫ Brute forte: O(n2) ⚫ Tìm một cặp điểm (p,q) ⚫ Trượt phẳng: gần nhau nhất. – Dùng 1 đường thẳng thẳng đứng, trượt từ trái ⚫ Khoảng cách giữa 2 sang phải từ điểm trái điểm: nhất. d(a,b)=sqrt((x -x )2+(y -y )2) a b a b – Lưu giữ các cặp điểm gần nhất và các điểm gần với đường quét 33
24. Ý tưởng ⚫ Khi quét ngang qua 1 điểm – Loại bỏ khỏi S các điểm r ta lưu trữ: thỏa: x(p)-x(r) > d – Cặp điểm gần nhất trong – Tìm điểm q trong S sao cho tập hợp các điểm đã quét d(p,q)<d. Cập nhật lại a=p, qua (a,b) với khoảng cách b=q và d=d(p,q) d(a,b) – Insert p vào S. – Một tự điển S chứa các điểm đã quét qua theo thứ tự tọa độ y. ⚫ Như vậy, khi quét ngang 1 điểm p phải thực hiện các phép toán sau: 34
25. Vùng khảo sát d Đường quét d
26. B(p,d) C(p,d) q p Nhận xét ⚫ Rõ ràng mỗi lần quét – Điểm q cần tìm thuộc qua một điểm p ta chỉ giao của B(p,d) với nửa hình tròn (p,d) xét các điểm trong S và cần tìm điểm q với ⚫ Với mỗi điểm thuộc S, d(p,q)<d. thực hiện tìm kiếm theo phạm vi với các khóa là – Các điểm cần xét thuộc hình chữ nhật B(p,d) tọa độ y. kích thước dx2d ⚫ Tổ chức cây tìm kiếm là AVL hoặc red-black lưu trữ S. 36
27. B(p,d) C(p,d) q p Định lý ⚫ Hình chữ nhật dx2d chứa nhiều nhất là 6 điểm sao cho khoảng cách giữa hai điểm bất kỳ ít nhất là d. ⚫ Hệ quả: thời gian tìm kiếm trong S để xác định các điểm thuộc B(p,d) là O(logn+6) đó là thời gian 1DRangeSearchTree. 37
28. Thời gian thực hiện GT tìm cặp điểm gần nhất ⚫ Sắp xếp các điểm theo x – Nếu X(FirstInTrip) < x(lastInTrip)- tăng dần, mục đích d, thì ⚫ ta loại FirstInTrip – Xác định điểm kế tiếp được ⚫ FirstInTrip=Next(FirstInTrip) xử lí (được quét) ⚫ Thời gian – Xác định điểm bị loại khỏi – Sắp xếp các điểm O(nlogn) S. – Thêm/xóa một phần tử vào/từ S là ⚫ Gọi FirstIntrip và LastInTrip O(logn) là điểm đầu tiên và cuối – Thực hiện tìm kiếm phạm vi trong cùng trong các điểm đang S là O(logn) xét (theo thứ tự) – Thực hiện tìm kiếm khi quét qua n điểm O(nlogn). ⚫ Thời gian tổng cộng O(nlogn) 38
29. Tìm bao lồi (convex Hull) ⚫ Cho n>3 điểm (không – Đa giác đơn: giao của thẳng hàng) trong mặt hai cạnh bất kỳ (nếu có) là đỉnh của đa giác. phẳng, tìm đa giác lồi: – Đa giác lồi nếu nó là đơn – có các đỉnh thuộc tập và mọi góc trong đều các điểm đã cho, nhỏ hơn . – chứa tất cả các điểm đã cho. ⚫ Đa giác là một chuỗi khép kín các đỉnh đa giác. 39
30. Hướng của 3 điểm ⚫ Cho một bộ 3 điểm (p,q,r) r – (p,q,r) là “cua trái” nếu chúng có hướng ngược chiều kim đồng hồ, tức là góc (p,q,r) < nằm bên trái q pq. – (p,q,r) là “cua phải” nếu chúng có hướng cùng chiều p kim đồng hồ, tức là góc (p,q,r) < nằm bên phải pq. r – nếu (p,q,r)= thì 3 điểm q thẳng hàng. p 40
31. Phân tích toán học ⚫ Cho ba điểm p1(x1,y1), p2(x2,y2), p3(x3,y3) ⚫ Xét định thức x1 y1 1 ⚫ (p1,p2,p3)= x2 y2 1 x3 y3 1 Định lý: (p1,p2,p3) là cua trái, cua phải hoặc thẳng hàng tùy theo dương, âm hoặc bằng 0 tương ứng. 41
32. Kiểm tra hai đoạn thẳng giao nhau ⚫ Cho hai đoạn thẳng s1=p1q1,s2=p2q2. s1 và s2 giao nhau nếu một trong các điều kiện sau thỏa: 1. (p1,q1,p2), (p1,q1,q2) khác hướng VÀ (p2,q2,p1), (p2,q2,p2) khác hướng. 2. (p1,q1,p2), (p1,q1,q2), (p2,q2,p1) và (p2,q2,q1) thẳng hàng, VÀ hình chiếu lên trục x của s1 và s2 là giao nhau, VÀ hình chiếu của s1 và s2 lên trục y là giao nhau. 42
33. Tính chất cơ bản của bao lồi ⚫ Vùng R là lồi nếu hai điểm – Điểm p là một đỉnh của bao p,q thuộc R thì cả đoạn lồi nếu và chỉ nếu tồn tại thẳng pq thuộc R. một đường thẳng l đi qua p sao cho tất cả các điểm ⚫ Định lý: Cho S là tập hợp khác p thuộc về nửa mặt điểm và H là bao lồi của S, phẳng xác định bởi l ta có: – Điểm p không phải là đỉnh – Cặp (a,b) làm thành một của H nếu và chỉ nếu p cạnh của H nếu và chỉ nếu chứa trong một tam giác có tất cả điểm khác thuộc nửa 3 đỉnh là 3 điểm khác trong mặt phẳng xác định bởi S hoặc p thuộc một đoạn đường thẳng ab. thẳng nối hai đỉnh khác. 43
34. Hệ quả ⚫ Các điểm sau đây sẽ luôn nằm trên biên của bao lồi – Điểm có tọa độ x nhỏ nhất – Điểm có tọa độ x lớn nhất – Điểm có tọa độ y nhỏ nhất – Điểm có tọa độ y lớn nhất 44
35. Giải thuật “gói quà” (gift wrapping) ⚫ Chọn điểm A(xmin,ymin), A là một đỉnh của bao lồi, gọi là điểm neo (anchor) B ⚫ Xét tia Ax ⚫ Quay tia Ax ngược chiều A kim đồng hồ cho đến khi gặp một điểm B. B là đỉnh kế tiếp A trên bao lồi. Thay A bởi B và tiếp tục quay tia Ax. ⚫ Cho đến khi điểm B tìm thấy trùng với điểm neo. B 45 A
36. Định lý ⚫ Cho tập S gồm các điểm trong mặt phẳng, a là một đỉnh của bao lồi H của S, điểm p là đỉnh kế tiếp trên bao lồi khi quay ngược chiều kim đồng hồ thì (a,p,q) là “cua trái” với mọi điểm q của S. ⚫ Gọi C(a) hướng của (a,p,q), định nghĩa: C(a).isLess(p,q) nếu và chỉ nếu (a,p,q) là một “cua trái” 46
37. Hiệu quả của giải thuật “gói quà” ⚫ Cho n là số điểm, h là số ⚫ Gọi p0,p1, ,ph-1 là các đỉnh đỉnh của bao lồi (h≤n). Thời bao lồi. gian thực hiện “gói quà” là ⚫ Thời gian tìm điểm neo p0 là O(hn), trong trường hợp xấu O(n) nhất h=n thì thời gian gói ⚫ Ở bước i: thời gian tìm đỉnh quà là O(n2). kế tiếp (tính C(pi-1)) là O(n) ⚫ Có h đỉnh phải tìm vậy thời gian là O(hn) ⚫ Trong trường hợp xấu nhất h=n thì thời gian “gói quà” là O(n2). 47
38. Giải thuật quét Graham (Graham Scan) ⚫ Cho tập P các điểm trong – Xét các điểm p P-{A} theo mặt phẳng thứ tự trên ⚫ Thêm p vào H nếu H có ít ⚫ Giải thuật tìm bao lồi H hơn 2 điểm hoặc Nếu p – Tìm một điểm A nằm trên hợp với hai điểm trước đó bao lồi, gọi là điểm neo; ví làm thành một cua trái dụ điểm có tọa độ y nhỏ ⚫ Xóa điểm cuối cùng trong nhất. Thêm A vào H H trong trường hợp ngược lại và lặp lại test đối với p – Sắp xếp các điểm P-{A} theo C(A), tức là góc của hợp phương ngang (tia Ax). 48
39. Giải thuật quét Graham Scan(S,a){ S.Append(a) //Input: S là danh Prev=S.first();//prev=a sách có thứ tự Curr=S.after(prev); theo chiều ngược Do{ chiều kim đồng next=S.after(curr) if isLeftturn(prev,curr,next) hồ; a là điểm neo prev=curr //Output: S chứa các else{ đỉnh của bao lồi S.remove(curr); (các đỉnh còn lại prev=S.before(prev); sau khi thực hiện } giải thuật) curr=S.after(prev) } while curr!=S.last() S.Remove(S.last());//xóa điểm neo a } 49
40. Hiệu quả của giải thuật quét Graham ⚫ Tìm điểm neo O(n) ⚫ Sắp xếp các điểm O(nlogn) ⚫ Giải thuật quét thực hiện vòng lặp do while nhiều nhất là 2n, mỗi lần mất O(1) ⚫ Vậy thời gian thực hiện giải thuật quét Graham là O(nlogn). 50
41. Cài đặt giải thuật quét Graham ⚫ Trang 583-586, Algorithm Design, Goodrich. 51
42. Hết chương 5