Наилучшее соответствие в двудольном графике (например, сопоставление меток с точками на графике)

Я пытаюсь извлечь семантику из графических графиков xy, где точки отображаются, а некоторые или все имеют метки. Метка нанесена «рядом с точкой». так что человек обычно может понять, какой ярлык идет с какой точкой. Например, на этом графике ясно, какая метка (число) принадлежит какой точке (*), и алгоритм, основанный на евклидовом расстоянии, будет работать. (Метки и точки не имеют семантического порядка - например, график рассеяния)

<code> *1
    *2

        *3

      *4
</code>

На перегруженных участках авторское программное обеспечение / человек может размещать метку в разных направлениях, чтобы избежать дублирования. Например в

<code>1**2
 **4
 3
</code>

Человек-читатель обычно может определить, какой ярлык связан с каким ярлыком.

Одно решение, которое я бы принял, состояло бы в создании евклидовой матрицы расстояний и перемешивании строк, чтобы получить минимум функции (например, суммированные квадраты расстояний на диагонали или другую эвристику). Во втором примере (с точками, помеченными a, b, c, d по часовой стрелке от угла NW) мы имеем матрицу расстояний (до 1 d.p.)

<code>             a   b   c   d
 1ab2    1  1.0 2.0 2.2 1.4    
  dc4    2  2.0 1.0 1.4 2.2
  3      3  2.0 2.2 1.4 1.0
         4  2.2 1.4 1.0 2.0
</code>

и нам нужно пометитьa1 b2 c4 d3, Обмен строк 3 и 4 дает минимальную сумму диагонали. Вот более сложный пример, в котором простой выбор ближайшего может потерпеть неудачу

<code> *1*2*5
  **4
  3 *6
</code>

Если это будет решено, то мне нужно перейти к случаям, когда количество меток может быть меньше или больше, чем количество баллов.

Если алгоритм является стандартным, я был бы признателен за указатель на Java с открытым исходным кодом (например, математика JAMA или Apache)

ПРИМЕЧАНИЕ: этот ТАК ответСвязывание ближайших точек с дорожкой не совсем подходит в качестве ответа, потому что указан путь через точки.

Ответы на вопрос(3)

Ваш ответ на вопрос