Manera fácil de demostrar que este algoritmo finalmente termina

Introducción y anotaciones:

Aquí hay una versión nueva y simple de mi algoritmo que parece terminar (según mis experimentos), y ahora me gustaría probarlo.

Deje que la notación refiera a un punto de datos dimensional (un vector). Tengo tres conjuntos A, B y C, de modo que , , : p | A | = n | B | = m | C | = l A = { x i | i = 1 , . . , n } B = { x j | j = n + 1 , . . , n + m } C = { x u $x_i \in \mathbb{R}^p$$p$$|A| = n$$|B| = m$$|C| = l$

Dado , deje que denote la distancia euclidiana media desde a sus puntos más cercanos en ; y denota la distancia media euclidiana de a su más cercano puntos en . d A x i x i k A d C x i x i k $k \in \mathbb{N^*}$$d_{x_i}^A$$x_i$$k$$A$$d_{x_i}^C$$x_i$$k$$C$

Algoritmo:

Tengo el siguiente algoritmo que modifica iterativamente los conjuntos A y B moviendo algunos elementos seleccionados de A a B y viceversa, y C permanece siempre igual (no cambia). Para simplificarlo: el propósito del algoritmo es separar mejor los conjuntos y modo que "los puntos de sean más similares a los de un conjunto fijo conocido " y "los puntos de finalmente sean autosimilares y más lejos de los de y el conjunto final ":B B C A C $A$$B$$B$$C$$A$$C$$B$

• $A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$ ... (1)
• B = B ∪ A $A = A \setminus A'$ ; ... (2)$B = B \cup A'$
• $B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
• A = A ∪ B $B = B \setminus B'$ ; ... (4)$A = A \cup B'$
• Repita (1), (2), (3) y (4) hasta que: (ningún elemento se mueva de a o de a , es decir, A 'y B' se vacíen) o ( o )B B A | A | ≤ k | B | ≤ $A$$B$$B$$A$$|A| \leq k$$|B| \leq k$

El algoritmo termina en dos casos:

• cuandoose vuelve menor o igual aEl | B | $|A|$$|B|$$k$
• o el caso más estándar, cuando , lo que significa que no se mueven más elementos entre A y B.$A' = B' = \emptyset$

Pregunta:

¿Cómo demostrar que este algoritmo finalmente termina? No encontré una función potencial conveniente que pueda ser estrictamente minimizada o maximizada por el algoritmo. He intentado sin éxito algunas funciones: la función pero no aumenta en cada iteración. La función pero no está disminuyendo en cada iteración. La función parece no estar disminuyendo en cada iteración. La función ∑ x ∈ A d A x + ∑ x ∈ B d C x ∑ x ∈ A d A x + ∑ x ∈ B d B x ∑ x ∈ A d B x + ∑ x ∈ B d A $\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$parece no estar aumentando en cada iteración. Entonces, ¿cuál es la función potencial conveniente que se puede mostrar que aumenta o disminuye en cada iteración? ¿O deberíamos mostrar que la función disminuye pero no en cada iteración (después de algunas iteraciones)? Cómo ?

Notas:

• Los puntos más cercanos a en un conjunto , significa: los puntos (distintos de ) en , que tienen la distancia euclidiana más pequeña a . Simplemente puede tomar para simplificar el análisis.x S k x S x k = $k$$x$$S$$k$$x$$S$$x$$k = 1$
• No sé si esto puede ayudar o no, pero tengo la siguiente propiedad para mis conjuntos iniciales : inicialmente , si es el punto más cercano a y es el punto más cercano a entonces siempre . Esto intuitivamente significa que los puntos en están más cerca de de puntos en .∀ x i ∈ B , x j ∈ A x b ∈ C x i x a ∈ C x j d i s t a n c e ( x i , x b ) < d i s t a n c e ( x j , x a ) B C $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$
• Si eso facilita el análisis: es totalmente posible considerar una versión ligeramente diferente del Algoritmo en la que tan pronto como un punto de se mueva a , se mueva de a (sin pasar por ), y vis inversa de .B A B A ′$A$$B$$A$$B$$A'$$B$

Aquí está la solución para el caso :$k = 1$

Suponga que el algoritmo no termina. Como hay un número finito de estados del algoritmo (asignaciones de puntos a y B ), el estado del algoritmo debe repetirse en un ciclo. Dado que el ciclo pasa por diferentes estados, debe haber un punto que cambie entre A y B infinitamente.$A$$B$$A$$B$

Sea un punto que cambia infinitamente a menudo en este ciclo. Elige la primera iteración del algoritmo dentro del ciclo durante el cual x interruptores de B a A . Para que x cambie a A , debe haber habido al menos un punto x ' en A , con d C x > d i s t ( x , x ' ) . Elija arbitrariamente el punto más pequeño etiquetado; define una función f para que f ( x ) $x$$x$$B$$A$$x$$A$$x'$$A$$d_x^C > dist(x, x')$$f$ . Tenga en cuenta que x ' también debe cambiar entre A y B infinitamente (porque si x ' permaneció en A permanentemente, también lo haría x ), entonces podemos tomar f ( f ( x ) ) , f ( f ( f ( x ) ) ) , etc.$f(x) = x'$$x'$$A$$B$$x'$$A$$x$$f(f(x)), f(f(f(x))),$

Como tenemos un número finito de puntos, las iteraciones de f eventualmente deben repetirse: para algunos m > n . Ahora mira a las secuencias correspondientes de distancias de C: d C f ( x ) , d C f 2 ( x ) , . . . d C f n ( x ) , . . $f^n(x) = f^m(x)$$m > n$$d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ...$. Como se repite, esta secuencia no puede disminuir uniformemente. Debe haber una iteración tal que d C f o - 1 ( x ) ≤ d C f o ( x $o$$d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Ahora, y f o ( x ) están lo suficientemente cerca uno del otro como para causar que el otro esté en A , si uno de ellos está. Es decir, están más cerca uno del otro que cualquiera de ellos es C : d C f o ( x ) ≥ d C f o - 1 ( x ) > d i s t ( f o - 1 ( x ) $f^{o-1}(x)$$f^o(x)$$A$$C$ (de la definición de f )$d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$$f$

Tan pronto como y f o ( x ) estén ambos en A , se mantendrán mutuamente en A para siempre (ver líneas 1-2 del algoritmo). Esto contradice el hecho de que todas las iteraciones de f deben cambiar conjuntos infinitamente a menudo. Por lo tanto, para el caso en que k = 1 , el algoritmo termina.$f^{o-1}(x)$$f^o(x)$$A$$A$$f$$k = 1$