Wszystkie prawidłowe kombinacje punktów, w najbardziej efektywny sposób (prędkość)

Question

Wiem, że istnieje sporo pytań na temat generowania kombinacji elementów, ale myślę, że ten ma pewien zwrot wart jest nowego pytania:

Dla mojego zwierzęcia, muszę wstępnie obliczyć stan, aby później poprawić działanie środowiska wykonawczego aplikacji. Jeden z kroków, z którymi się borykam, to:

Podane N krotki z dwóch liczb całkowitych (pozwala wywoływać punkty od tego miejsca, chociaż nie są one w moim przypadku użycia, ale w przybliżeniu są powiązane z X/Y). trzeba obliczyć wszystkie prawidłowe kombinacje dla danej reguły.

Reguła może być coś jak

• „Każdy punkt zawarte wyłącza każdy inny punkt o tej samej współrzędnej X”
• „Każdy punkt zawiera wykluczeń co drugi punkt z nieparzystej współrzędnej X”

Mam nadzieję i oczekuję, że fakt ten doprowadzi do poprawy procesu selekcji, ale moje umiejętności matematyczne są właśnie wskrzeszane podczas pisania i nie jestem w stanie wymyślić eleganckiego algorytmu.

• Zbiór punktów (N) zaczyna się mały, ale przerasta 64 wkrótce (do „użytkowania ile maskę bitową” rozwiązania)
• Robię to w C#, ale rozwiązania w dowolnym języku powinno być w porządku jeśli wyjaśni leżący u podstaw pomysł:

Dzięki.

---

Update w odpowiedzi na odpowiedź Vlada:

Może mój pomysł, aby uogólnić pytanie była zła. Moje zasady powyżej zostały wymyślone w locie i po prostu zastępcze. Jeden realistyczny reguła będzie wyglądać następująco:

• „Każdy punkt zawiera wykluczeń co drugi punkt w pełny trójkąt nad wybranym punkcie”

Według tej zasady i wybierając (2,1) bym wykluczyć

• (2,2) - bezpośrednio nad
• (1,3) (2,3) (3,3) - następnej linii
• itd

Zasady są więc stałe, a nie ogólne. Są one niestety bardziej skomplikowane niż próbki X/Y, które początkowo dałem.

Answer 1

W przypadku niektórych typów reguł zadanie wydaje się proste. Na przykład dla przykładowej reguły nr 1 musisz wybrać podzbiór wszystkich możliwych wartości X, a następnie dla każdej wartości z podzbioru przypisać dowolną Y.

Dla reguł generycznych Wątpię, czy to możliwe zbuduj skuteczny algorytm bez żadnej sztucznej inteligencji.

Answer 2

Moje zrozumienie problemu jest następujące: Biorąc pod uwagę metodę bool property(Point x) const, znajdź wszystkie punkty zestawu, dla którego właściwość() jest true. Czy to jest rozsądne?

Metoda brute-force polega na uruchomieniu wszystkich punktów przez property() i zachowaniu tych, które zwracają wartość true. Złożoność czasu to: O(N) gdzie (a) N to całkowita liczba punktów, oraz (b) metoda property() to O(1). Domyślam się, że szukasz ulepszeń od O(N). Czy to prawda?

Dla niektórych rodzajów właściwości możliwe jest ulepszenie od O(N) pod warunkiem, że odpowiednia struktura danych jest używana do przechowywania punktów i jest wykonywane odpowiednie wstępne obliczenie (np. Sortowanie). Jednak może to nie być prawdą w przypadku dowolnej właściwości.

Answer 3

Co powiesz na "współrzędna x każdego uwzględnionego punktu jest dokładną sumą pewnego podzbioru współrzędnych y pozostałych dołączonych punktów". Jeśli możesz wymyślić szybki algorytm dla tego prostego problemu ograniczenia, to staniesz się bardzo sławny.

Uważam, że opisany problem jest tak ogólnikowy, że nie przyznaje się do problemów NP-zupełnych lub NP-trudnych. Problemy z optymalizacją ograniczeń są niezwykle trudne: - niezwykle trudne; jeśli nie potrafisz bardzo mocno ograniczyć problemu, to bardzo szybko staje się on niemożliwy do analizy przez maszyny w czasie wielomianowym.