Łatwy sposób na udowodnienie, że ten algorytm ostatecznie się kończy

Wprowadzenie i notacje:

Oto nowa i prosta wersja mojego algorytmu, która wydaje się kończyć (zgodnie z moimi eksperymentami), a teraz chciałbym to udowodnić.

Niech notacja odnosi się do wymiarowego punktu danych (wektora). Mam trzy zestawy A, B i C, takie że , $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\}$

Biorąc pod uwagę , niech oznacza średnią odległość euklidesową od do jej najbliższych punktów w ; i oznacza średnią odległość euklidesową z jego najbliższego punktów . $k \in \mathbb{N^*}$ $d_{x_i}^A$ $x_i$ $k$ $A$ $d_{x_i}^C$ $x_i$ $k$ $C$

Algorytm:

Mam następujący algorytm, który iteracyjnie modyfikuje zestawy A i B, przenosząc niektóre wybrane elementy z A na B i odwrotnie, a C pozostaje zawsze takie samo (nie zmieniaj). Upraszczając: celem algorytmu jest lepsze rozdzielenie zbiorów i taki sposób, aby „punkty były bardziej podobne do punktów znanego ustalonego zestawu ” i „punkty są w końcu samopodobne i dalej od i końcowego zestawu ": $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'$
Powtarzaj (1), (2), (3) i (4), dopóki: (żaden element nie przesunie się z na lub z na , czyli A 'i B' się opróżnią) lub ( lub ) $A$ $B$ $B$ $A$ $|A| \leq k$ $|B| \leq k$

Algorytm kończy się w dwóch przypadkach:

kiedylubstaje się mniejsza lub równa $|A|$ $|B|$ $k$
lub najbardziej standardowy przypadek, gdy , co oznacza, że nie ma już więcej elementów między A i B. $A' = B' = \emptyset$

Pytanie:

Jak udowodnić, że ten algorytm ostatecznie się kończy? Nie znalazłem wygodnej potencjalnej funkcji, którą algorytm może ściśle zminimalizować lub zmaksymalizować. Próbowałem bezskutecznie niektórych funkcji: funkcja ale nie zwiększa się przy każdej iteracji. Funkcja ale nie zmniejsza się przy każdej iteracji. Funkcja wydaje się nie zmniejszać przy każdej iteracji. Funkcja $\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$ wydaje się nie rosnąć z każdą iteracją. Jaka jest wygodna potencjalna funkcja, którą można zwiększyć lub zmniejszyć przy każdej iteracji? Czy też powinniśmy pokazać, że funkcja maleje, ale nie przy każdej iteracji (raczej po kilku iteracjach)? W jaki sposób ?

Uwagi:

najbliżej punktów w zbiorze , oznacza: punktów (inne niż ) w , mające najmniejszą euklidesową odległość . Możesz po prostu wziąć aby uprościć analizę. $k$ $x$ $S$ $k$ $x$ $S$ $x$ $k = 1$
Nie wiem, czy to może pomóc, czy nie, ale mam następującą właściwość dla moich początkowych zestawów : początkowo , jeśli jest najbliższym punktem do i to najbliższy punkt do a następnie zawsze . Ten intuicyjnie oznacza, że punkty są bliżej niż punktach . $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$
Jeśli to ułatwi analizę: całkowicie możliwe jest rozważenie nieco innej wersji Algorytmu, w której punkt z punktu powinien zostać przeniesiony do punktu , zostaje on przeniesiony z punktu do punktu (bez omijania punktu ), a vis versa dla . $A$ $B$ $A$ $B$ $A'$ $B$

— shn
źródło

Dlaczego interesuje Cię ten konkretny algorytm?

shna: Co chcesz zrobić ze zbiorem punktów arbitralnie podzielonych na trzy zestawy?

@shna Znajomość celu i celu algorytmu może prowadzić do poprawy intuicji, a tym samym pomóc w rozwiązaniu problemu.

@RichardRast Aby wyjaśnienie było proste: celem jest lepsze rozdzielenie zbiorów i tak aby „punkty były bardziej podobne do punktów znanego ustalonego zestawu ” i „punkty są w końcu podobne do siebie i dalej od i końcowego zestawu ”.

A $A$

B $B$

C $C$

A $A$

C $C$

B $B$

— shn

Migracja do cstheory została odrzucona.

Oto rozwiązanie dla przypadku : $k = 1$

Załóżmy, że algorytm się nie kończy. Ponieważ istnieje skończona liczba stanów algorytmu (przypisanie punktów do i ), stan algorytmu musi się powtarzać w cyklu. Ponieważ cykl przechodzi przez różne stany, musi istnieć punkt, który przełącza się między i nieskończenie często. $A$ $B$ $A$ $B$

Niech będzie punktem, który zmienia się nieskończenie często w tym cyklu. Odebrać pierwszej iteracji algorytmu w cyklu, podczas której zmienia się z do . Dla , aby przełączyć na , musi być co najmniej jeden punkt w , a . Arbitralnie wybierz najmniejszy taki punkt; zdefiniuj funkcję tak aby $x$ $x$ $B$ $A$ $x$ $A$ $x'$ $A$ $d_x^C > dist(x, x')$ $f$ . Zauważ, że również musi przełączać się między i nieskończenie często (ponieważ jeśli pozostanie w stałe, to też ), więc możemy wziąć itd. $f(x) = x'$ $x'$ $A$ $B$ $x'$ $A$ $x$ $f(f(x)), f(f(f(x))),$

Ponieważ mamy skończoną liczbę punktów, iteraty f muszą ostatecznie powtórzyć: dla niektórych . Spójrzmy teraz na odpowiednich sekwencji odległości od C: $f^n(x) = f^m(x)$ $m > n$ $d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ...$ . Ponieważ się powtarza, sekwencja ta nie może być równomiernie zmniejszana. Musi istnieć iteracja , że $o$ $d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Teraz i są wystarczająco blisko siebie, aby spowodować, że będą w , jeśli jeden z nich jest. Oznacza to, że są bliżej siebie niż którykolwiek z nich to : $f^{o-1}(x)$ $f^o(x)$ $A$ $C$ (z definicji ) $d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$ $f$

Tak więc, gdy tylko i znajdą się w , będą się utrzymywać w zawsze (patrz wiersze 1-2 algorytmu). Jest to sprzeczne z faktem, że wszystkie iteracje muszą zmieniać zestawy nieskończenie często. Zatem w przypadku, gdy , algorytm kończy się. $f^{o-1}(x)$ $f^o(x)$ $A$ $A$ $f$ $k = 1$

— przyczynowy
źródło

Jest to w jakiś sposób skomplikowane i może być pokazane tylko dla

. Raczej jest o wiele lepiej, jeśli możemy wyprowadzić potencjalną funkcję, która może być zwiększana lub zmniejszana przy każdej iteracji. Lub może wykazać, że rośnie lub maleje po „niektórych” iteracjach zamiast 1.k=1 $k = 1$

— shn

@shn Nie jestem pewien, dlaczego krytykujesz wybór techniki dowodu kogoś, kto odniósł większy sukces w rozwiązaniu twojego problemu niż ty. Zwłaszcza, gdy twoje własne pytanie wymienia cztery nieudane próby użycia preferowanej techniki.

— David Richerby

@DavidRicherby Nie krytykuję;) Właściwie rozmawiałem o tym rozwiązaniu z „sprawcą” (który udzielił tej odpowiedzi) na IRC i stwierdziliśmy, że nie będzie możliwe udowodnienie tego w ten sposób dla

; więc wywnioskowaliśmy, że o wiele lepiej jest wyprowadzić potencjalną funkcję, która może być zmniejszana przy każdej iteracji. Mój komentarz był po prostu informacyjny. $k > 1$

— shn