Поиск набора из 0 и 1 с наименьшим числом 1

[jhendrix]

Дается вектора $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$.

[Lia]

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

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

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

[Lia]

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

[Null]

На самом деле ваша задача похожа на задачу Режем торт. Там тоже нужно минимизировать количество ненулевых элементов, только уже в положительных действительных числах. Ни чего похожего нагуглить не смог

[Sonic86]

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

[Null]

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

(Оффтоп)

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

[jhendrix]

У меня есть некоторые соображения как можно это решить, но только с помощью алгоритмических рекурентных формул. Мне кажется данные расуждения относятся больше к программированию нежели к серьезному применении высшей математики. Если это решение правильное то ее время выполнения линейное, а не экспоненциальное. Тесты придумать чтоб сломать этот алгоритм я не знаю, поэтому прошу вас поделится примерами ну или добавить/исправить ошибки.
Обозначим вектор $\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)$.

[Null]

Возьмите $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} $$

[jhendrix]

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

[Null]

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

(Оффтоп)

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

[Lia]

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

[maxal]

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) для решения этой задачи.

[jhendrix]

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

[maxal]

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