Maneira fácil de provar que esse algoritmo termina eventualmente

Introdução e anotações:

Aqui está uma versão nova e simples do meu algoritmo que parece terminar (de acordo com meus experimentos), e agora eu gostaria de provar isso.

Deixe a notação referir-se a um ponto de dados dimensionais (um vetor). Eu tenho três conjuntos A, B e C, de modo que , , : p | Um | = 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 , deixe denotar a distância euclidiana média de até seus pontos mais próximos em ; e denotar a distância Euclidiana significativo de a sua mais próxima pontos em . 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:

Eu tenho o seguinte algoritmo que modifica iterativamente os conjuntos A e B movendo alguns elementos selecionados de A para B e vice-versa, e C permanece sempre o mesmo (não mude). Para simplificar: o objetivo do algoritmo é separar melhor os conjuntos e modo que "os pontos de sejam mais semelhantes aos de um conjunto fixo conhecido " e "os pontos de finalmente sejam auto-similares e mais distantes dos de e do 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)
• $A = A \setminus A'$ ; ... (2)$B = B \cup A'$
• $B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
• $B = B \setminus B'$ ; ... (4)$A = A \cup B'$
• Repita (1), (2), (3) e (4) até: (nenhum elemento se move de para ou de para , ou seja, A 'e B' ficam vazios) ou ( ou )$A$$B$$B$$A$$|A| \leq k$$|B| \leq k$

O algoritmo termina em dois casos:

• quandooutorna-se menor ou igual a$|A|$$|B|$$k$
• ou o caso mais padrão, quando , o que significa que não mais elementos se movem entre A e B.$A' = B' = \emptyset$

Questão:

Como provar que esse algoritmo termina eventualmente? Não encontrei uma função potencial conveniente que possa ser estritamente minimizada ou maximizada pelo algoritmo. Tentei, sem êxito, algumas funções: a função mas não está aumentando a cada iteração. A função mas não está diminuindo a cada iteração. A função parece não estar diminuindo a cada iteração. A função$\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 não estar aumentando a cada iteração. Então, qual é a função potencial conveniente que pode ser mostrada para aumentar ou diminuir a cada iteração? Ou devemos mostrar que a função diminui, mas não a cada iteração (após algumas iterações)? Como ?

Notas:

• Os pontos mais próximos de em um conjunto significam: os pontos (exceto ) em , tendo a menor distância euclidiana de . Você pode usar para simplificar a análise.x S k x S x k = $k$$x$$S$$k$$x$$S$$x$$k = 1$
• Não sei se isso pode ajudar ou não, mas tenho a seguinte propriedade para meus conjuntos iniciais : inicialmente , se for o ponto mais próximo para e é o ponto mais próximo de então sempre . Isto intuitivamente significa que os pontos em estão mais perto de de pontos em .$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$
• Se isso facilita a análise: é totalmente possível considerar uma versão ligeiramente diferente do algoritmo em que, assim que um ponto de deve ser movido para , ele é movido de para (sem passar por ), e vis versa para .$A$$B$$A$$B$$A'$$B$

Aqui está a solução para o caso :$k = 1$

Suponha que o algoritmo não termine. Como existe um número finito de estados do algoritmo (atribuições de pontos para e ), o estado do algoritmo deve se repetir em um ciclo. Como o ciclo passa por diferentes estados, deve haver um ponto que alterne entre e infinitamente.$A$$B$$A$$B$

Seja um ponto que muda infinitamente com frequência neste ciclo. Escolha da primeira iteração do algoritmo no ciclo durante o qual muda de para . Para mudar para , deve haver pelo menos um ponto em , com . Escolha arbitrariamente o menor ponto com esse rótulo; defina uma função para que . Observe que também deve alternar entre e infinitamente (porque se permaneceu em$x$$x$$B$$A$$x$$A$$x'$$A$$d_x^C > dist(x, x')$$f$$f(x) = x'$$x'$$A$$B$$x'$$A$permanentemente, o mesmo ocorreria com ), para que possamos tomar etc.$x$$f(f(x)), f(f(f(x))),$

Como temos um número finito de pontos, as iterações de f devem eventualmente repetir: para alguns . Agora observe as seqüências correspondentes de distâncias de C: . Como se repete, essa sequência não pode estar diminuindo uniformemente. Deve haver uma iteração tal que$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$

Agora, e estão próximos o suficiente um do outro para causar um ao outro estar em , se um deles estiver. Ou seja, eles estão mais próximos um do outro que : (da definição de )$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$

Portanto, assim que e estiverem em , eles se manterão em para sempre (consulte as linhas 1-2 do algoritmo). Isso contradiz o fato de que todas as iterações de devem mudar de conjuntos infinitamente com frequência. Assim, para o caso em que , o algoritmo termina.f o ( x ) Uma Uma f k = $f^{o-1}(x)$$f^o(x)$$A$$A$$f$$k = 1$