Решите линейную задачу присвоения
решает линейную задачу присвоения для строк и столбцов матричного M
= matchpairs(Cost
,costUnmatched
)Cost
. Каждая строка присвоена столбцу таким способом, которым минимизирована общая стоимость. costUnmatched
задает стоимость на строку не присвоения каждой строки, и также стоимости для каждого столбца не ссорения присвоенного к каждому столбцу.
[
дополнительно возвращает индексы для несопоставленных строк в M
,uR
,uC
] = matchpairs(Cost
,costUnmatched
)uR
и индексы для несопоставленных столбцов в uC
.
[___] = matchpairs(
задает цель оптимизации с помощью любой из комбинаций выходного аргумента в предыдущих синтаксисах. Cost
,costUnmatched
,goal
)goal
может быть 'min'
или 'max'
произвести соответствия, которые или минимизируют или максимизируют общую стоимость.
Присвойте продавцов рейсам, таким образом, что общая стоимость транспортировки минимизирована.
Компания имеет четырех продавцов, которые должны переместиться в ключевые города по всей стране. Компания должна забронировать их рейсы и хочет потратить как можно меньше денег. Эти продавцы базируются в различных частях страны, таким образом, стоимость для них, чтобы полететь в каждый город варьируется.
Эта таблица показывает стоимость для каждого продавца, чтобы полететь в каждый ключевой город.
Каждый город представляет возможность продаж. Если город пропущен, то компания терпит неудачу на среднем усилении дохода 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
вычисляет наименее дорогой способ получить продавца в каждый город.
Совпадайте со строками к столбцам, когда у вас будет намного больше столбцов, чем строки в матрице стоимости.
Создайте 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
не являются соответствующими никаким строкам.
Присвойте такси до маршрутов, таким образом, что прибыль максимизируется.
Служба такси имеет несколько запросов поездки со всех концов города. Компания хочет диспетчеризировать свое ограниченное количество такси способом, которое делает большую часть денег.
Эта таблица показывает предполагаемый тариф такси для каждого из пяти запросов поездки. Только три из пяти запросов поездки могут быть заполнены.
Создайте матрицу прибыли, чтобы представлять прибыль каждой поездки на такси.
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 незаполненных.
Вычислите общую прибыль для расчетного решения. Начиная с costUnmatched
нуль, только необходимо добавить вместе прибыль от каждого соответствия.
TotalProfits = sum(P(sub2ind(size(P), M(:,1), M(:,2))))
TotalProfits = 17
Используйте matchpairs
отслеживать перемещение нескольких точек путем минимизации общего количества изменяется в расстоянии.
Постройте сетку точек во время в зеленом. Во время , некоторые точки перемещают небольшое количество в случайное направление.
[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*')
Используйте matchpairs
совпадать с точками в с точками в . Для этого сначала вычислите матрицу стоимости где 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)
соответствуйте исходным точкам , в то время как значения M(:,1)
соответствуйте перемещенным точкам .
Постройте совпадающие пары точек. Точки, которые переместились дальше, чем 2*costUnmatched
далеко от исходной точки остаются несопоставленными.
xc = [x0(M(:,2)); x1(M(:,1))];
yc = [y0(M(:,2)); y1(M(:,1))];
plot(xc,yc,'-o')
Cost
— Стойте матрицыСтойте матрицы. Каждая запись Cost(i,j)
задает стоимость присвоения строки i
к столбцу j
.
Типы данных: single
| double
costUnmatched
— Стоимость не соответствияСтоимость не соответствия, заданного как скаляр. matchpairs
сравнивает значение 2*costUnmatched
к записям в Cost
определить, более ли выгодно это для строки или столбца, чтобы остаться несопоставленным. Используйте этот параметр, чтобы сделать соответствия, более или менее вероятно, в алгоритме. Для получения дополнительной информации смотрите линейную проблему присвоения.
Пример: M = matchpairs(C,10)
задает стоимость 10 для того, чтобы не совпадать со строкой или столбцом C
.
Типы данных: single
| double
goal
— Цель оптимизации'min'
(значение по умолчанию) | 'max'
Цель оптимизации, заданная как любой 'min'
или 'max'
. Цель оптимизации задает, должна ли общая стоимость быть минимизирована или максимизирована.
Пример: M = matchpairs(Cost,costUnmatched,'max')
указывает что строки и столбцы Cost
должен быть соответствующим вместе, чтобы максимизировать общую стоимость.
M
— СоответствияСоответствия, возвращенные как матрица. 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
— Неприсвоенные строкиНеприсвоенные строки, возвращенные как вектор-столбец индексов. Записи в uR
укажите который строки в Cost
являются неприсвоенными. Каждая запись в uR
и uC
способствует общей стоимости решения согласно costUnassigned
.
uC
— Неприсвоенные столбцыНеприсвоенные столбцы, возвращенные как вектор-столбец индексов. Записи в uC
укажите который столбцы в Cost
являются неприсвоенными. Каждая запись в uR
и uC
способствует общей стоимости решения согласно costUnassigned
.
Линейной проблемой присвоения является способ присвоить строки столбцам, таким образом, что каждая строка присвоена столбцу, и общая стоимость присвоений минимизирована (или максимизирована). Стоимость присвоения каждой строки к каждому столбцу получена в матрице стоимости. Запись Cost(i,j)
стоимость присвоения строки i
к столбцу j
.
Стоимость неприсвоения присваивает стоимость для любой строки или столбца, который не является соответствующим. Эта практика допускает минимальные экономичные решения, которые не присваивают все строки или столбцы. Если строка и столбец не является соответствующей, это увеличивает общую стоимость на 2*costUnmatched
.
Общая стоимость решения M
сумма стоимости всех совпадающих пар, добавленных к стоимости всех несопоставленных пар:
В коде общая стоимость
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.
Указания и ограничения по применению:
Генерация кода не поддерживает входные параметры разреженной матрицы для этой функции.
dmperm
| equilibrate
| sprank
У вас есть модифицированная версия этого примера. Вы хотите открыть этот пример со своими редактированиями?
1. Если смысл перевода понятен, то лучше оставьте как есть и не придирайтесь к словам, синонимам и тому подобному. О вкусах не спорим.
2. Не дополняйте перевод комментариями “от себя”. В исправлении не должно появляться дополнительных смыслов и комментариев, отсутствующих в оригинале. Такие правки не получится интегрировать в алгоритме автоматического перевода.
3. Сохраняйте структуру оригинального текста - например, не разбивайте одно предложение на два.
4. Не имеет смысла однотипное исправление перевода какого-то термина во всех предложениях. Исправляйте только в одном месте. Когда Вашу правку одобрят, это исправление будет алгоритмически распространено и на другие части документации.
5. По иным вопросам, например если надо исправить заблокированное для перевода слово, обратитесь к редакторам через форму технической поддержки.