Блог

Я пытаюсь найти эффективный алгоритм для решения следующей задачи: даны два разных набора, оба размера N. Каждый элемент в двух наборах имеет координаты (x, y). Задача состоит в том, чтобы оптимизировать пары между этими двумя наборами таким образом, чтобы максимальное расстояние между сопряженными элементами при заданном сопряжении было сведено к минимуму. Я нашел только алгоритмы, которые имеют дело с суммой квадратов всех расстояний между парными элементами или наименьшим расстоянием между любыми двумя точками из двух разных наборов. Есть идеи, как этого можно достичь за разумное время выполнения? или назовите алгоритм, который может здесь помочь.

Например: задан список из N пар точек, которые связаны с местоположениями — (x0, y0), (x1,y1), (x2,y2)….(xn-1, yn-1), назовите их a0, a1,a2 … aN-1 соответственно

И еще один список из N пар разных точек (местоположений) (x0, y0), (x1,y1), (x2,y2)….(xn-1, yn-1), назовите их b0, b1, b2 … bN-1 соответственно

Как я могу связать все элементы (каждый элемент представляет собой пару точек) из списка 1 (a0, a1, a2 … aN-1) с другими элементами в списке 2 (b0, b1, b2 … bN-1), чтобы мы выбрали кратчайшие расстояния? в конце концов, нам нужно будет вывести максимальное расстояние среди всех минимальных расстояний, которые мы нашли для каждого из элементов.

Спасибо