Я ищу подходящий алгоритм для решения следующей проблемы:
Для вектора v (Nx1, double, single) мне нужно найти наборы элементов этого вектора (пары), которые удовлетворяют следующим условиям:
Каждый элемент назначен только в одной паре
сумма расстояний между предметами по всем назначенным парам (нарушение) минимальна
в качестве входа функции используется дополнительный параметр vio_max, который ограничивает нарушение неприсвоения
[pair, dist, vio] = findpairs (v, vio_max)
ExampleA:
Ввод: v = [3,0 2,1 0,9 2,9 1,1], vio_max = 1,0
Вывод: пары = [1 4; 3 5], dist = [0,1; 0,2], vio = сумма (dist) = 0,3
и пункт 2.1 остается неназначенным (длина нечетная (v))
ExampleB:
Ввод: v = [3,0 2,1 0,9 2,9 1,1], vio_max = 0,15
Выход: пары = [1 4], dist = [0,1], vio = сумма (dist) = 0,1
Примечание:
Проблема полностью решена, см .: https://cs.stackexchange.com/questions/106214/find-separate-pairs-of-points-with-minimal-total-distance