Назначение S-D с помощью релаксации Лагранжа
[ возвращает таблицу назначений, assignments,cost,solutionGap] = assignsd(costmatrix)assignments, обнаружений к трекам путем нахождения неоптимального решения задачи назначения S-D с помощью релаксации Лагранжа. Стоимость каждого потенциального присвоения содержится в матрице затрат, costmatrix. Алгоритм заканчивается, когда погрешность достигает ниже 0,01 (1 процент) или если количество итераций достигает 100.
costmatrix - n-мерная матрица затрат, где costmatrix(i,j,k ...) определяет стоимость n-кортежа (i,j,k, ...) в назначении. Индекс ' 1 ' всех размерностей в costmatrix представляет фиктивное измерение или ложную дорожку и используется для выполнения задачи назначения. Индекс 1, являющийся манекеном, может быть частью нескольких n-кортежей. Индекс можно назначить более одного раза. Типичное значение затрат для costmatrix(1,1,1,1, ...) равен 0.
Все входы могут быть одинарной или двойной точности, но все они должны быть одинаковой точности.
Функция также возвращает погрешность решения, solutionGapи общая стоимость заданий, cost.
[ также задает требуемый максимальный зазор, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap)desiredGap, между двойственным и возможными решениями в качестве скаляра. Зазор контролирует качество решения. Значения обычно варьируются от 0 до 1. Значение 0 означает, что двойственные и возможные решения одинаковы.
[ также задает максимальное количество итераций, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations)maxIterations.
[ также задает алгоритм назначения, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations,algorithm)algorithm.
Метод релаксации Лагранжа вычисляет неоптимальное решение задачи назначения S-D. Метод расслабляет задачу назначения S-D к задаче назначения 2-D с помощью множества лагранжевых умножителей. Задача расслабленного назначения 2-D обычно известна как двойственная задача, которая может быть решена оптимально с помощью алгоритмов, подобных алгоритму Мункреса. Ограничения затем налагаются на двойственное решение путем решения нескольких задач назначения 2-D, чтобы получить возможное решение исходной задачи. Стоимость двойного решения и возможное решение служат более низкими и верхними границами оптимальной стоимости, соответственно. Алгоритм итеративно пытается минимизировать разрыв между двумя и возможными решениями, обычно известными как двойная погрешность. Итерация останавливается, когда двойной промежуток ниже желаемой погрешности или достигнуто максимальное количество итераций.
При использовании алгоритма аукциона assignsd функция использует алгоритм Эвристического Обновления Цены, чтобы обновить множители Лагранжа. При использовании алгоритмов Munkres и JV функция использует алгоритм Accelerated Subgradient Update.
Для матриц затрат с четко определенными решениями, такими как пассивная ассоциация с высокоточными датчиками, зазор решения сходится в пределах 0,05 (5 процентов) приблизительно за 100 итераций.
Поскольку оптимальное решение неизвестно, зазор решения может быть ненулевым, даже когда возвращенное решение оптимально.
[1] Deb, S., Yeddanapudi, M., Pattipati, K., and Bar-Shalom, Y. (1997). Обобщенный алгоритм назначения SD для оценки состояния мультисенсор-мультитаргет. Транзакции IEEE по аэрокосмическим и электронным системам, 33 (2), 523-538.
[2] Блэкман, Сэмюэль и Роберт Пополи. Проект и анализ современных систем слежения. Norwood, MA: Artech House, 1999. (1999)
