Exponenta Banner
exponenta event banner

assignkbestsd

K-лучшее решение S-D, которое минимизирует общую стоимость назначения

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

Синтаксис

[присвоения, затраты, solityGap] = assignkbestsd (costmatrix)
[присвоения, затраты, solityGap] = assignkbestsd (costmatrix, k)
[присвоения, затраты, solityGap] = assignkbestsd (costmatrix, k, desiredGap)
[назначения, затраты, solityGap] = assignkbestsd (costmatrix, k, desiredGap, maxIterations)
[назначения, стоимость, solityGap] = assignkbestsd (costmatrix, k, desiredGap, maxIterations, алгоритм)

Описание

[assignments,cost,solutionGap] = assignkbestsd(costmatrix) возвращает таблицу assignments обнаружения треков путем поиска лучшего решения S-D, которое минимизирует общую стоимость назначений. Алгоритм использует лагранжевую релаксацию для преобразования задачи назначения S-D в соответствующую задачу назначения 2-D и затем решает задачу 2-D. Стоимость каждого потенциального назначения содержится в матрице затрат, 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 К-лучших решений S-D. Функция находит K оптимальных решений, которые минимизируют общую стоимость. Во-первых, функция находит наилучшее решение. Затем функция использует алгоритм Мурти для генерации разделенных матриц затрат. Наконец, функция получает оставшиеся 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 array
    {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

Алгоритм назначения для решения задачи назначения 2-D, указанный как 'munkres' для алгоритма Манкра, 'jv' для алгоритма Йонкера-Волгенанта, или 'auction' для алгоритма аукциона.

Пример: 'jv'

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

свернуть все

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

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

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

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

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

Алгоритмы

Все числовые входные данные могут иметь одну или двойную точность, но все они должны иметь одинаковую точность.

Ссылки

[1] Popp, R.L., Pattipati, K. и Bar Shalom, Y. «M-best S = D Алгоритм назначения с применением к многозначному отслеживанию». Сделки IEEE по аэрокосмическим и электронным системам, 37 (1), 22-39. 2001.

[2] Деб, С., Йедданапуди, М., Паттипати, К., и Бар-Шалом, Ю. (1997). «Обобщенный алгоритм назначения SD для оценки многосенсорного-многоцелевого состояния». Сделки IEEE по аэрокосмическим и электронным системам, 33 (2), 523-538.

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

Создание кода C/C + +
Создайте код C и C++ с помощью MATLAB ® Coder™

.

См. также

Функции

Представлен в R2018b

Документация по комплекту инструментов для слияния и отслеживания датчиков

Поддержка