Tất cả các kết hợp hợp lệ của các điểm, theo cách hiệu quả nhất (tốc độ)

Question

Tôi biết có một số câu hỏi trên tạo kết hợp các yếu tố, nhưng tôi nghĩ rằng điều này có một sự thay đổi nhất định để có giá trị một câu hỏi mới:

Đối với một proejct thú cưng của tôi, tôi đã tính toán trước rất nhiều trạng thái để cải thiện hành vi thời gian chạy của ứng dụng sau này. Một trong những bước mà tôi phải vật lộn với điều này là:

Cho hai bộ dữ liệu N (cho phép gọi chúng từ đây trở đi, mặc dù chúng không nằm trong trường hợp sử dụng của tôi. Chúng gần đúng là X/Y) cần tính toán tất cả các kết hợp hợp lệ cho một quy tắc nhất định.

Nguyên tắc có thể là một cái gì đó giống như

• "Mỗi điểm bao gồm không bao gồm tất cả các điểm khác với cùng X phối hợp"
• "Mỗi điểm bao gồm không bao gồm tất cả các điểm khác với một X lẻ phối hợp"

Tôi hy vọng rằng điều này dẫn đến sự cải tiến trong quá trình lựa chọn, nhưng kỹ năng toán học của tôi chỉ được hồi sinh khi tôi nhập và tôi không thể đưa ra một thuật toán thanh lịch.

• Tập hợp các điểm (N) bắt đầu nhỏ, nhưng triển nhanh hơn 64 sớm (đối với "sử dụng miễn là bitmask" giải pháp)
• tôi đang làm điều này trong C#, nhưng giải pháp trong bất kỳ ngôn ngữ cần sử dụng tốt nếu nó giải thích ý tưởng cơ bản

Cảm ơn.

---

Cập nhật để đáp ứng với câu trả lời của Vlad:

Có lẽ ý tưởng của tôi để khái quát những câu hỏi là một xấu. Quy tắc của tôi ở trên đã được phát minh khi đang di chuyển và chỉ là trình giữ chỗ. Một nguyên tắc thực tế sẽ trông như thế này:

• "Mỗi điểm bao gồm không bao gồm tất cả các điểm khác trong triagle trên điểm chọn"

Bằng quy tắc đó và bằng cách chọn (2,1) Tôi muốn loại trừ

• (2,2) - trực tiếp trên
• (1,3) (2,3) (3,3) - dòng tiếp theo
• và vân vân

Vì vậy, các quy tắc được khắc phục, chứ không phải chung. Chúng không may phức tạp hơn các mẫu X/Y mà tôi đã đưa ra ban đầu.

Answer 1

Đối với một số loại quy tắc đặc biệt, nhiệm vụ của bạn có vẻ đơn giản. Ví dụ: đối với quy tắc mẫu số 1 của bạn, bạn cần phải chọn một tập hợp con của tất cả các giá trị có thể có của X và hơn cho mỗi giá trị từ tập hợp con gán một tùy ý Y.

Cho generic quy tắc Tôi nghi ngờ rằng có thể xây dựng một thuật toán hiệu quả mà không cần bất kỳ AI nào.

Answer 2

Sự hiểu biết của tôi về vấn đề là: Đưa ra phương pháp bool property(Point x) const, tìm tất cả các điểm mà tập hợp cho thuộc tính() là true. Điều đó có hợp lý không?

Phương pháp tiếp cận vũ phu là chạy tất cả các điểm qua property() và lưu trữ các điểm trả về đúng. Độ phức tạp của thời gian này là O(N) trong đó (a) N là tổng số điểm và (b) phương pháp property() là O(1). Tôi đoán bạn đang tìm kiếm các cải tiến từ O(N). Có đúng không?

Đối với một số loại thuộc tính, có thể cải thiện từ O(N) cung cấp cấu trúc dữ liệu phù hợp được sử dụng để lưu trữ điểm và tính toán trước thích hợp (ví dụ: sắp xếp). Tuy nhiên, điều này có thể không đúng đối với bất kỳ tài sản tùy ý nào.

Answer 3

Làm thế nào về "tọa độ x của mỗi điểm được bao gồm là tổng chính xác của một số tập con của toạ độ y của các điểm khác". Nếu bạn có thể đưa ra một thuật toán nhanh cho vấn đề ràng buộc đơn giản, thì bạn sẽ trở nên rất nổi tiếng.

Vấn đề của tôi là vấn đề được nêu rõ quá mơ hồ như thừa nhận các vấn đề NP-complete hoặc NP-hard. Các vấn đề tối ưu hóa hạn chế là vô cùng khó khăn; nếu bạn không thể đặt các giới hạn cực kỳ chặt chẽ vào vấn đề thì nó sẽ nhanh chóng trở thành không thể phân tích bởi các máy trong thời gian đa thức.