Враховуючи список 2-х балів, знайдіть точку, найближчу до всіх інших точок - алгоритм, мова-агностик

Input: list of 2d points (x,y) where x and y are integers.

Distance: distance is defined as the Manhattan distance.
ie:
def dist(p1,p2)
return abs(p1.x-p2.x) + abs(p1.y - p2.y)

Що таке ефективний алгоритм пошуку точки, яка є найближчою до всіх інших точок.

Я можу лише думати про рішення грубої сили O (n ^ 2):

minDist=inf
bestPoint = null
for p1 in points:
dist = 0
for p2 in points:
dist+=distance(p1,p2)
minDist = min(dist,minDist)
bestPoint = argmin(p1, bestPoint)

в основному подивіться на кожну пару точок.

Відповіді:

11 за відповідь № 1

Зверніть увагу, що в 1-D точка, яка мінімізує суму відстаней до всіх точок, є медіаною.

У 2-D проблему можна вирішити в O(n log n) наступним чином:

Створіть відсортований масив x-координат і длякожен елемент масиву обчислює "горизонтальну" вартість вибору цієї координати. Горизонтальна вартість елемента - це сума відстаней до всіх точок, спроектованих на вісь X. Це можна обчислити за лінійний час, двічі просканувавши масив (один раз зліва направо і один раз у зворотному напрямку). Подібним чином створіть відсортований масив y-координат і для кожного елемента масиву обчисліть "вертикальну" вартість вибору цієї координати.

Тепер для кожної точки в вихідному масиві ми можемо обчислити загальну вартість для всіх інших точок у O(1) час шляхом додавання горизонтальних та вертикальних витрат. Тож ми можемо обчислити оптимальну точку в O(n). Таким чином, загальний час роботи становить O(n log n).

---

4 для відповіді № 2

Те, що ви шукаєте, є центр мас.

Ви в основному складаєте всі xs "і ys" разом і ділите маси всієї системи. Тепер у вас рівномірна маса за винятком частинок, нехай їх маса дорівнює 1.

тоді все, що вам потрібно зробити, - це підсумувати розташування частинок і розділити на кількість частинок.

скажімо, що маємо p1 (1,2) p2 (1,1) p3 (1,0)

// we sum the x"s

bestXcord = (1+1+1)/3 = 1

//we sum the y"s

bestYcord = (2+1)/3 = 1

отже p2 є найближчим.

вирішено в O (n)

---

1 для відповіді № 3

Починаючи з вашого початкового алгоритму, можлива оптимізація:

minDist=inf
bestPoint = null
for p1 in points:
dist = 0
for p2 in points:
dist+=distance(p1,p2)
//This will weed out bad points rather fast
if dist>=minDist then continue(p1)
/*
//Unnecessary because of new line above
minDist = min(dist,minDist)
bestPoint = argmin(p1, bestPoint)
*/
bestPoint = p1

Ідея полягає в тому, щоб викидати викиди якомога швидше. Це можна покращити ще:

• розпочати цикл p1 з евристичною "внутрішньою" точкою (Це створює користь minDist по-перше, так гірші очки швидше викидаються)
• почати цикл p2 з евристичними "зовнішніми" точками (це робить dist швидко підніматися, можливо, швидше викликати умову виходу

Якщо ви торгуєте розміром за швидкість, ви можете піти іншим шляхом:

//assumes points are numbered 0..n
dist[]=int[n+1]; //initialized to 0
for (i=0;i<n;i++)
for (j=i+1;j<=n;j++) {
dist=dist(p[i], p[j]);
dist[i]+=dist;
dist[j]+=dist;
}
minDist=min(dist);
bestPoint=p[argmin(dist)];

якому потрібно більше місця для масиву dist, алеобчислює кожну відстань лише один раз. Це має перевагу в тому, що він краще підходить для завдання типу "отримати N найкращих балів" і для метрик, що вимагають великих обчислень. Я підозрюю, що це не принесе нічого для метрики Манхеттена, на архітектурі x86 або x64: доступ до пам'яті буде сильно домінувати в розрахунку.

---