Bài toán tìm cặp điểm gần nhất

Nguồn: [You must be registered and logged in to see this link.]
Khoảng cách giữa các điểm thường được xét trong các bài toán hình học. Đã có rất nhiều ứng dụng của một bài toán quen thuộc “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”. Thông thường, để giải quyết bài toán trên có lẽ hướng thông dụng nhất là 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 tốt hơn. Ở đây, tôi xin đưa ra và cùng các bạn xem xét một bài toán khác về khoảng cách, một thuật toán mẫu được dùng có hiệu quả trong các biến thể của các 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.

Bài toán tìm cặp điểm gần nhất

Bài toán cặp điểm gần nhất tìm hai điểm gần nhau nhất trong một tập điểm cho trước?

Với một yêu cầu đề bài như trên, dường như công việc của chúng ta là phải tính khoảng cách giữa mọi cặp điểm để tìm khoảng cách nhỏ nhất: Giả sử cho trước N điểm, vậy thời gian thực hiện sẽ tỉ lệ với N2. Tuy nhiên, ta có thể dùng một thuật toán sắp xếp để chỉ phải tính chừng NlogN khoảng cách trong trường hợp xấu nhất (về mặt trung bình sẽ ít hơn nhiều). Và bây giờ chúng ta hãy cùng xem xét một thuật toán như vậy nhé.

Chúng ta sẽ dùng một thuật toán dựa trên chiến lược “chia để trị”. Ý tưởng ở đây là sắp xếp các điểm theo một trục toạ độ, như trục x chẳng hạn, rồi dùng thứ tự này để chia tập điểm thành hai phần. Trong toàn bộ tập điểm đã cho, cặp điểm gần nhất hoặc là cặp gần nhất trong cùng một bên nào đó, hoặc là một cặp điểm cắt ngang đường thẳng phân giới giữa hai tập điểm thành phần. Dĩ nhiên, trường hợp đáng chú ý là khi cặp điểm gần nhất cắt ngang đường phân giới. Cặp điểm gần nhất trong mỗi nửa bên rõ ràng là tìm được bằng các lời gọi đệ quy, nhưng còn các cặp có mỗi điểm ở một bên đường phân giới sẽ được kiểm tra như thế nào?

Điều tất nhiên là chúng ta sẽ chỉ cần xét những điểm trong khoảng cách min ở hai bên đường phân giới (vì đang tìm cặp điểm gần nhất), với min là là khoảng cách nhỏ hơn giữa các cặp điểm gần nhất ở mỗi nửa bên. Tuy nhiên, trong trường hợp xấu nhất thì nhận xét này là không đủ, vì có thể có nhiều cặp gần với đường phân giới; ví dụ như tất cả các điểm ở mỗi nửa bên có thể sắp thành một hàng ngay cạnh đường thẳng phân giới.

Để xử lý tình huống trên, có vẻ như chúng ta cần phải sắp các điểm theo y. Như vậy, chúng ra có thể giới hạn các khoảng cách phải tính như sau:

-Xử lý các điểm theo chiều tăng của y

-Kiểm tra xem mỗi điểm có nằm trong dải đứng chứa các điểm trong phạm vi min kể từ điểm phân giới

-Với mỗi điểm trong dải trên, tính khoảng cách giữa điểm này với các điểm cũng trong dải và có tung độ y nhỏ hơn tung độ của điểm đang xét nhưng không nhỏ quá min.

Khoảng cách giữa các điểm ở mỗi nửa bên tối thiểu là min nên số điểm phải kiểm tra sẽ ít hơn.

Dù rằng thuật toán này đơn giản, nhưng chúng ta cũng nên chú ý một vài điều để cài đặt có hiệu quả. Chúng ta có thể trả giá để sắp các điểm theo y bằng một thủ tục đệ quy. Nhiều thuật toán có thời gian thi hành được mô tả bằng biểu thức quy nạp CN= 2CN/2+ N, dẫn đến CN là tỉ lệ với NlogN; Nếu chúng ta xấp xếp theo y thì biểu thức quy nạp sẽ là:

CN=2*CN/2 + NlogN, dẫn đến CN tỉ lệ với Nlog2N( NlogN*logN). Bởi vậy, để loại bỏ điều này, chúng ta sẽ tránh sắp theo y

Lời giải vấn đề này tuy đơn giản nhưng cũng thật tinh vi. Ta có hai vấn đề và có chung một lời giải cho chúng, như vậy chúng ta có thể giải chúng đồng thời. Đặc biệt chúng ta sẽ viết một thủ tục đệ quy vừa sắp theo y lại vừa tìm cặp điểm gần nhất. Thủ tục này sẽ chia đôi tập điểm, rồi gọi lại chính nó để sắp hai nửa bên theo y và tìm cặp điểm gần nhất trong mỗi nửa, sau đó trộn hai nửa bên để hoàn tất việc sắp theo y và áp dụng lại thủ tục trên để hoàn tất việc tính cặp điểm gần nhất. Cách này chúng ta đã tránh được chi phí cho sự thêm việc sắp theo y bằng cách trộn dữ liệu được yêu cầu trong việc sắp xếp với dữ liệu được yêu cầu khi tính cặp điểm gần nhất.

Khi sắp theo y, việc chia đôi có thể làm bằng bất kỳ cách nào, nhưng với phép tính cặp điểm gần nhất, việc chia đôi yêu cầu có một nửa bên có hoành độ x nhỏ hơn nửa bên còn lại. Điều này được cài đặt dễ dàng bằng cách sắp theo x trước khi chia đôi tập điểm. Thực tế, ta có thể dùng ngay thủ tục này để sắp theo x! Khi đã hiểu dự định tổng thể, việc cài đặt không còn khó khăn nữa.

Chúng ta sẽ cần sử dụng đến thủ tục sort và merge đệ quy. Đầutiên là thay đổi các cấu trúc danh sách để lưu các điểm thay cho các khóa, và sử dụng thủ tục merge để kiểm tra biếnt toàn cục p dùng cho việc chọn cách so sánh. Nếup= 1, ta sẽ so sánh hoành độ x của hai điểm; nếu p=2 ta so sánh tung độ y giữa hai điểm. Chúng ta cùng xét hàm merge:



Nút rỗng x ở cuối danh sách làm điểm cầm canh với toạ độ x,y giả. Ta dung một thủ tục đơn giản khác để kiểm tra khoảng cách giữa hai điểm đã cho có nhỏ hơn biến toàn cục min hay không. Nếu nhỏ hơn, biến min sẽ lưu lại khoảng cách này và các điểm nút được lưu vào hai biến toàn cục gp1 và gp2





Như vậy, min luôn chứa khoảng cách giữa gp1 và gp2, là 2 điểm gần nhất được thấy tới lúc này.

Bước tiếp theo là chúng ta cùng xét thủ tục Sort sau để tìm điểm gần nhất khi pa=2



Nếu pa:=1 thủ tục sẽ trả lại một danh sách kết nối các điểm được sắp theo hoành độ x. Cái hay của thủ tục này là khi pa:= 2, chương trình không chỉ sắp xếp theo y mà còn hoàn thành việc tính điểm gần nhất.

Đầu tiên chúng ta sắp xếp theo x, sau đó sắp xếp theo y rồi cặp điểm gần nhất bằng lời gọi sort như trên thủ tục trên

Trong thủ tục kiemtra, hai biến toàn cục gp1, gp2 chứa cặp điểm gần nhất

điều then chốt trong thuật toán này là thao tác sort khi pa= 2. Trước khi thực hiện đệ quy, các điểm đã được sắp xếp theo x; trật tự này dùng để chia đôi các điểm và tìm hoành độ x của đường phân giới. Sau khi đệ quy, các điểm được sắp xếp theo y và khoảng cách giữa các cặp điểm trong mỗi nửa bên là lớn hơn min. Trật tự theo y được dùng để quét các điểm ở gần đường phân giới; giá trị min được dùng để giới hạn số điểm kiểm tra. mỗi điểm ở trong phạm vi min kể từ điểm phân giới được kiểm tra với từng điểm trong 4 điểm trước đó và 4 điểm này cũng ở trong phạm vi min kể từ đường phân giới. Ta biết rằng các điểm rơi vào một bên của đường phân giới cách nhau một khoảng tối thiểu là min, như vậy số các điểm rơi vào vòng tròn có bán kính minsẽ được giới hạn lại.

Nếu các bạn để ý sẽ nhận ra rằng, chúng ta đã không cài đặt thuần tuý thuật toán chia để trị. Ta không thực sự tính cặp gần nhất trong hai nửa bên, rồi lấy cặp gần hơn trong hai cặp có được. Thay vào đó, chúng ta chỉ đơn giản tính cặp gần hơn giữa hai cặp gần nhất bằng cách dùng một biến toàn cục min trong suốt việc tính toán đệ quy. Mỗi lần ta tìm được một cặp gần hơn, ta có thể xét một dải đứng hẹp hơn quanh đường phân giới đang xét.

Qua tất cả những điều chúng ta xét ở trên, đến lúc này chúng ta có thể thấy:

*** Cặp điểm gần nhất trong một tập N điểm có thể được tìm trong NlogN bước.

Như vậy, bài toán tìm cặp điểm gần nhất có thể dùng cho các bài toán hình học khác. Ví dụ như bài toán tìm “tất cả láng giềng gần nhất: Với mỗi điểm ta tìm điểm gần nhất của nó”. Bài toán này có thể giải bằng cách dùng một chương trình tương tự như trên với việc mở rộng xử lý theo đường phân giới: Với mỗi điểm xem có hay không một điểm ở bên kia đường phân giới gần với nó hơn là điểm gần nhất ở cùng bên. Một lần nữa, việc sắp xếp theo y giúp ích cho quá trình tính toán này