Exponenta Banner
exponenta event banner

assignkbest

Назначение с использованием k-best глобального ближайшего соседа

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

Синтаксис

[назначения, unassignedrows, unassignedcolumns, стоимость] = assignkbest (costmatrix, costofnonassignment)
[назначения, unassignedrows, unassignedcolumns, стоимость] = assignkbest (costmatrix, costofnonassignment, k)
[назначения, unassignedrows, unassignedcolumns, стоимость] = assignkbest (costmatrix, costofnonassignment, k, алгоритм)

Описание

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment) возвращает таблицу назначений, assignmentsобнаружения дорожек с использованием алгоритма Йонкера-Волгенера. Алгоритм находит решение глобального ближайшего соседа (GNN), которое минимизирует общую стоимость назначений.

Стоимость каждого потенциального назначения содержится в матрице затрат, costmatrix. Каждая запись матрицы представляет стоимость возможных назначений. Строки матрицы представляют дорожки, а столбцы представляют обнаружения. Все возможные присвоения представлены в матрице затрат. Чем ниже стоимость, тем больше вероятность выполнения назначения. Каждая дорожка может быть назначена максимум одному обнаружению, и каждая дорожка может быть назначена максимум одному обнаружению. Если число строк больше количества столбцов, некоторые дорожки не назначаются. Если число столбцов превышает число строк, некоторые обнаруженные элементы не назначаются. Можно задать запись costmatrix кому Inf запретить назначение.

costofnonassignment представляет собой стоимость оставления дорожек или обнаружений без назначения. Более высокие значения увеличивают вероятность назначения каждого существующего объекта.

Все входные данные должны быть одинарной или двойной точностью.

Функция возвращает список неназначенных дорожек, unassignedrows, список неназначенных обнаружений, unassignedcolumnsи стоимость уступки, cost.

пример

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k)также указывает число, k, из k-лучших глобальных ближайших соседних решений, которые минимизируют общую стоимость назначений. Помимо наилучшего решения, функция использует алгоритм Мурти для поиска оставшихся решений k-1.

[assignments,unassignedrows,unassignedcolumns,cost] = assignkbest(costmatrix,costofnonassignment,k,algorithm) также определяет алгоритм, algorithm, для поиска назначений.

Примеры

свернуть все

Открыть сценарий в реальном времени

Создайте матрицу затрат, содержащую запрещенные назначения. Затем используйте assignkbest функция для поиска 5 лучших решений.

Настройте матрицу затрат, чтобы она содержала некоторые запрещенные или недопустимые назначения путем вставки Inf в матрицу.

costMatrix = [10 5 8 9; 7 Inf 20 Inf; Inf 21 Inf Inf; Inf 15 17 Inf; Inf inf 16 22];
costOfNonAssignment = 100;

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

[assignments,unassignedrows,unassignedcols,cost] = ...
    assignkbest(costMatrix,costOfNonAssignment,5)
assignments=5×1 cell array
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}
    {4x2 uint32}


unassignedrows=5×1 cell array
    {[3]}
    {[3]}
    {[3]}
    {[4]}
    {[5]}


unassignedcols=5×1 cell array
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}
    {0x1 uint32}


cost = 5×1

   147
   151
   152
   153
   154

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

свернуть все

Матрица затрат, заданная как матрица M-by-N. M - количество назначаемых дорожек, а N - количество назначаемых обнаружений. Каждая запись в матрице затрат содержит стоимость назначения дорожки и обнаружения. Матрица может содержать Inf для указания на то, что назначение запрещено. Матрица затрат не может быть разреженной матрицей.

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

Стоимость неназначения, определяемая как скаляр, двухэлементный вектор скаляров или двухэлементный клеточный массив векторов.

  • Если указан как скаляр, он представляет собой стоимость оставления дорожек или обнаружений неназначенными. Более высокие значения увеличивают вероятность назначения каждого объекта. Значение не может быть установлено в Inf.

  • Если указан как двухэлементный скаляр, первый элемент представляет стоимость оставления обнаружений без назначения, а второй элемент представляет стоимость оставления дорожек без назначения.

  • При определении в качестве двухэлементной ячейки векторов каждый элемент в первом векторе представляет стоимость оставления конкретного обнаружения неназначенным, а каждый элемент второго вектора представляет стоимость оставления конкретной дорожки неназначенным. Длина первого вектора равна количеству обнаружений, а длина второго вектора равна количеству дорожек.

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

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

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

Алгоритм назначения, указанный как 'jv' для алгоритма Йонкера-Волгенера, 'munkres' для алгоритма Манкра, 'auction' для алгоритма аукциона, или 'matchpair' для алгоритма пары совпадений. Когда 'jv' Для повышения производительности алгоритма функция использует эвристику, определенную в [3].

Пример: 'jv'

Типы данных: char | string

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

свернуть все

Назначение дорожек обнаружениям, возвращаемых в виде массива ячеек k-элементов. k - количество лучших решений. Каждая ячейка содержит матрицу Li-by-2 пар индексов дорожки и назначенных индексов обнаружения. Li - количество пар назначения в i-ой ячейке раствора. Первый столбец каждой матрицы содержит индексы дорожки, а второй столбец содержит назначенные индексы обнаружения.

Индексы неназначенных дорожек, возвращаемые в виде массива ячеек k-element. Каждая ячейка является вектором Pi, где Pi = M-Li - количество неназначенных строк в i-ой ячейке. Каждый элемент является индексом строки, которой не назначены столбцы. k - количество лучших решений.

Типы данных: uint32

Индексы неназначенных обнаружений, возвращаемые в виде массива ячеек k-element. Каждая ячейка является вектором Qi, где Qi = M-Li - количество неназначенных обнаружений в i-ой ячейке. Каждый элемент является индексом столбца, которому не назначены строки. k - количество лучших решений.

Типы данных: uint32

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

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

Ссылки

[1] Мурти, Катта Г. «Алгоритм ранжирования всех назначений в порядке увеличения стоимости». Исследование операций 16, № 3 (1968): 682-687.

[2] Сэмюэл Блэкман и Роберт Пополи. Проектирование и анализ современных систем слежения, Artech House, 1999.

[3] Миллер, M.L., et al. «Оптимизация метода рангового назначения Мурти». IEEE Transactions on Aerospace and Electronic Systems, vol. 33, no. 3, July 1997, pp. 851-62. DOI.org (Crossref), дой: 10.1109/7.599256.

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

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

.

См. также

Функции

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

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

Поддержка