Задача о минимуме/максимуме скалярного произведения — различия между версиями
(→Литература) |
Haposiwe (обсуждение | вклад) (Изменения в "см. также") |
||
| (не показаны 4 промежуточные версии 3 участников) | |||
| Строка 4: | Строка 4: | ||
}} | }} | ||
== Решение == | == Решение == | ||
| − | Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + | + | Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m</tex> |
{{ | {{ | ||
Теорема | Теорема | ||
| − | |about=о минимуме/максимуме скалярного произведениях<ref | + | |about=о минимуме/максимуме скалярного произведениях<ref name = "wiki" /> |
| − | |statement=Минимум скалярного произведения достигается при сопоставлении | + | |statement=Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности <tex>x_1 \ldots x_m</tex> и убывающей последовательности <tex>y_1 \ldots y_m</tex>. При сопоставлении возрастающей <tex>y_1 \ldots y_m</tex> достигается максимум. |
|proof= | |proof= | ||
| − | Будем считать, что <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность. | + | Будем считать, что последовательность <tex>x_i</tex> отсортирована по возрастанию. Покажем, что если существуют пары чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, такие что <tex>x_i < x_j</tex> и <tex>y_i < y_j</tex>, то скалярное произведение можно уменьшить, поменяв местами <tex>y_i</tex> и <tex>y_j</tex>. Так как в нашем случае <tex>(x_j - x_i)(y_j - y_i) > 0</tex>, то <tex>x_i y_i + x_j y_j > x_j y_i + x_i y_j</tex>, а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех <tex>y_i < y_j</tex> получим отсортированную по убыванию последовательность <tex>y_i</tex>, и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел <tex>(x_i, y_i)</tex> и <tex>(x_j, y_j)</tex>, таких что <tex>x_i < x_j</tex> и <tex>y_i > y_j</tex> нужно менять местами <tex>y_i</tex> и <tex>y_j</tex>. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным. |
}} | }} | ||
Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов]] и [[Flow shop| расписаний]]. | Данная теорема нашла себе практическое применение в теории [[Теорема Радо-Эдмондса (жадный алгоритм)|матроидов]] и [[Flow shop| расписаний]]. | ||
| − | == | + | == Примечания == |
| − | <references/> | + | <references> |
| + | <ref name = "wiki">[https://ru.wikipedia.org/wiki/Перестановочное_неравенство Википедия {{---}} Перестановочное неравенство]</ref> | ||
| + | </references> | ||
| + | |||
| + | ==См. также== | ||
| + | * [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]] | ||
| + | * [[Теорема Кэли]] | ||
| + | * [[Матричное представление перестановок]] | ||
== Источники информации == | == Источники информации == | ||
Текущая версия на 18:07, 24 декабря 2017
| Задача: |
| Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел. |
Содержание
Решение
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число
| Теорема (о минимуме/максимуме скалярного произведениях[1]): |
Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности и убывающей последовательности . При сопоставлении возрастающей достигается максимум. |
| Доказательство: |
| Будем считать, что последовательность отсортирована по возрастанию. Покажем, что если существуют пары чисел и , такие что и , то скалярное произведение можно уменьшить, поменяв местами и . Так как в нашем случае , то , а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех получим отсортированную по убыванию последовательность , и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел и , таких что и нужно менять местами и . В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным. |
Данная теорема нашла себе практическое применение в теории матроидов и расписаний.
Примечания
См. также
- Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
- Теорема Кэли
- Матричное представление перестановок
Источники информации
- Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.
