2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение01.12.2015, 22:34 


24/12/09
25
Дается вектора $a_1, a_2, ... a_p, b$, состоящие из наборов $0$ и $1$ длины $n$. Найти такие коэффициенты $\alpha_1,  \alpha_2, ...  \alpha_p$, чтоб полученный вектор $y  =   \alpha_1 a_1  +  \alpha_2 a_2  + ... +  \alpha_p a_p  + b$ содержал наименьшее число $1$. Все операции совершаются по модулю $2$.

 Профиль  
                  
 
 Posted automatically
Сообщение02.12.2015, 00:30 


20/03/14
12041
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- неинформативный заголовок;
- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы. Не разбивайте формулы на мелкие фрагменты. Каждая формула должна быть полностью заключена в одну пару долларов и не содержать их в середине.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение02.12.2015, 06:55 


20/03/14
12041
 i  Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение02.12.2015, 08:21 
Заслуженный участник


12/08/10
1608
На самом деле ваша задача похожа на задачу Режем торт. Там тоже нужно минимизировать количество ненулевых элементов, только уже в положительных действительных числах. Ни чего похожего нагуглить не смог :-(

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение02.12.2015, 08:32 
Заслуженный участник


08/04/08
8556
Че-то, по-моему, обычная линейная алгебра:
1) Сначала надо рассмотреть случай $n=p$ и $\det (a_j)$ невырожденный. В таком случае для любого $b$ удается подобрать соответствующее значение линейной комбинации так, что сумма обнуляется.
2) Если $p>n$, то очевидно сводится к 1)
3) Если $r=\operatorname{rk} (a_j)<n$, то ясно, что ничего больше пространства размерности $r$ породить мы не сможем, значит зануляем линейно зависимые вектора, а потом убиваем максимум $r$ единиц в $b$, если только вся колонка коэффициентов не нулевая.
Все.
Я ошибаюсь?
Если нет, то теме место в ПРР, ИМХО.

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение02.12.2015, 08:40 
Заслуженный участник


12/08/10
1608
Вы ошибаетесь. Рассмотрите вектора $b=(1,1,1,1);a_1=(0,1,1,1)$ Ранг 1 а занулить можем три $1$.

(Оффтоп)

Олимпиадные задачи? ТС Располагает решением?

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение03.12.2015, 05:33 


24/12/09
25
У меня есть некоторые соображения как можно это решить, но только с помощью алгоритмических рекурентных формул. Мне кажется данные расуждения относятся больше к программированию нежели к серьезному применении высшей математики. Если это решение правильное то ее время выполнения линейное, а не экспоненциальное. Тесты придумать чтоб сломать этот алгоритм я не знаю, поэтому прошу вас поделится примерами ну или добавить/исправить ошибки.
Обозначим вектор $\vec F_+\left(p\right)$ - оптимальное решение, рассматривая вектора на отрезке $\left[1, p\right]$, включая $p$-й. Аналогично $\vec F_-(p)$ - оптимальное решение, рассматривая вектора на отрезке $\left[1, p\right)$, не включая $p$-й. Тогда
$$
\begin{cases}
\vec F_+\left(p\right) = \min\left(a_p + \vec F_+\left(p - 1\right) , a_p + \vec F_-\left(p - 1\right) \right), \\         
\vec F_-\left(p\right) = \min\left(\vec F_+\left(p - 1\right) , \vec F_-\left(p - 1\right) \right), \\      
\vec F_+\left(1\right) = a_1 + b, \\      
\vec F_-\left(1\right) = b.
\end{cases}
$$
где минимум берется по количеству 1 у векторов. Здесь применяется комбинация жадного алгоритма с динамикой. Ответ будет $\min\left(\vec F_+\left(p\right), \vec F_-\left(p\right)\right)$. Сложность примерно $O\left(n \cdot p\right)$.

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение05.12.2015, 12:33 
Заслуженный участник


12/08/10
1608
Возьмите $b=(1,1,1,1),a_1=(0,0,1,1),a_2=(0,1,1,1),a_3=(1,1,1,1)$.
$F_+(1)=(1,1,0,0),F_-(1)=(1,1,1,1),\\F_+(2)=(1,0,0,0),F_-(2)=(1,1,0,0),\\F_+(3) = (0,0,1,1),F_-(3)=(1,0,0,0)$,
а правильный ответ $(0,0,0,0)$.
Можно построить контрпример даже для

$$ \begin{cases} \vec F_+\left(p\right) = \min_{k<p}{}\left(a_p + \vec F_+\left(k - 1\right) , a_p + \vec F_-\left(k - 1\right) \right), \\ \vec F_-\left(p\right) = \min_{k<p}\left(\vec F_+\left(k - 1\right) , \vec F_-\left(k - 1\right) \right), \\ \vec F_+\left(1\right) = a_1 + b, \\ \vec F_-\left(1\right) = b. \end{cases} $$

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение06.12.2015, 10:18 


24/12/09
25
Null, можно сделать еще лучше! Надеюсь, что это будет последним этапом решения. Использовать ваш вариант + после нахождения $i$-ого оптимального варианта сортировать последующие $a_{i+1}, a_{i+2}, \ldots a_{p}$ вектора с текущим найденным. Получается мы разобрали два подотрезка, а вместе и весь.

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение06.12.2015, 11:40 
Заслуженный участник


12/08/10
1608
Напишите алгоритм подробно, тогда его можно будет проверять.

(Оффтоп)

Судя по всему это уже программирование

 Профиль  
                  
 
 Posted automatically
Сообщение06.12.2015, 12:50 


20/03/14
12041
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Computer Science»

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение18.12.2015, 07:13 
Модератор
Аватара пользователя


11/01/06
5660
jhendrix в сообщении #1078706 писал(а):
Дается вектора $a_1, a_2, ... a_p, b$, состоящие из наборов $0$ и $1$ длины $n$. Найти такие коэффициенты $\alpha_1,  \alpha_2, ...  \alpha_p$, чтоб полученный вектор $y  =   \alpha_1 a_1  +  \alpha_2 a_2  + ... +  \alpha_p a_p  + b$ содержал наименьшее число $1$. Все операции совершаются по модулю $2$.

Рассмотрите решётку $L=\langle a_1, a_2, \dots, a_p, 2e_1, 2e_2, \dots, 2e_n\rangle$, где $e_i$ -- единичный вектор с 1 в $i$-й компоненте. Тогда ваша задача сводится к нахождению closest vector problem (CVP) к $b$ в $L$. Есть эффективные приближенные алгоритмы (например, на основе LLL) для решения этой задачи.

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение18.12.2015, 22:11 


24/12/09
25
maxal, получается эту задачу не реально решить с помощью точных алгоритмов без перебора ? Стоит ли искать лучший переход к др задаче или то что вы привели это означает их уже не сущ. ?

 Профиль  
                  
 
 Re: Поиск набора из 0 и 1 с наименьшим числом 1
Сообщение19.12.2015, 08:57 
Модератор
Аватара пользователя


11/01/06
5660
jhendrix, зачастую LLL находит точное решение, но гарантии нет. Точные алгоритмы здесь скорее всего практически неприменимы для больших $n,p$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group