Геометрическая медиана - PullRequest
Новая
       13

Геометрическая медиана

0 голосов
/ 17 июня 2019

Я написал некоторый код для поиска

Геометрическая медиана для набора взвешенных точек

это основано на этом Google-kickstart испытании. Я не хочу лучшего решения, но хочу знать, что не так в моем коде

.Код выполняет итерацию с заданным значением точности 10 ^ -6 , чтобы получить значение, близкое к геометрической медиане.проблема, с которой я сталкиваюсь, это то, что она возвращает правильное значение для цифр до 10 ^ -3 и после этого идет не так.Я не могу понять, что происходит не так. Я также отметил, что изменение значения инициализации приводит к изменению результата , но не знаю почему. Код также остается в силе, если вес точек не учитывается здесь есть формулая использую, чтобы найти расстояние до каждой точки: max (abs (ix-kx), abs (iy-ky)) x (weight_of_i) (это Расстояние Чебышева )

вот итерационная функция, которую я использовал: 

#c = previous centre , stp =previous step ,listy_r = list of points(x,y,wt) ,k = previous sum of distances
def move_ct( c,stp,listy_r,k):  #calculates the minimum centre itrateviely , returns c--> center,stp-->step,k-->sum of distances
while True:
    tmp=list()
    moves = [(c[0], c[1]+stp), (c[0], c[1]-stp),
            (c[0]+stp, c[1]), (c[0]-stp, c[1])]
    for each in moves:tmp.append(sdist(listy_r, each))
    tmp_min = min(tmp)
    if tmp_min < k:
        k = tmp_min
        index = tmp.index(tmp_min)
        c = moves[index]
        break
    else:
        stp *= 0.5   
return (c,stp,k)

вот значения, которые я инициализировал:

  1. начальная геометрическаяцентр = центр тяжести взвешенных точек
  2. точность = 10 ** - 6
  3. шаг = половина расстояния между самой высокой и самой низкой координатами по x, y

Iприкрепил входной текстовый файл здесь , который содержит 10000 точек ( это тестовый пример 1 для большого ввода для запроса ) в формате одна точка для каждой строкии каждая точка имеет 3 параметра (x, y, вес), например: 980,69 595,86 619,03, где

  • 980,69 = координата x
  • 595,86= координата y
  • 619.03 = вес

результат 10000 баллов должен дать: 3288079343.471880 , но он дает 3288079343.4719906 в качестве результата. Обратите внимание, что он выключен только после 10 ^ -3.

...