matchpairs

Решите линейную задачу присвоения

Описание

пример

M = matchpairs(Cost,costUnmatched) решает линейную задачу присвоения для строк и столбцов матричного Cost. Каждая строка присвоена столбцу таким способом, которым минимизирована общая стоимость. costUnmatched задает стоимость на строку не присвоения каждой строки, и также стоимости для каждого столбца не ссорения присвоенного к каждому столбцу.

[M,uR,uC] = matchpairs(Cost,costUnmatched) дополнительно возвращает индексы для несопоставленных строк в uR и индексы для несопоставленных столбцов в uC.

пример

[___] = matchpairs(Cost,costUnmatched,goal) задает цель оптимизации с помощью любой из комбинаций выходного аргумента в предыдущих синтаксисах. goal может быть 'min' или 'max' произвести соответствия, которые или минимизируют или максимизируют общую стоимость.

Примеры

свернуть все

Присвойте продавцов рейсам, таким образом, что общая стоимость транспортировки минимизирована.

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

Эта таблица показывает стоимость для каждого продавца, чтобы полететь в каждый ключевой город.

DallasChicagoNew Йорк ГородSt. ЛуиFred$600$670$960$560Beth$900$280$970$540Sue$310$350$950$820Greg$325$290$600$540

Каждый город представляет возможность продаж. Если город пропущен, то компания терпит неудачу на среднем усилении дохода 2 000$.

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

C = [600 670 960 560
     900 280 970 540
     310 350 950 820
     325 290 600 540];

Используйте matchpairs присваивать продавцов городам с минимальной стоимостью. Задайте стоимость неприсвоения как 1 000, поскольку стоимость неприсвоения считается дважды, если строка и столбец остаются несопоставленными.

M = matchpairs(C,1000)
M = 4×2

     3     1
     2     2
     4     3
     1     4

matchpairs вычисляет наименее дорогой способ получить продавца в каждый город.

DallasChicagoNew Йорк ГородSt. ЛуиFred$600$670$960$560Beth$900$280$970$540Sue$310$350$950$820Greg$325$290$600$540

Совпадайте со строками к столбцам, когда у вас будет намного больше столбцов, чем строки в матрице стоимости.

Создайте 3 8 матрица стоимости. Поскольку у вас есть только три строки, matchpairs может произвести самое большее три соответствия с этими восемью столбцами.

rng default % for reproducibility
C = randi([10 100], 3, 8)
C = 3×8

    84    93    35    97    97    22    82    13
    92    67    59    24    54    48    97    87
    21    18    97    98    82    93    69    94

Используйте matchpairs совпадать со строками и столбцами матрицы стоимости. Чтобы получить максимальное количество соответствий, используйте большую стоимость неприсвоения (относительно величины записей в матрице стоимости). Задайте три выходных параметров, чтобы возвратить индексы несопоставленных строк и столбцов.

[M,uR,uC] = matchpairs(C,1e4)
M = 3×2

     3     2
     2     4
     1     8

uR =

  0x1 empty double column vector
uC = 5×1

     1
     3
     5
     6
     7

Пять из столбцов в C не являются соответствующими никаким строкам.

Присвойте такси до маршрутов, таким образом, что прибыль максимизируется.

Служба такси имеет несколько запросов поездки со всех концов города. Компания хочет диспетчеризировать свое ограниченное количество такси способом, которое делает большую часть денег.

Эта таблица показывает предполагаемый тариф такси для каждого из пяти запросов поездки. Только три из пяти запросов поездки могут быть заполнены.

Ride 1Ride 2Ride 3Ride 4Ride 5Cab A$5.70$6.30$3.10$4.80$3.50Cab B$5.80$6.40$3.30$4.70$3.20Cab C$5.70$6.30$3.20$4.90$3.40

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

P = [5.7 6.3 3.1 4.8 3.5
     5.8 6.4 3.3 4.7 3.2
     5.7 6.3 3.2 4.9 3.4];

Используйте matchpairs совпадать с такси до самых прибыльных поездок. Задайте три выходных параметров, чтобы возвратить любые несопоставленные строки и столбцы и 'max' опция, чтобы максимизировать прибыль. Задайте стоимость неприсвоения как нуль, поскольку компания не делает денег из незаполненных такси или запросов поездки.

costUnmatched = 0;
[M,uR,uC] = matchpairs(P,costUnmatched,'max')
M = 3×2

     1     1
     2     2
     3     4

uR =

  0x1 empty double column vector
uC = 2×1

     3
     5

matchpairs вычисляет самые прибыльные поездки, чтобы заполнить. Листовая поездка решения запрашивает 3 и 5 незаполненных.

Ride 1Ride 2Ride 3Ride 4Ride 5Cab A$5.70$6.30$3.10$4.80$3.50Cab B$5.80$6.40$3.30$4.70$3.20Cab C$5.70$6.30$3.20$4.90$3.40

Вычислите общую прибыль для расчетного решения. Начиная с costUnmatched нуль, только необходимо добавить вместе прибыль от каждого соответствия.

TotalProfits = sum(P(sub2ind(size(P), M(:,1), M(:,2))))
TotalProfits = 17

Используйте matchpairs отслеживать перемещение нескольких точек путем минимизации общего количества изменяется в расстоянии.

Постройте сетку точек во время t=0 в зеленом. Во время t=1, некоторые точки перемещают небольшое количество в случайное направление.

[x,y] = meshgrid(4:6:16);
x0 = x(:)';
y0 = y(:)';
plot(x0,y0,'g*')
hold on
rng default % for reproducibility
x1 = x0 + randn(size(x0));
y1 = y0 + randn(size(y0));
plot(x1,y1,'r*')

Figure contains an axes object. The axes object contains 2 objects of type line.

Используйте matchpairs совпадать с точками в t=0 с точками в t=1. Для этого сначала вычислите матрицу стоимости где C(i,j) Евклидово расстояние от точки i указать j.

C = zeros(size(x).^2);
for k = 1:length(y1)
  C(k,:) = vecnorm([x1(k)-x0; y1(k)-y0],2,1)';
end
C
C = 9×9

    2.8211    3.2750    9.2462    6.1243    6.3461   10.7257   11.7922   11.9089   14.7169
    4.9987    2.2771    7.5752    6.2434    4.3794    8.4485   11.1792   10.2553   12.5447
   15.2037    9.3130    3.7833   17.1539   12.2408    8.7988   20.7211   16.8803   14.5783
    6.9004    8.6551   13.1987    1.1267    5.3446   11.3075    5.1888    7.3633   12.3901
    8.6703    6.3191    8.7571    5.9455    0.3249    6.0714    8.2173    5.6816    8.3089
   13.5530    8.1918    4.7464   12.7818    6.8409    1.4903   14.6652    9.9242    7.3426
   11.5682   13.1257   16.8150    5.5702    8.3359   13.4144    0.4796    6.2201   12.2127
   13.6699   12.3432   13.7784    8.6461    6.3438    8.8167    5.8858    0.3644    6.1337
   20.6072   17.2853   15.6495   16.5444   12.1590    9.6935   13.9562    8.3006    3.8761

Затем используйте matchpairs совпадать со строками и столбцами в матрице стоимости. Задайте стоимость неприсвоения как 1. С такой низкой стоимостью неприсвоения относительно записей в матрице стоимости это - вероятный matchpairs оставит некоторые точки несопоставленными.

M = matchpairs(C,1)
M = 5×2

     4     4
     5     5
     6     6
     7     7
     8     8

Значения M(:,2) соответствуйте исходным точкам (x0,y0), в то время как значения M(:,1) соответствуйте перемещенным точкам (x1,y1).

Постройте совпадающие пары точек. Точки, которые переместились дальше, чем 2*costUnmatched далеко от исходной точки остаются несопоставленными.

xc = [x0(M(:,2)); x1(M(:,1))];
yc = [y0(M(:,2)); y1(M(:,1))];
plot(xc,yc,'-o')

Figure contains an axes object. The axes object contains 7 objects of type line.

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

свернуть все

Стойте матрицы. Каждая запись Cost(i,j) задает стоимость присвоения строки i к столбцу j.

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

Стоимость не соответствия в виде скаляра. matchpairs сравнивает значение 2*costUnmatched к записям в Cost определить, более ли выгодно это для строки или столбца, чтобы остаться несопоставленным. Используйте этот параметр, чтобы сделать соответствия, более или менее вероятно, в алгоритме. Для получения дополнительной информации смотрите линейную проблему присвоения.

Пример: M = matchpairs(C,10) задает стоимость 10 для того, чтобы не совпадать со строкой или столбцом C.

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

Цель оптимизации в виде любого 'min' или 'max'. Цель оптимизации задает, должна ли общая стоимость быть минимизирована или максимизирована.

Пример: M = matchpairs(Cost,costUnmatched,'max') указывает что строки и столбцы Cost должен быть соответствующим вместе, чтобы максимизировать общую стоимость.

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

свернуть все

Соответствия, возвращенные как матрица. M p- 2 матрица, где M(i,1) и M(i,2) индексы строки и столбца совпадающей пары в матрице стоимости. Строки M сортируются со вторым столбцом в порядке возрастания.

  • Каждая строка и столбец может быть соответствующей одно время только, таким образом, каждый M(i,1) значение и каждый M(i,2) значение уникально.

  • M содержит p соответствия и p меньше чем или равно максимальному количеству соответствий min(size(Cost)).

  • Стоимость соответствий в M sum([Cost(M(1,1),M(1,2)), Cost(M(2,1),M(2,2)), ..., Cost(M(p,1),M(p,2))]).

Неприсвоенные строки, возвращенные как вектор-столбец индексов. Записи в uR укажите который строки в Cost являются неприсвоенными. Каждая запись в uR и uC способствует общей стоимости решения согласно costUnassigned.

Неприсвоенные столбцы, возвращенные как вектор-столбец индексов. Записи в uC укажите который столбцы в Cost являются неприсвоенными. Каждая запись в uR и uC способствует общей стоимости решения согласно costUnassigned.

Больше о

свернуть все

Линейная проблема присвоения

Линейной проблемой присвоения является способ присвоить строки столбцам, таким образом, что каждая строка присвоена столбцу, и общая стоимость присвоений минимизирована (или максимизирована). Стоимость присвоения каждой строки к каждому столбцу получена в матрице стоимости. Запись Cost(i,j) стоимость присвоения строки i к столбцу j.

Стоимость неприсвоения присваивает стоимость для любой строки или столбца, который не является соответствующим. Эта практика допускает минимальные экономичные решения, которые не присваивают все строки или столбцы. Если строка и столбец не является соответствующей, это увеличивает общую стоимость на 2*costUnmatched.

Общая стоимость решения M сумма стоимости всех совпадающих пар, добавленных к стоимости всех несопоставленных пар:

TC=i=1pCost(M(i,1),M(i,2))+costUnmatched(m+n2p)

В коде общая стоимость

CostAssigned = sum(Cost(sub2ind(size(Cost), M(:,1), M(:,2))));
CostUnassigned = costUnmatched*(sum(size(Cost))-2*size(M,1));
TotalCost = CostAssigned + CostUnassigned;

  • Cost m- n матрица.

  • M p- 2 матрица, где M(i,1) и M(i,2) строка и столбец совпадающей пары.

  • (m+n-2*p) общее количество несопоставленных строк и столбцов.

Ссылки

[1] Подновите, И.С. и Дж. Костер. "На Алгоритмах Для Перестановки Больших Записей в Диагональ Разреженной матрицы". SIAM J. Анальная матрица. & Прикладной 22 (4), 2001. стр 973–996.

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

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

| |

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