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

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ươ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ơ 2013 Dữ liệu nhiều chiều Các giải thuật hình học liên quan tới dữ liệu không gian đa chiều. Một điểm trong mặt phẳng (x,y) Một điểm trong không gian (x,y,z) Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiều Một số bài toán quan trọng Tìm kiếm theo phạm vi (range searching query) Tìm bao lồi (convex hull) Cây tìm kiếm phạm vi Một điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1, ,xd-1). Tìm kiếm theo phạm vi là tìm kiếm các điểm 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. Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r) Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi. Tìm kiếm 1 chiều theo phạm vi Cho một tự điển (tập hợp các phần tử) có thứ tự findAllInRange(k1,k2): trả về các phần tử thỏa: k1 ≤ x ≤ k2 Dùng cấu trúc cây TKNP để lưu trữ các phần tử Giải thuật tìm kiếm 1DTreeRangeSearch(k1,k2,v) Nếu v là nút ngoài (V=NULL): dừng Nếu v là nút trong Key(v)k2: tìm đệ qui trên cây con trái của v. Giải thuật 1DTreeRangeSearch 1DTreeRangeSearch(k1,k2,v){ if (v) return ; if (k1 ≤ key(v) ≤ k2) { L= 1DTreeRangeSearch(k1,k2,(v)); R= 1DTreeRangeSearch(k1,k2,(v)); return L U {element(v)} U R; } else if (key(v) 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ơ 2013 Dữ liệu nhiều chiều Các giải thuật hình học liên quan tới dữ liệu không gian đa chiều. Một điểm trong mặt phẳng (x,y) Một điểm trong không gian (x,y,z) Các ứng dụng máy học, xử lí ảnh cần xử lí dữ liệu hàng trăm, hàng ngàn chiều. Các bài toán thống kê, điều khiển cũng cần xử lí dữ liệu nhiều chiều Một số bài toán quan trọng Tìm kiếm theo phạm vi (range searching query) Tìm bao lồi (convex hull) Cây tìm kiếm phạm vi Một điểm trong không gian d chiều được biểu diễn theo tọa độ bởi (x0,x1, ,xd-1). Tìm kiếm theo phạm vi là tìm kiếm các điểm 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. Kết quả tìm kiếm là tất cả các điểm hình tròn ((xq,yq),r) Giải thuật tìm kiếm thường tổ chức dữ liệu theo cây cân bằng – gọi là cây TK phạm vi. Tìm kiếm 1 chiều theo phạm vi Cho một tự điển (tập hợp các phần tử) có thứ tự findAllInRange(k1,k2): trả về các .