Оптимизация из частичного решения: минимизировать сумму расстояний между парами

У меня есть проблема, которая мне нравится, и я люблю думать о решениях, но, к сожалению, я застрял. Надеюсь, тебе тоже понравится. Задача гласит:

У меня есть два списка 2D точек (скажем, A и B), и мне нужно объединить точки из A с точками из B, при условии, что сумма расстояний во всех парах минимальна. Пара содержит одну точку из A и одну из B, точку можно использовать только один раз, и следует создать как можно больше пар (например, min (length (A), length (B)) ) .

Я сделал простой пример, где цвет обозначает, из какого списка находится точка, а черные соединения - это решение.

Хотя это хорошая проблема и я подозреваю, что она NP-трудная, она становится лучше. Я могу опираться на существующие решения. Предположим, у меня есть два списка и соответствующее решение (то есть набор пар), тогда проблема, которую мне нужно решить, состоит в том, чтобы повторно оптимизировать это решение, когда точка добавляется или удаляется из любого списка.

Я, к сожалению, не был способен предложить любой алгоритм без перебора, дающий оптимальное решение. Я надеюсь, ты сможешь. Любой алгоритм приветствуется на любом (псевдо) языке, предпочтительно C #.