TAILIEUCHUNG - Một thuật toán hiệu quả cho bài toán tìm cặp điểm khác màu gần nhất trong tập điểm hai màu trên mặt phẳng

Bài toán tập điểm hai màu trong mặt phẳng được phát biểu như sau : “Cho n điểm màu xanh và m điểm màu đỏ trên mặt phẳng, làm thế nào tìm được cặp điểm xanh – đỏ gần nhau nhất”. Việc xác định lời giải cho bài toán này có thể được thực hiện tương đối dễ dàng bằng thuật toán vét cạn – kiểm tra hết tất cả các cặp điểm khác màu. Tuy nhiên, trong bài báo này chúng tôi sẽ trình bày một thuật toán tốt hơn rất nhiều để giải quyết bài toán này. Công cụ chủ yếu được sử dụng trong thuật toán của chúng tôi là lược đồ Voronoi trên mặt phẳng. | Một thuật tốn hiệu quả cho bài tốn tìm cặp điểm khác màu gần nhất trong tập điểm hai màu trên mặt phẳng Tạp chí KHOA HỌC ĐHSP Nguyễn Ngọc Trung, Trần Thị Diệu Huyền MỘT THUẬT TỐN HIỆU QUẢ CHO BÀI TỐN TÌM CẶP ĐIỂM KHÁC MÀU GẦN NHẤT TRONG TẬP ĐIỂM HAI MÀU TRÊN MẶT PHẲNG Nguyễn Ngọc Trung*, Trần Thị Diệu Huyền† 1. Mở đầu Bài tốn tìm cặp điểm khác màu gần nhất trong tập điểm hai màu trên mặt phẳng thuộc dạng các bài tốn tìm các cặp điểm gần nhất trong mặt phẳng. Bài tốn đặt ra là : “Cho n điểm màu xanh và m điểm màu đỏ trên mặt phẳng, làm thế nào tìm được cặp điểm xanh – đỏ gần nhau nhất”. Bài tốn trên cĩ thể được giải một cách dễ dàng bằng cách lấy lần lượt từng cặp phần tử là các điểm xanh và và điểm đỏ, xác định khoảng cách giữa chúng và chọn ra cặp cĩ khoảng cách nhỏ nhất. Thuật tốn như vậy sẽ cĩ độ phức tạp là O() trong đĩ n là số điểm xanh và m là số điểm đỏ trên mặt phẳng. Một câu hỏi được đặt ra là liệu cĩ thể xây dựng một thuật tốn tốt hơn cho bài tốn này ? Chúng ta thấy rằng, trong chuyên ngành hình học tính tốn, lược đồ Voronoi đĩng một vai trị rất quan trọng trong việc giải quyết các bài tốn tìm các cặp điểm gần nhất trên mặt phẳng. Điều này cũng dễ hiểu vì lược đồ Voronoi cĩ những tính chất rất đặc trưng về khoảng cách, điều mà rất hay được dùng để rút ngắn thời gian tính tốn, cũng như thời gian thực hiện các thuật tốn giải những bài tốn trên. Chính vì thế trong bài báo này, chúng tơi đã chọn lược đồ Voronoi để làm cơng cụ xây dựng thuật tốn giải bài tốn tìm cặp điểm khác màu gần nhất trong số tập điểm hai màu trên mặt phẳng. Cấu trúc bài báo như sau : mục 2 dành cho việc giới thiệu sơ lược về lược đồ Voronoi và các tính chất của nĩ. Phần mơ tả chi tiết về thuật tốn giải quyết bài tốn sẽ được trình bày trong mục 3. Phần cuối của bài báo sẽ là một số chứng * ThS, Khoa Tốn – Tin học, Trường Đại học Sư phạm † CN, Sinh viên Khoa Tốn – Tin học Trường ĐHSP .

• Toán học
• Bài toán tìm cặp điểm khác màu
• Tìm cặp điểm khác màu gần nhất
• Tập điểm hai màu trên mặt phẳng
• Lược đồ Voronoi trên mặt phẳng
• Thuật toán vét cạn
• Thiết kế thuật toán
• Đánh giá thuật toán
• Bài giảng Phân tích thuật toán Phần 2
• Chiến lược vét cạn
• Chiến lược chia để trị
• Cấu trúc dữ liệu
• chu trình Hamilton
• lược đồ phương pháp
• vét cạn nhánh cận
• chứng minh tính đúng
• mô hình thuật toán
• Sinh số giả ngẫu nhiên
• Đồng dư tuyến tính
• Liên lạc mật
• Tấn công vét cạn
• Thuật toán sinh số giả ngẫu nhiên
• Lý thuyết trò chơi
• Ứng dụng trong trò chơi Caro
• Trí tuệ nhân tạo
• Trò chơi Caro
• Thuật toán Min max
• Mạng neural
• Machine learning
• Định lý Bayes
• Giải thuật di truyền
• Thuật toán học MAP vét cạn
• Sàng nguyên tố cải tiến
• Lí thuyết số
• Bồi dưỡng học sinh giỏi Tin học
• Số nguyên tố
• Sàng Eratosthenes
• Phương pháp Wheel factorization