Задача о минимуме/максимуме скалярного произведения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Изменения в "см. также")
 
(не показано 9 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
{{  
 
{{  
 
Задача  
 
Задача  
|definition=задача о нахождении минимальной/максимальной суммы попарных произведений для двух заданных упорядоченных наборов чисел.  
+
|definition=Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.  
 
}}  
 
}}  
 
== Решение ==  
 
== Решение ==  
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + ... + x_m y_m</tex>  
+
Скалярным произведением двух упорядоченных последовательностей чисел будем называть число <tex>S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m</tex>  
 
{{  
 
{{  
 
Теорема  
 
Теорема  
|about=о минимуме/максимуме скалярного произведениях<ref>[http://ru.wikipedia.org/wiki/Перестановочное_неравенс.. Транс-неравенство или перестановочное неравенство]</ref>  
+
|about=о минимуме/максимуме скалярного произведениях<ref name = "wiki" />  
|statement=Минимум скалярного произведения достигается при сопоставлении возрастащей последовательности <tex>x_1..x_m</tex> и убывающей последовательности <tex>y_1..y_m</tex>. При сопоставлении возрастающей <tex>y_1..y_m</tex> достигается максимум.  
+
|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| расписаний]].
 +
 
 +
== Примечания ==
 +
<references>
 +
<ref name = "wiki">[https://ru.wikipedia.org/wiki/Перестановочное_неравенство Википедия {{---}} Перестановочное неравенство]</ref>
 +
</references>
  
== Примечание ==  
+
==См. также==
<references/>
+
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 +
* [[Теорема Кэли]]
 +
* [[Матричное представление перестановок]]
  
== Литература ==  
+
== Источники информации ==  
 
* Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.  
 
* Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.  
  
Строка 23: Строка 32:
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]
 +
 +
[[Категория: Свойства комбинаторных объектов]]

Текущая версия на 18:07, 24 декабря 2017

Задача:
Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.

Решение

Скалярным произведением двух упорядоченных последовательностей чисел будем называть число [math]S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m[/math]

Теорема (о минимуме/максимуме скалярного произведениях[1]):
Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности [math]x_1 \ldots x_m[/math] и убывающей последовательности [math]y_1 \ldots y_m[/math]. При сопоставлении возрастающей [math]y_1 \ldots y_m[/math] достигается максимум.
Доказательство:
[math]\triangleright[/math]
Будем считать, что последовательность [math]x_i[/math] отсортирована по возрастанию. Покажем, что если существуют пары чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math], такие что [math]x_i \lt x_j[/math] и [math]y_i \lt y_j[/math], то скалярное произведение можно уменьшить, поменяв местами [math]y_i[/math] и [math]y_j[/math]. Так как в нашем случае [math](x_j - x_i)(y_j - y_i) \gt 0[/math], то [math]x_i y_i + x_j y_j \gt x_j y_i + x_i y_j[/math], а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех [math]y_i \lt y_j[/math] получим отсортированную по убыванию последовательность [math]y_i[/math], и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math], таких что [math]x_i \lt x_j[/math] и [math]y_i \gt y_j[/math] нужно менять местами [math]y_i[/math] и [math]y_j[/math]. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.
[math]\triangleleft[/math]

Данная теорема нашла себе практическое применение в теории матроидов и расписаний.

Примечания

См. также

Источники информации

  • Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.