tailieunhanh - Cẩm nang thuật toán tập 2 part 3

Tham khảo tài liệu 'cẩm nang thuật toán tập 2 part 3', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 28 BÀI TOÁN ĐIỂM GẦN NHẤT Các bài toán hình học thương xét đến các khoảng cách giữa các điểm. Ví dụ một bài toán quen thuộc trong nhỉêu ứng dụng là bài toán tìm láng giêng gàn nhất tìm điểm gân nhất của một điểm cho trước trong một tập cho trước. Đĩêu này có lẽ bao gồm việc kiểm tra khoảng cách giữa điểm được cho với mỗi điểm trong tập điểm đã cho nhưng có những cách giải quyết khác tốt hơn. Trong đoạn này ta sẽ xem xét một vài bài toán khác vê khoảng cách một thuật toán mẫu và một cấu trúc hình học cơ sô là biểu đỗ Vơronoi được dùng có hiệu quả trong các biến thể cỏa những bài toán như vậy. Cách tiếp cận của chúng ta là sẽ thâo luận một phương pháp tổng quát để giài các bài toán điểm gân nhất thông qua việc xem xét kỹ lưỡng một cài đạt mẫu giải quyết một bài toán đơn giàn. Một số bài toán trong chương này tương tự với các bài toán tìm kiếm vùng của Chương 26 và các phương pháp lưới phương pháp cây 2D cũng được triển khai thích hợp cho bài toán láng giêng gan nhất và các bài toán khác. Tuy nhiên thiếu sót lốn nhất của những phương pháp này lã chúng dựa vào tính ngấu nhỉèn cùa tập điểm chúng sẽ làm việc rát tôi trong trường hợp xấu nhất. Mục đích chúng ta trong chương này là khảo sát một tiếp cận tổng quát khác mà vẫn bíio diim sự thực hiện tốt trong nhiêu bài toán không phụ thuộc sô liẹu vào. Một vài phương pháp quá phức tạp để cãi đặt đây đủ và chúng đòi hói tổng phí đủ để Ciic phương pháp đơn giàn hơn óở RÀỈ TOÁN TÌM CẶP tìUĨM ĩẦN NIIẲT lại có thể làm việc tốt hơn trên những tập không lớn lắm hoặc khi tập điểm này được phân tán đù tốt. Tuy nhiên sự nghiên cứu các phương pháp như vậy với việc thực hiện trong nhđng trường hợp xấu nhất sẽ cho thây một vài đặc tính cơ bân cần được hiểu rõ của các tập điểm ngay như nếu các phương pháp đơn giản là tốt hơn trong các tình huống đặc biệt. Ta sẽ xét một tiếp cận tổng quát dùng các thủ tục ổệ quy kép để liên kết các xử lý theo hai trục toạ độ. Hai phương pháp trước đã xét cây kD và giao điểm dựa trên cây tìm kiếm nhị phân .