Как эффективно найти ближайшую точку из отдельного набора точек к каждой точке другого набора в python - PullRequest
Новая
       12

Как эффективно найти ближайшую точку из отдельного набора точек к каждой точке другого набора в python

0 голосов
/ 23 января 2020

У меня есть этот код 

import random as rand


W = 2
H = 2
n_riders = 10
n_drivers = 20
riders_coords = []
drivers_coords = []
for n in range(n_riders):
    x = rand.uniform(-1,1)*W
    y = rand.uniform(-1,1)*H
    riders_coords.append((x, y))
for n in range(n_drivers):
    x = rand.uniform(-1,1)*W
    y = rand.uniform(-1,1)*H
    drivers_coords.append((x, y))
print(riders_coords)
print(drivers_coords)

Я хотел бы найти способ соединить каждого водителя с ближайшим водителем (евклидово расстояние), учитывая, что один водитель может быть назначен только одному водителю , Задача состоит в том, чтобы найти такие варианты, которые минимизируют общее расстояние. Все гонщики должны быть назначены водителю, если n_riders <= n_drivers. Кто-нибудь знает простой способ добиться этого, или я должен начать рисовать полигоны вороной с нуля? </p>

1 Ответ

2 голосов
/ 24 января 2020

Ваша проблема известна как евклидова задача присваивания или, альтернативно, евклидова проблема двудольного соответствия . Эта проблема изучалась академически, и есть некоторые известные алгоритмы, но я не нашел никакой информации о них, кроме как в научных статьях: c

  • Вайдья (1989) описал алгоритм, который работает за O(n^2.5 log n) время.
  • Agarwal, Efrat & Sharir (1999) описал алгоритм, который работает за O(n^(2 + ε)) время для сколь угодно малого ε.
  • Agarwal & Varadarajan (2004) описал алгоритм heuristi c, который выполняется за O(n^(1 + ε)) время и находит соответствие с ожидаемым весом в постоянном множителе истинного минимума.

Вероятно, вы можете найти еще несколько опубликованных алгоритмов или эвристик, выполнив поиск по литературе.

...