Finden Sie die nächsten

Wie kann man die $d+1$ Ecken des Einheitswürfels in $\mathbb{R}^d$ einem Punkt $x$ im Würfel am nächsten liegen ?
Verwenden Sie die L1-Metrik, so dass in 4d | $x$ - 0000 | = $\sum {x_i}$ , | $x$ - 0001 | = $x_3 + x_2 + x_1 + (1 - x_0)$
( $x_0$ rechts) und so weiter.

Für eine alternative Formulierung drehen Sie zuerst $x_i$ > 1/2 und sortieren Sie, so dass $0 \leq x_{d-1} \leq \dots\ x_1 \leq x_0 \leq$ 1/2; Aus Symmetriegründen kann ein Algorithmus für diesen Fall jedes $x$ im Würfel ausführen.
Definieren Sie $c \equiv 1 - 2x$ , $1\geq c_{d-1} \geq \dots\ c_1 \geq c_0 \geq 0$ .
Dann wollen wir das $d+1$Ecken mit kleinster $c \cdot$ Ecke.

In 4d zum Beispiel können mit $x_i$ , 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.

Zeit$O(d^3\log d)$

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 $x\in[0,1]^d$$S$$d+1$$\{0,1\}^d$$x$$S$$S$

Beweis. Betrachten Sie zunächst den Fall, dass keine Koordinaten gleich .1 /$x$$1/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 /$a$$S$$a_j$$a$$a$$x$$|a_j - x_j| \ge 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 $a,b$$S$$j$$a_j=0$$b_j=1$$x_j<1/2$$b_j$$b$$S$$b$$x$$x_j>1/2$$a_j$$a$$S$ und b ergibt einen Pfad, der a und verbindet$a$$b$$a$ innerhalb von S .$b$$S$

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. QED$x$$1/2$$S$

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 j ≤ 1 / 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. $S$$x$$a$$a_j = 0$$x_j \le 1/2$$S$$x$$S$$d+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 .$x$$d+1$$O(d^2)$$d$$d$$O(d^3\log d)$

Zeit $O(d^2\log d)$

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)$$h$$i$$a_i=1$$d$$x$$a$$a$$O(d)$$O(d^2\log d)$

Schneller?

Um die Diskussion zu vereinfachen, formulieren wir das Problem wie folgt um. Wenn eine Folge von nicht negativen Zahlen y 1 ≤ y 2 ≤ ⋯ ≤ y 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. $d$$y_1 \le y_2 \le \cdots \le y_d$$d+1$ (Um die Verbindung mit dem vorhergehenden Problem zu sehen, nehmen , dann wird jeder Teilmenge Y des Y i ‚s entspricht einer Ecke $y_i = |x_i - 1/2|$$Y$$y_i$ der HyperWürfels, wobei a i ( y ) ist 1wenn ( x i ≤ 1 / 2 und y i ∈ Y ) oder ( x i > 1 / 2 und y i ∉ Y ); und die Kosten von Y sind der Abstand von x zu a ( y ) .)$a(y)$$a_i(y)$$x_i \le 1/2$$y_i\in Y$$x_i>1/2$$y_i\not\in Y$$Y$$x$$a(y)$

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

$Y$$y_i$$(h, c)$$h$$c$$Y$$Y\rightarrow Y'$$(Y') \ge$$(Y)$$Y'$$Y\rightarrow Y'$$Y$$(Y) \le$$(Y')$

$d+1$$O(d)$$O(d\log d)$

$d$$d+1$$d+1$

$d+1$$S$$S$$S$

$O(d\log d)$

$d+1$$O(d)$

$\dots$

$\qquad$$d$$\dots$
$\qquad$ $\lceil ln_2 d\rceil$
$\qquad$$\lceil ln_2 d\rceil$
$d+1$$d$