Простой способ доказать, что этот алгоритм в конечном итоге завершается

10

Введение и обозначения:

Вот новая и простая версия моего алгоритма, которая, кажется, заканчивается (согласно моим экспериментам), и теперь я хотел бы доказать это.

Пусть обозначение относится к p- мерной точке данных (вектору). У меня есть три набора A, B и C, так что | A | = n , | Б | = м , | C | = l : A = { x i | я = 1 , . , , n } B = { x j | j = n + 1xiRpp|A|=n|B|=m|C|=l

A={xi|i=1,..,n}
C = { x u | у = п + т + 1 , . , , n + m + l }
B={xj|j=n+1,..,n+m}
C={xu|u=n+m+1,..,n+m+l}

Для пусть d A x i обозначает среднее евклидово расстояние от x i до k ближайших точек в A ; и д С й я обозначаю среднее евклидово расстояния от й я ее к ближайшей точке в C .kNdxiAxikAdxiCxikC

Алгоритм:

ABBCACB

  • A={xiAdxiA>dxiC}
  • A=AAB=BA
  • B={xiBdxiA<dxiC
  • B=BBA=AB
  • ABBA|A|k|B|k

Алгоритм заканчивается в двух случаях:

  • |A||B|k
  • A=B=

Вопрос:

xAdxC+xBdxAxAdxA+xBdxCxAdxA+xBdxBxAdxB+xBdxA

Ноты:

  • kxSkxSxk=1
  • A,B,CxiB,xjAxbCxixaCxjdistance(xi,xb)<distance(xj,xa)BCA
  • ABABAB
SHN
источник
3
Почему вы заинтересованы в этом конкретном алгоритме?
1
Шна: Что вы хотите сделать с набором точек, произвольно разделенных на три набора?
4
@shna Знание цели и задач алгоритма может привести к улучшению интуиции и, следовательно, помочь в решении проблемы.
ABBCACB
Миграция в теорию была отклонена.

Ответы:

2

k=1

ABAB

xxBAxAxAdxC>dist(x,x)ff(x)=xxABxAxf(f(x)),f(f(f(x))),

fn(x)=fm(x)m>ndf(x)C,df2(x)C,...dfn(x)C,...odfo1(x)Cdfo(x)C

fo1(x)fo(x)ACdfo(x)Cdfo1(x)C>dist(fo1(x),fo(x))f

fo1(x)fo(x)AAfk=1

причинный
источник
k=1
1
@shn Я не уверен, почему вы критикуете методику доказательства того, кто был более успешным в решении вашей проблемы, чем вы. Особенно, когда в вашем собственном вопросе перечислено четыре неудачных попытки использовать предпочитаемую вами технику.
Дэвид Ричерби
1
k>1