У меня есть двудольный граф, где каждый узел имеет соединения (ребра) различной длины с узлами другого раздела. Я хочу выбрать ребра таким образом, чтобы сумма длин была как можно меньше, но при условии ограничения, что каждый узел должен иметь один и только один выбранный ребро (если количество узлов в двух разделах равно - если нет, один или несколько узлов не будут иметь выбранного края).Двусторонний граф, кратчайшее соединение?
Я хочу найти это совпадение как можно быстрее, но до сих пор я нашел подход грубой силы, чтобы попробовать каждую возможность, которая дает мне O (n!) Алгоритм - что невозможно. Есть ли у кого-то предложение для лучшего подхода?
Моя конкретная проблема заключается в следующем: я наблюдал более или менее случайные движущиеся 3D-частицы в двух разных временных точках. Я хочу знать, где движется каждая частица, т. Е. Отслеживать каждую частицу, предполагая, что их общее движение как можно короче.
Точный ответ будет один предложенный @tjhighley. Если вы можете жить с помощью «достаточно хорошего» алгоритма, вы можете начать с наивного соответствия, а затем подвергнуть его [* отжигу *] (https://en.wikipedia.org/wiki/Simulated_annealing). –