Exponenta Banner

assignsd

Присвоение S-D с помощью лагранжевой релаксации

свернуть все на странице

Синтаксис

[assignments,cost,solutionGap] = assignsd(costmatrix)
[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap)
[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations)
[assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations,algorithm)

Описание

[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.

Примеры

свернуть все

Открыть скрипт

Используйте assignsd, чтобы выполнить строгое присвоение без индекса 1.

Не наличие фиктивного индекса означает, что никакую сущность не оставляют неприсвоенной. Поэтому задайте матрицу стоимости, чтобы быть равновеликими.

costMatrix = rand(6,6,6);

Инициализируйте fullmatrix ко всему Inf. fullmatix является одним размером, больше, чем матрица стоимости во всех размерностях.

fullMatrix = inf(7,7,7);

Установите внутреннюю матрицу на costMatrix обеспечивать присвоения включающий индекс 1, чтобы иметь бесконечную стоимость.

fullMatrix(2:end,2:end,2:end) = costMatrix;
fullMatrix(1,1,1) = 0;
[assignments,cost,gapAchieved] = assignsd(fullMatrix,0.01,100);

Восстановите фактические индексы.

assignments = assignments - 1

assignments =

  6x3 uint32 matrix

   1   6   6
   2   4   3
   3   3   4
   4   1   2
   5   2   1
   6   5   5

Входные параметры

свернуть все

Стойте матрицы, заданной как n-мерный массив, где costmatrix(i,j,k ...) задает стоимость n-кортежа (i,j,k, ...) в присвоении. Индекс '1' на всех размерностях в costmatrix представляет фиктивное измерение или ложную дорожку и используется, чтобы завершить проблему присвоения. Индекс 1, будучи макетом, может быть частью нескольких n-кортежей. Индекс может быть присвоен несколько раз. Типичная величина затрат для costmatrix(1,1,1,1, ...) 0.

Типы данных: single | double

Желаемый максимальный разрыв между двойными и выполнимыми решениями, заданными как неотрицательный скаляр.

Пример: 0.05

Типы данных: single | double

Максимальное количество итераций, заданных как положительное целое число.

Пример: 50

Типы данных: single | double

Алгоритм присвоения для решения 2D проблемы присвоения, заданной как 'munkres' для алгоритма Munkres, 'jv' для алгоритма Jonker-Volgenant или 'auction' для Аукционного алгоритма.

Пример: 'jv'

Выходные аргументы

свернуть все

Присвоения дорожек к обнаружениям, возвращенным как P-by-N список присвоений. Присвоения типа, [1 1 Q 1] из четырехмерной матрицы стоимости может рассматриваться как сущность Q-1 от размерности 3, который оставили неприсвоенным. Величина затрат в (1,1,Q,1) задает стоимость не присвоения (Q-1) th сущность от размерности 3.

Общая стоимость решений, возвращенных как K - вектор элемента, где K является количеством лучших решений. Каждый элемент является скалярным значением, обобщающим общую стоимость решения проблемы присвоения.

Типы данных: single | double

Разрыв решения, возвращенный как положительная скалярная величина. Разрыв решения является разрывом дуальности, достигнутым между выполнимым и двойным решением. Значение разрыва около нуля указывает на качество решения.

Типы данных: single | double

Алгоритмы

  • Лагранжевый релаксационный метод вычисляет субоптимальное решение проблемы присвоения S-D. Метод ослабляет проблему присвоения S-D к 2D проблеме присвоения с помощью набора лагранжевых множителей. Расслабленная 2D проблема присвоения обычно известна как двойную проблему, которая может быть решена оптимально с помощью алгоритмов как алгоритм Munkres. Ограничения затем осуществляются на двойном решении путем решения нескольких 2D проблем присвоения получить выполнимое решение исходной проблемы. Стоимость двойного решения и выполнимого решения служит нижними и верхними границами на оптимальной стоимости, соответственно. Алгоритм итеративно пытается минимизировать разрыв между двойными и выполнимыми решениями, обычно известными как двойной разрыв. Итерация останавливается, когда двойной разрыв ниже желаемого разрыва, или максимальное количество итераций достигли.

  • При использовании аукционного алгоритма функция assignsd использует Эвристический Ценовой алгоритм Обновления, чтобы обновить лагранжевые множители. При использовании Манкров и алгоритмов JV, функция использует Ускоренный алгоритм Обновления Подградиента.

  • Для матриц стоимости с четко определенными решениями, такими как пассивная связь с датчиками высокой точности, разрыв решения сходится к в 0,05 (5 процентов) приблизительно в 100 итерациях.

  • Когда оптимальное решение неизвестно, разрыв решения может быть ненулевым, даже когда возвращенное решение оптимально.

Ссылки

[1] Деб, S., Yeddanapudi, M., Pattipati, K. и Панель Шалом, Y. (1997). Обобщенный алгоритм присвоения SD для мультицелевой мультидатчиком оценки состояния. Транзакции IEEE на Космических и Электронных системах, 33 (2), 523-538.

[2] Блэкмен, Сэмюэль и Роберт Пополи. Проект и анализ современных систем слежения. Норвуд, MA: Дом Artech, 1999. (1999)

Расширенные возможности

Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.

Смотрите также

Функции

Введенный в R2018b

Документация Sensor Fusion and Tracking Toolbox
Поддержка