intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

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 Đệ

Chia sẻ: Lê Kim Luông | Ngày: | Loại File: PPT | Số trang:52

109
lượt xem
9
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:
Lưu

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 Đệ

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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)
  6. 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.
  7. 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.
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. Ví dụ minh họa Nút phân phối Nút biên
  16. 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
  17. 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”) } }
  18. 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”);
  19. 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
  20. 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2