assignkbestsd

Решение K-best S-D, которое минимизирует общую стоимость присвоения

Описание

[assignments,cost,solutionGap] = assignkbestsd(costmatrix) возвращает таблицу assignments из обнаружений к дорожкам путем нахождения лучшего решения S-D, которое минимизирует общую стоимость присвоений. Алгоритм использует лагранжевую релаксацию, чтобы преобразовать проблему присвоения S-D в соответствующую 2D проблему присвоения и затем решает 2D задачу. Стоимость каждого потенциального присвоения содержится в матрице стоимости, costmatrix.

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] = assignkbestsd(costmatrix,k) также задает номер, k из K - лучшие решения S-D. Функция находит оптимальные решения K, которые минимизируют общую стоимость. Во-первых, функция находит лучшее решение. Затем функция использует алгоритм Murty, чтобы сгенерировать разделенные матрицы стоимости. Наконец, функция получает остающийся K - 1 минимальное экономичное решение для каждой разделенной матрицы.

[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap) также задает желаемый максимальный разрыв, desiredGap, между двойным решением и выполнимым решением. Разрыв управляет качеством решения. Значения обычно лежат в диапазоне от 0 до 1. Значение 0 средних значений двойные и выполнимые решения является тем же самым.

[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations) также задает максимальное количество позволенных итераций. desiredGap и maxIterations аргументы задают завершающие работу условия для алгоритма S-D.

[assignments,cost,solutionGap] = assignkbestsd(costmatrix,k,desiredGap,maxIterations,algorithm) также задает algorithm для нахождения присвоений.

Примеры

свернуть все

Найдите первые 5 лучших присвоений проблемы присвоения S-D. Установите желаемый разрыв на 0,01 и максимальное количество итераций к 100.

Загрузите матрицу стоимости.

load passiveAssociationCostMatrix.mat

Найдите эти 5 лучших решений.

[assignments,cost,solutionGap] = assignkbestsd(costMatrix,5,0.01,100)
assignments=5×1 cell
    {2x3 uint32}
    {3x3 uint32}
    {3x3 uint32}
    {3x3 uint32}
    {3x3 uint32}

cost = 5×1

  -34.7000
  -31.7000
  -29.1000
  -28.6000
  -28.0000

solutionGap = 5×1

         0
    0.0552
    0.0884
    0.1075
    0.1964

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

свернуть все

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

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

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

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

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

Пример: 0.05

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

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

Пример: 50

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

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

Пример: 'jv'

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

свернуть все

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

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

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

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

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

Алгоритмы

Все числовые входные параметры могут быть одинарные или двойная точность, но у них всех должна быть та же точность.

Ссылки

[1] Popp, R.L., Pattipati, K. и панель шалом, Y. "Алгоритм присвоения M-best S=D с приложением, чтобы мультипредназначаться для отслеживания". Транзакции IEEE на космических и электронных системах, 37 (1), 22-39. 2001.

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

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

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

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

Функции

Системные объекты

Введенный в R2018b

Для просмотра документации необходимо авторизоваться на сайте