Задача на собеседовании в Дойч Банк

saika

Дана положительно определенная симметричная матрица $||a_{ij}||$ размера $1000х1000$. Пусть $L$ - набор $100$ различных числе из набора $\{1, 2, ... , 999, 1000\}$. Найти минимум по всем наборам $L$ Суммы $\Sigma_{i \in L, j \in L}a_{ij} \rightarrow min_{L}$.
Ответ в видне перебора $C_{1000}^{100}$ вариантов не устраивает.

Verochka

$\Sigma_{i \in L, j \in L}a_{ij} \rightarrow min_{L}$
Можно вот это вот поподробнее расписать?

myznkaht

[math]  Дана положительно определенная симметричная матрица $||a_{ij}||$ размера $1000х1000$. Пусть $L$ -   набор $100$ различных числе из набора $\{1, 2, ... , 999, 1000\}$. Найти минимум по всем наборам $L$   Суммы $\Sigma_{i \in L, j \in L}a_{ij} \rightarrow min_{L}$.  Ответ в видне перебора $C_{1000}^{100}$ вариантов не устраивает.  [/math]

1853515

нужно придумать алгоритм решения за меньшее время или найти ответ?

svetik5623190

Дана положительно определенная симметричная матрица $||a_{ij}||$ размера $1000х1000$. Пусть $L$ - набор $100$ различных числе из набора $\{1, 2, ... , 999, 1000\}$. Найти минимум по всем наборам $L$ Суммы $\Sigma_{i \in L, j \in L}a_{ij} \rightarrow min_{L}$.
Ответ в видне перебора $C_{1000}^{100}$ вариантов не устраивает.
Попробуем провести хотя бы оценки, если найти минимум пока не получается явно. Матрица положительно определённая - значит все с.ч. положительны. Методом Гаусса за ~1000^3 операций находим собственные числа, упорядочиваем пузырьком, отсюда получаем операторную норму матрицы. Поскольку все нормы в конечномерных пространствах эквивалентны, то норму "максимум суммы элементов по строке" можно оценить через операторную (точные константы см. К.Ю.Богачёв "Что-то там про методы вычислений на ЭВМ" а через строковую норму можно сверху оценить нашу сумму. Оценка конечно получится очень плохая :( Ещё одну плохую оценку сверху можно получить, взяв минимум не по всем возможным наборам, а по какому-то небольшому числу наборов.
Зато хорошую оценку снизу получить легко. В нашей матрице всего-то 1000 000 элементов, упорядочив их по возрастанию пузырьком, найдём сто наименьших, сложим их - это оценка снизу на минимум.
(Апдейт: Ступил, не сто а 100^2 надо искать. Учитывая мой следующий пост, можно искать ещё меньше , что будет быстрее)
Теперь попробуем найти сам минимум. Кажется я почти придумал как, сейчас напишу.

svetik5623190

В силу симметричности матрицы и минимизируемой суммы, минимизируемая сумма на самом деле равна сумме двух сумм:
[math]$ \sum\limits_{j\in L, k\in L}a_{kj}=2\sum\limits_{j\in L, k\in L, k<j}a_{kj} \quad + \quad \sum\limits_{k\in L} a_{kk}$[/math]
Упорядочиваем пузырьком (500 000 - 1000) наших элементов матрицы в верхнем треугольнике по возрастанию, то же самое делаем с 1000 элементами на диагонали.
Теперь нужно выбрать грамотно индексы чтобы сумма сумм была минимальна.

svetik5623190

Принудительно поделим элементы вне главной диагонали на 2, получим новую матрицу A1. Задача свелась к тому, чтобы найти такое L из 100 элементов, что сумма 5050 чисел [math]$\sum\limits_{k,j\in L, k\leq j}a1_{kj}  $[/math] минимальна.
Пока хз что делать дальше..... Видимо какой-то алгоритм индуктивного построения множества L нужен, по результатам сортировки пузырьком подмножества (верхний треугольник + диагональ) матрицы А1, хотя хз.
Извините, ребята, больше времени думать над этой задачей у меня нет.
Но задача интересная :)
Надеюсь мои мысли помогут кому-нибудь её решить.

olegikristina

Забавная задача, а что за позиция?

lena1978

пока смог найти только верхнюю и нижнюю оценки :crazy:

narkom

может все-таки метод нахождения нужно найти? :confused:

lena1978

ну короче, если посмотреть на выражение для суммы, котрое написал гонобобель, видно, что это значение квадратичной формы A на некотором 1000-мерном векторе, у которого 100 координат - единицы, остальные 900 - нули. т.е. задача состоит в том, чтобы найти вектор x из такого множества векторов X (у котрорых 100 каких-то координат 1, а остальные 0 на котором значение формы A минимально.

так как A положительно определена, то поверхностями уровня будут гомотетичные эллипсоиды с центром в начале координат. дальше заметим, что множество X располагается на 999-мерной сфере с центром в нуле и радиусом корень квадратный из 100. минимум значения формы на этой сфере будет нижней оценкой для минимума на множестве X.
понятно, что если раздувать эллипсоид из начала координат, то он первым делом упрется в нашу сферу своей самой большой осью (отрезком оси). т.е. минимизирующим вектором m на сфере будет приведенный к длине корень из 100 вектор большой оси. он находится как собственный вектор, соответсвующий максимальному (или минимальному, не помню :) ) собственному значению матрицы A.
дальше вроде как хочется находить искомый вектор x\in X в некоторой окрестности вектора m. можно поискать его как вектор, такой что обычное скалярное произведение (x, m) максимально. такой вектор тоже найти просто, достаточно найти 100 самых больших координат вектора m, тогда x иметь по этим координатам единицы. (ну тут на самом деле надо сделать то же самое для
-m, и выбрать из двух векторов, вдруг мы не за тот конец оси схватились).
но вот только найденый таким образом вектор x может не давать минимума. точки, лежащие на большем расстоянии от конца m, могут лежать на меньшем эллипсоиде, нежели тот, на котором лежит конец x.
т.е. вроде как значение формы на x - не минимум, но его верхняя оценка.
 
дальше надо как-то крутиться. будем раздувать эллипсоид от момента, когда он уперся в нашу сферу до того момента, как он начнет задевать за 998-мерную сферу, задаваемую уравнениями (y, y) = 100,
(m, y) = (m, x). вот это будет уточнением нижней оценки на минимум. если проецировать всё вдоль вектора m, эллипсоид станет 998-мерным и видно, что заденет он эту сферу опять же отрезком самой большой оси, которой уже будет вторая по величине главная ось формы A.
вобщем как-то хочется из таких соображений и наблюдения, что вектора из X находятся на расстоянии друг от друга не менее корня из 2, посторить цепочку к решению.

rjhgec

они что ищут генея?
я тут тоже в одну конторку ходил дали задачу на 10 минут (вытащить соответствие метаданным 8.0 таблиц скуля) - так ее вообще никто не смог сделать из моих знакомых :grin:

svetik5623190

Принудительно поделим элементы вне главной диагонали на 2, получим новую матрицу A1. Задача свелась к тому, чтобы найти такое L из 100 элементов, что сумма 5050 чисел [math]$\sum\limits_{k,j\in L, k\leq j}a1_{kj}  $[/math] минимальна.
Пока хз что делать дальше..... Видимо какой-то алгоритм индуктивного построения множества L нужен, по результатам сортировки пузырьком подмножества (верхний треугольник + диагональ) матрицы А1, хотя хз.
А что если так вот делать?
В множестве (треугольник + диагональ) выберем 5050 наименьших чисел. проверяем: можно ли индексы элементов этого множества записать в нужном нам виде?
если да - задача решена.
Если нет - добавим ещё один, следующий по возрастанию, элемент, и проверим для всех 5050-элементных подмножеств получившегося 5051-элементного множества, можно ли индексы хоть одного из них записать в нужном виде. Если да - задача решена. Если нет - добавим следующий по возрастанию элемент, и проверим для всех 5050-элементных подмножеств полученного 5052-элементного множества.....
Этот алгоритм хорош тем, что доказательство минимальности суммы, если она будет найдена, в него уже включено.
Как проверить, что набор из 5050 пар натуральных чисел {(j,k)} удовлетворяют нужному условию?
Например отсеивать плохие, чтобы остались только хорошие: если различных индексов j не столько же, сколько различных индексов k - набор сразу идёт в топку. Если различных индексов хоть одного типа не 100 - набор в топку. Если разных индексов каждого типа равное 100, но сами наборы индексов разные - тоже в топку. Пусть теперь различных индексом j и k по 100 штук, и наборы индексов k и j однинаковые, обозначим эти совпадающие наборs индесов одной буквой L. Вместе с парой (j,k) в наше множество из 5050 элементов должны входить так же все попадающие в (вержний треугольник + диагональ) пары (s, k) и (j,s) где s из L. Если и этот последний тест пройден, то множество из 5050 пар индексов допустимое, и даже построено множество L.
PS: я нигде не ошибся?.. А то уже спать хочу..... :)

vc_orlov

А зачем сферу брать если можно плоскость х1+...+xn=100,причем ту ее часть ,где все х положительны.Потом методом Ла-Гранжа :) найти минимум, там линейная система будет и потом в окрестности искать нужное решение.Окрестность искать можно минимизируя
|x0-x| на множестве нашей гиперплоскости опять же методом Ла-Гранжа,окрестности непересекаются, так что минимальная , наверное и будет решением.

lena1978

я тут всадил "клюковки" и подумал, что лучше перейти в базис из собственных векторов, там форма A будет задаваться единичной матрицей. потом считаем вектора исходного базиса в новом (долго, правда, придется это все считать :grin: ). эти вектора останутся ортогональными, правда ведь?
у нас искомый вектор был разложен по старому базису (сумма из ста какиех-то базисных векторов). значение формы на нем - это ведь скалярное произведение самого на себя, т.е. [math]$ A(x) = ( \Sigma_{i \in L} e_i, \Sigma_{i \in L} e_i) = \Sigma_{i \in L}(e_i, e_i)$[/math] (попарные произведения векторов уничтожились ввиду их ортогональности). Чтобы такая сумма была минимальной, надо взять вектра e_i с минимальным модулем (в новых координатах).
что-то как-то просто получилось, но если задача действительно для собеседования, то неудивительно.

зы. внатуре какая-то неделя линала :)

toxin

Это решение не правильное! В базисе из собственных векторов A будет диагональной, а не единичной. А если вы сделаете ее единичной, то ортогональность исходных векторов потеряется! Мне кажется, эта задача не имеет точного полиномиального алгоритма.

lena1978

точно, так и думал, что что-то не так. пойду убъюсь :crazy:
Оставить комментарий
Имя или ник:
Комментарий: