Finden Sie die nächsten

8

Wie kann man die d+1 Ecken des Einheitswürfels in Rd einem Punkt x im Würfel am nächsten liegen ?
Verwenden Sie die L1-Metrik, so dass in 4d | x - 0000 | = xi , | x - 0001 | = x3+x2+x1+(1x0)
( x0 rechts) und so weiter.

Für eine alternative Formulierung drehen Sie zuerst xi > 1/2 und sortieren Sie, so dass 0xd1 x1x0 1/2; Aus Symmetriegründen kann ein Algorithmus für diesen Fall jedes x im Würfel ausführen.
Definieren Sie c12x , 1cd1 c1c00 .
Dann wollen wir das d+1Ecken mit kleinster c Ecke.

In 4d zum Beispiel können mit xi , das wie oben um 1/2 .. 0 abnimmt, die 5 nächsten Ecken sein

    0 0 0 0
    0 0 0 1
    0 0 1 0

    0 1 0 0  or  0 0 1 1
                 0 1 * *

    1 0 0 0
 or 0 1 0 1

In 5d, 6d ... sehen die Bäume mit zunehmenden Ecken (für mich) jedoch immer unordentlicher aus.
Heuristiken für ungefähr am nächsten wäre in Ordnung.

Denis
quelle
Was bricht im einfachen Ansatz? Angenommen, jede Ecke des Würfels befindet sich in und x [ 0 , 1 ] d . Runden Sie jeden Koordinator auf die nächste ganze Zahl, um den nächsten Punkt p zu erhalten , und erzeugen Sie d weitere "nächstgelegene Punkte", indem Sie jeder Koordinate von unabhängig voneinander hinzufügen . {0,1}dx[0,1]dpdp1mod2p
Daniel Apon
@ Daniel Apon, in 3d mit 0 <= x2 <= x1 <= x0 <= 1/2 oder 1> = c2> = c1> = c0> = 0 wie oben können die nächsten 4 Ecken 000 001 010 100 sein Sie schlagen vor, kann aber auch ein Gesicht sein 000 001 010 011. (Der gesamte 3D-Würfel teilt sich in 8 + 6 Teile, 8 Ecken plus angrenzende und 6 Gesichter.)
Denis
2
Hier ist eine andere Möglichkeit, dieses Problem zu benennen: Suchen Sie bei einer Sammlung von nicht negativen Zahlen die Teilmengen mit minimalen Kosten (wobei die Kosten einer Menge die Summe der darin enthaltenen Zahlen sind). n + 1nn+1
Neal Young
Ja, das ist die min c. Ecke oben - Min-Cost-Teilmenge ist ein besserer Name, fügen Sie diesen dem Titel / den Tags hinzu?
Denis

Antworten:

8

ZeitO(d3logd)

Lemma: Fixiere jedes . Dann gibt es eine Menge die Ecken von , die nächsten liegen und so, dass verbunden ist (was bedeutet, dass der durch induzierte Teilgraph des Hyperwürfels verbunden ist). S d + 1 { 0 , 1 } d x S S.x[0,1]dSd+1{0,1}dxSS

Beweis. Betrachten Sie zunächst den Fall, dass keine Koordinaten gleich .1 / 2x1/2

Wenn eine Ecke in , erhöht das Umdrehen einer Koordinate von nicht den Abstand von nach wenn . S a j a a x | a j - x j | 1 / 2aSajaax|ajxj|1/2

Betrachten Sie zwei beliebige Ecken in , die sich in mindestens einer Koordinate , und nehmen Sie WLOG an, dass und . Wenn ist, ergibt das Umdrehen von in einen weiteren Punkt in (weil dadurch der Abstand von zu verringert wird ). Oder, wenn dann Spiegeln in gibt einen Punkt in . Wiederholen Sie diesen Vorgang für jede unterschiedliche Koordinate inS j a j = 0 b j = 1 x j < 1 / 2 b j b S b x x j > 1 / 2 ein j a Sa,bSjaj=0bj=1xj<1/2bjbSbxxj>1/2ajaS und b ergibt einen Pfad, der a und verbindetaba innerhalb von S .bS

Wenn die Koordinaten auf gleich 1 / 2 , dann, bei der Auswahl S , Pause Beziehungen zwischen den äquidistanten Punkten durch Vorrang zu denen mit mehr Null Koordinaten geben. Dann funktioniert das gleiche Argument. QEDx1/2S

Durch das Lemma können Sie einen Dijkstra-ähnlichen Algorithmus verwenden, um zu finden . Beginne mit einer Ecke am nächsten x ( a mit einem j = 0 , wenn x j1 / 2 ). Fügen Sie dann wiederholt zu S eine Ecke hinzu, die x am nächsten ist, unter denen, die an einen Punkt in S angrenzen . Stoppen Sie, wenn d + 1 Punkte hinzugefügt wurden. Sxaaj=0xj1/2SxSd+1

Naiv (unter Verwendung eines Min-Heaps, um den nächstgelegenen Punkt zu in jeder Iteration zu finden), gibt es vermutlich d + 1 Iterationen, und jede Iteration erfordert O ( d 2 ) -Arbeit, um die d Nachbarn des hinzugefügten Knotens (jeweils ) zu erzeugen davon hat eine Darstellung der Größe d ), was die Laufzeit O ( d 3 log d ) ergibt .xd+1O(d2)ddO(d3logd)

Zeit O(d2logd)

Stellen Sie jede Ecke implizit als Paar ( h , d ) dar , wobei h ein Hash der Menge von Indizes i ist, so dass a i = 1 ist und d der Abstand von x zu a ist . Aus einer gegebenen Ecke a können die Paare für alle benachbarten Ecken in O ( d ) Zeit (gesamt) erzeugt werden. Dies reduziert die Laufzeit auf O ( d 2 log d ) .a(h,d)hiai=1dxaaO(d)O(d2logd)

Schneller?

Um die Diskussion zu vereinfachen, formulieren wir das Problem wie folgt um. Wenn eine Folge von nicht negativen Zahlen y 1y 2y d gegeben ist , finden Sie die d + 1 -Teilmengen der Zahlen mit minimalen Kosten, wobei die Kosten einer Teilmenge die Summe der darin enthaltenen Zahlen sind. dy1y2ydd+1 (Um die Verbindung mit dem vorhergehenden Problem zu sehen, nehmen , dann wird jeder Teilmenge Y des Y i ‚s entspricht einer Ecke ayi=|xi1/2|Yyi der HyperWürfels, wobei a i ( y ) ist 1wenn ( x i1 / 2 und y iY ) oder ( x i > 1 / 2 und y iY ); und die Kosten von Y sind der Abstand von x zu a ( y ) .)a(y)ai(y)xi1/2yiYxi>1/2yiYYxa(y)

Hier ist eine allgemeine Idee für einen schnelleren Algorithmus. Vielleicht kann jemand herausfinden, wie es funktioniert.

Yyi(h,c)hcYYY(Y)(Y)YYYY(Y)(Y)

d+1O(d)O(dlogd)

Neal Young
quelle
Danke Neal. Kann man die Erweiterung der Dijkstra-ähnlichen Ecke verbessern? Die Sätze möglicher nächster d + 1-Ecken nach der Normalisierung (Umdrehen von x auf <= 1/2 und Sortieren) scheinen mit d sehr langsam zu wachsen.
Denis
Ich habe die Antwort bearbeitet, um die Laufzeit genauer zu diskutieren.
Neal Young
O(dlogd)
8

dd+1d+1

d+1SSS

O(dlogd)

d+1O(d)

David Eppstein
quelle
O(dlogd)
0



d
ln2d
ln2d
d+1d

Denis
quelle