У меня есть проблема, которая мне нравится, и я обожаю думать о решениях, но к сожалению. Надеюсь, вам тоже понравится. Проблема заключается в следующем:
У меня есть два списка двумерных точек (например, A и B) и необходимо соединить точки из A с точками из B при условии, что сумма расстояний во всех парах минимальна. Пара содержит одну точку из A и одну из B, точка может использоваться только один раз, и должно быть создано как можно больше пар (т.е. min(length(A), length(B))).
Я сделал простой пример, где цвет обозначает, из какого списка находится точка, а черные соединения - это решение.
Хотя это хорошая проблема, и я подозреваю, что NP-жесткий, он становится приятнее. Я могу опираться на существующие решения. Предположим, что у меня есть два списка и соответствующее решение (т.е. Множество пар), то проблема, которую мне нужно решить, состоит в том, чтобы повторно использовать это решение, когда точка добавляется или удаляется из любого списка.
Я, к сожалению, не смог придумать какой-либо алгоритм без грубой силы, обеспечивающий оптимальное решение. Надеюсь, ты сможешь. Любой алгоритм оценивается на любом (псевдо) языке, предпочтительно С#.
