Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 4 - PGS.TS. Trần Cao Đệ
lượt xem 11
download
Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 4 nhằm giúp bạn đọc hiểu hơn về các vấn đề của giải thuật hình học như dữ liệu nhiều chiều, cây tìm kiếm phạm vi, tìm kiếm 1 chiều trong phạm vi, hiệu quả của giải thuật,... Tham khảo nội dung bài giảng để nắm bắt nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Phân tích và Thiết kế giải thuật nâng cao: Chương 4 - PGS.TS. Trần Cao Đệ
- Chương 4: Các giải thuật hình học Computational Geometry PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 1 2013
- Dữ liệu nhiều chiều Các giải thuật hình học Các bài toán thống kê, liên quan tới dữ liệu điều khiển cũng cần xử không gian đa chiều. lí dữ liệu nhiều chiều – Một điểm trong mặt Một số bài toán quan phẳng (x,y) trọng – Một điểm trong không – Tìm kiếm theo phạm vi gian (x,y,z) (range searching query) Các ứng dụng máy – Tìm bao lồi (convex hull) học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. 2
- Cây tìm kiếm phạm vi Một điểm trong không – Kết quả tìm kiếm là tất gian d chiều được biểu cả các điểm hình tròn ((xq,yq),r) diễn theo tọa độ bởi (x0,x1,…,xd-1). Giải thuật tìm kiếm thường tổ chức dữ liệu Tìm kiếm theo phạm vi theo cây cân bằng – gọi là tìm kiếm các điểm là cây TK phạm vi. trong một phạm vi nào đó. – Ví dụ tìm các điểm gần với (xq,yq) trong khoảng cách r. 3
- Tìm kiếm 1 chiều theo phạm vi Cho một tự điển (tập Giải thuật tìm kiếm hợp các phần tử) có 1DTreeRangeSearch(k1,k2,v) thứ tự – Nếu v là nút ngoài (V=NULL): dừng findAllInRange(k1,k2): – Nếu v là nút trong trả về các phần tử thỏa: Key(v)k2: tìm đệ qui trên cây con trái của v. 4
- Giải thuật 1DTreeRangeSearch 1DTreeRangeSearch(k1,k2,v){ if v.isExternal(v) return ; if (k1 ≤ key(v) ≤ k2) { L= 1DTreeRangeSearch(k1,k2,T.leftChild(v)); R= 1DTreeRangeSearch(k1,k2,T.rightChild(v)); return L U {element(v)} U R; } else if (key(v)
- 68 37 99 18 55 81 12 23 42 61 74 90 21 49 Cho k1=30, k2=80 Tìm kiếm 1DTreeRangeSearch(k1,k2,T.Root()) sẽ trả ra các nút nằm giữa hai nút ngoài màu đỏ ở trên.
- 68 37 99 18 55 81 12 23 42 61 74 90 21 49 Gọi P1 là đường đi khi tìm kiếm trên cây theo khóa k1 Gọi P2 là đường đi khi tìm kiếm trên cây theo khóa k2 Định nghĩa; – V là nút biên: nếu v là nút thuộc P1 hoặc P2 – V là nút trong: nếu v không là nút biên và v là nút thuộc cây con phải của nút thuộc P1 hoặc con trái của nút thuộc P2. – V là nút ngoài: nếu v không là nút trong cũng không là nút biên.
- Hiệu quả của giải thuật Định lý: Tìm kiếm 1 chiều theo phạm vi trên một cây TKNP cân bằng có chứa n nút cần: Không gian lưu trữ O(n) Thời gian thực hiện 1DTreeRangeSearch là O(logn+s) với s là số phần tử trả về sau tìm kiếm Thời gian thực hiện xóa một phần tử là O(logn) 8
- Chứng minh Không duyệt nút ngoài nào – Các nút trong nằm trên j cây con rời nhau có nút gốc Có nhiều nhất là 2h+1 nút là con của nút biên và biên j ≤ 2h. Mỗi khi duyệt nút trong v, tất – Gọi si là số nút của cây Ti ta cả các cây con Tv gốc v có tổng số nút phải duyệt cũng được duyệt và tất cả là: ji=1(2si+1)=2s+j ≤ 2s+2h các nút của Tv có trong kết Vậy phải duyệt nhiều nhất là quả tìm kiếm. 2s+4h+1 tức là O(logn + s) – Nếu Tv có sv nút thì ta phải duyệt 2sv+1 nút (Sv nút trong và sv+1 nút ngoài) 9
- Tìm kiếm 2 chiều theo phạm vi Cho không gian hai chiều Mỗi điểm là một cặp (x,y) FindAllInRange(x1,x2,y1,y2): Tìm kiếm tất cả các cặp thỏa: – x1 ≤ x ≤ x2 – y1 ≤ y ≤ y2 10
- 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
- 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 33 50 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
- 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
- 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 25tr40tr, 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
- Ví dụ minh họa Nút phân phối Nút biên
- 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
- 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”) } }
- else { //của if đầu tiên M= ; if (x(v) < x1){ L= ; R=2DTreeRangeSearch(x1,x2,y1,y2,T.rightChild(v),t); } else { //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”);
- 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
- 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 Xét các điểm trong mặt phẳng r3 r2 r4 r1 (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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Chương 3 - PGS.TS. Nguyễn Mậu Hân
134 p | 52 | 7
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 4 – Hà Đại Dương
23 p | 36 | 6
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 4.1
30 p | 80 | 5
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Chương 1 - PGS.TS. Nguyễn Mậu Hân
82 p | 59 | 4
-
Bài giảng Phân tích và thiết kế hệ thống thông tin: Phân 1 - ĐH Phạm Văn Đồng
62 p | 64 | 4
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 2 – Hà Đại Dương
25 p | 48 | 4
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 3 – Hà Đại Dương
26 p | 40 | 4
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 1 - Nguyễn Nhật Quang
12 p | 21 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 5 - Nguyễn Nhật Quang
35 p | 15 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 9 - Nguyễn Nhật Quang
44 p | 13 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 3.1
11 p | 78 | 3
-
Bài giảng Phân tích và thiết kế mạng: Chương 3 – Vũ Chí Cường
25 p | 37 | 3
-
Bài giảng Phân tích và thiết kế mạng: Chương 2 – Vũ Chí Cường
17 p | 55 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 10 - Nguyễn Nhật Quang
58 p | 15 | 3
-
Bài giảng Phân tích và thiết kế thuật toán: Bài 1 – Hà Đại Dương
18 p | 38 | 3
-
Bài giảng Phân tích và thiết kế hệ thống: Chương 3.2
19 p | 80 | 3
-
Bài giảng Phân tích và thiết kế thuật toán
26 p | 124 | 2
-
Bài giảng Phân tích và thiết kế mạng: Chương 1 – Vũ Chí Cường
14 p | 39 | 2
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn