5
Моя проблема заключается в следующем:Минимизация расстояния спаривания точек
Given a number of 2n points, I can calculate the distance between all points
and get a symmetrical matrix.
Can you create n pairs of points, so that the sum of the distance of all pairs is
minimal?
EDIT: Every point has to be in one of the pairs. Which means that
every point is only allowed to be in one pair.
я наивно пытался использовать венгерский алгоритм и надеется, что он может дать мне задание, так что задания симметричны. Но это явно не сработало, так как у меня нет двудольного графа.
После поиска я нашел Stable roommates problem, который, похоже, похож на мою проблему, но разница в том, что он просто пытается найти совпадение, но не пытается свести к минимуму какое-то расстояние.
Кто-нибудь знает похожие проблемы или даже решение? Я что-то пропустил? Проблема действительно не кажется такой трудной, но я просто не мог найти оптимальное решение.
Итак, если я правильно понял это, у вас есть симметричная матрица, содержащая расстояние между каждой точкой? Почему бы не превратить эту матрицу в набор, отсортированный по расстоянию [start_point, end_point, distance] и выбрать первые n пар? – Yay295
Каждой точке разрешено находиться только в одной паре. Это не гарантируется, если я только сортирую по расстоянию. Я должен добавить это к описанию проблемы. – the
Хм, это усложняет ситуацию. Однако вы уверены, что венгерский алгоритм не будет работать? Вместо того, чтобы рассматривать его как полный неориентированный граф, разделите каждую точку на две точки (источник и место назначения) и просмотрите ее как полный двунаправленный ориентированный граф. – Yay295