Einfacher Weg, um zu beweisen, dass dieser Algorithmus schließlich endet

Einführung und Notationen:

Hier ist eine neue und einfache Version meines Algorithmus, die (gemäß meinen Experimenten) zu enden scheint, und jetzt möchte ich das beweisen.

Die Notation beziehe sich auf einen dimensionalen Datenpunkt (einen Vektor). Ich habe drei Sätze A, B und C, so dass , , : $x_i \in \mathbb{R}^p$ $p$ $|A| = n$ $|B| = m$ $|C| = l$

A = {x_{i} | i = 1, . ., n}

$A = \{x_i | i = 1, .., n\}$

B = {x_{j} | j = n + 1, . ., n + m}

$B = \{x_j | j = n+1, .., n+m\}$

C = {x_{u} | u = n + m + 1, . ., n + m + l}

$C = \{x_u | u = n+m+1, .., n+m+l\}$

Wenn ist, bezeichne den mittleren euklidischen Abstand von zu seinen nächsten Punkten in ; und bezeichnen den mittleren euklidischen Abstand von zu seinem nächsten Punkten in . $k \in \mathbb{N^*}$ $d_{x_i}^A$ $x_i$ $k$ $A$ $d_{x_i}^C$ $x_i$ $k$ $C$

Algorithmus:

$A$ $B$ $B$ $C$ $A$ $C$ $B$

$A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$
$A = A \setminus A'$ $B = B \cup A'$
$B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$
$B = B \setminus B'$ $A = A \cup B'$
$A$ $B$ $B$ $A$ $|A| \leq k$ $|B| \leq k$

Der Algorithmus wird in zwei Fällen beendet:

$|A|$ $|B|$ $k$
$A' = B' = \emptyset$

Frage:

$\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$ $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$ $\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$ $\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$

Anmerkungen:

$k$ $x$ $S$ $k$ $x$ $S$ $x$ $k = 1$
$A, B, C$ $\forall x_i \in B, x_j \in A$ $x_b \in C$ $x_i$ $x_a \in C$ $x_j$ $distance(x_i, x_b) < distance(x_j, x_a)$ $B$ $C$ $A$
Wenn das die Analyse erleichtert: Es ist durchaus möglich, eine etwas andere Version des Algorithmus in Betracht zu ziehen, sobald ein Punkt von $A$ $B$ $A$ $B$ $A'$ $B$

algorithms complexity-theory algorithm-analysis optimization shn
quelle

Warum interessieren Sie sich für diesen speziellen Algorithmus?

shna: Was möchten Sie mit einer Sammlung von Punkten machen, die willkürlich in drei Mengen unterteilt sind?

@shna Die Kenntnis des Zwecks und des Ziels des Algorithmus kann zu einer verbesserten Intuition führen und somit das Problem lösen.

A

$A$

B

$B$

B

$B$

C

$C$

A

$A$

C

$C$

B

$B$

Die Migration zur Theorie wurde abgelehnt.

$k = 1$

$A$ $B$ $A$ $B$

Lassen $x$ $x$ $B$ $A$ $x$ $A$ $x'$ $A$ $d_x^C > dist(x, x')$ $f$ $f(x) = x'$ $x'$ $A$ $B$ $x'$ $A$ $x$ $f(f(x)), f(f(f(x))),$

$f^n(x) = f^m(x)$ $m > n$ $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ...$ $o$ $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

$f^{o-1}(x)$ $f^o(x)$ $A$ $C$ $d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$ $f$

$f^{o-1}(x)$ $f^o(x)$ $A$ $A$ $f$ $k = 1$

ursächlich
quelle

k = 1

$k = 1$

@shn Ich bin mir nicht sicher, warum Sie die Wahl der Proof-Technik von jemandem kritisieren, der Ihr Problem erfolgreicher gelöst hat als Sie. Besonders wenn Ihre eigene Frage vier fehlgeschlagene Versuche auflistet, Ihre bevorzugte Technik anzuwenden.

David Richerby

k > 1

$k > 1$

Einfacher Weg, um zu beweisen, dass dieser Algorithmus schließlich endet

Einführung und Notationen:

Algorithmus:

Frage:

Anmerkungen:

Antworten: