Как доказать np-hardность задачи оптимального расписания?

[urankhai]

Задача формулируется таким образом:

Есть множество устройств $\{d_1, d_2, ..d_n\}$, которые должны передать свою информацию (i) контроллеру. Для этого выделено $T$ слотов времени, в каждый из которых передать свою информацию может лишь одно устройство. В каждый слот времени мы сами выбираем, какую комбинацию i (т.е. от каких устройств) мы передаем. Если два и более устройства одновременно пытаются передать информацию в одном слоте, то информация считается потерянной. Если устройство передало свою информацию, то больше оно не активно, даже если в следующих слотах в расписании оно значится. Например, мы передаем в данном слоте $\{d_1, d_2\}$. Если $d_1$ уже передало свою i, то $d_2$ может передать свою. И наоборот, если $d_2$ уже передало свою i, то $d_1$ может передать свою. Если же в предыдущие слоты ни одно из устройств не передало свою информацию, то они могут пытаться передать одновременно и в этом случае вся информация от них теряется. Все вероятности перехода известны и не зависят от времени.
Нужно найти расписание (последовательность активных устройств в каждом слоте), чтобы после всех $T$ слотов вероятность передачи информации со всех устройств $P(\{d_1,d_2,..d_n\})$ была бы максимальной
Задача решается перебором, но при больших размерностях очень долго. Предполагаю, что задача np-hard, но не знаю, как доказать.
Задачу можно свести к последовательности умножения матриц. Пусть $P_k$ – это столбец вероятностей передачи информации после выполнения k слотов:
$P_{k+1}=P$(передали $\emptyset$, передали только $d_1$, передали только $d_2$, передали только $d_1,d_2$,…, передали $d_1,d_2..d_n$), $P_0=(1,0,..,0)$
Тогда $P_T=A_T\cdot A_{T-1} \cdot\ldots\cdot A_1\cdot P_0$
Где матрица $A_j$ может принимать любое значение из множества размерности $2^{n-1}$. Это множество - есть множество матриц вероятностей перехода для любого возможного действия – расписания в данном слоте. Все эти матрицы - нижнетреугольные стохастические (сумма элементов любого столбца равна 1).
Нужно найти определить такую последовательность матриц, при перемножения которых, мы получим наибольшее значение в левом нижнем углу.
Есть ли у кого-нибудь идеи,
1) как доказать, что задача np hard
2) придумать какой-нибудь критерий выбора субоптимальной последовательности, которая даст решение близкое к оптимальному, но вычислительно не так затратно.

[пианист]

Почему нельзя просто: в каждый слот передает одно устройство?

urankhai в сообщении #1154464 писал(а):

Все вероятности перехода известны и не зависят от времени

О каких переходах речь?

[svv]

Действительно.
Естественно, нам известно, какие устройства уже передали информацию до наступления $k$-го слота, так как мы сами управляли передачей. Поэтому, назначая для следующей передачи несколько устройств сразу, мы либо включаем в список заведомо неактивные (зачем?), либо намеренно сталкиваем активные устройства лбами (зачем?), либо и то и другое.

Пожалуйста, следите за тем, чтобы формулы, даже самые простые, окружались двумя знаками доллара, а НЕ тэгом math (его система добавит сама). Тогда такого разнобоя d_1,d_2 не будет, а будет всегда красиво: $d_1,d_2$. Код: $d_1,d_2$.

[urankhai]

Извиняюсь за непонятное объяснение.
Для каждого уcтройства $d_1, d_2, \ldots, d_n$ известны вероятности несрабатывания $p_1, p_2, \ldots, p_n$, они независимы. Поэтому нам известно только с некоторой вероятностью, передало ли к этому моменту свою информацию устройство или нет.
Например, при расписании из 3 слотов $\{d_1, d_2, d_1d_2\}$, к концу второго слота вероятность, что мы получили информацию и от $d_1$, и от $d_2$ равна $(1-p_1)(1-p_2)$. После третьего слота эта вероятность возрастает до $(1-p_1)(1-p_2)(1+p_1+p_2)$.
Матрицы $A_i$ выражаются как раз через $p_1, p_2, \ldots, p_n$.

[пианист]

urankhai
На первый взгляд, в Вашей постановке нечего оптимизировать.
Т.к. вероятности отказов независимы и постоянны, не все ли равно, в каком порядке - результат (в среднем) д.б. одинаковым.
Главное, не пропускать слоты.

[urankhai]

Допустим у нас 3 слота и 2 устройста $d_1,d_2$ с вероятностями непередачи $p_1,p_2$. При расписании $\{d_1,d_2,d_1\}$ интересующая нас вероятность $(1-p_1^2)(1-p_2)$, при расписании $\{d_1,d_2,d_2\}$ интересующая нас вероятность $(1-p_1)(1-p_2^2)$. При расписании $\{d_1,d_2,d_1d_2\}$ интересующая нас вероятность $(1-p_1)(1-p_2)(1+p_1+p_2)$, что больше двух предыдущих.
Если в каждом слоте запускать лишь одно какое-либо устройство, то да - порядок не имеет значения. Слоты в расписании можно переставить местами и ничего не изменится. Но как только в расписании в одном слоте ставим 2,3 и так далее вплоть до $n$ устройств, порядок имеет значения.

-- Пн сен 26, 2016 11:32:13 --

Если забыть про эти несчастные устройства и оставить только матрицы:

Дано $Q_T=A_T\cdot A_{T-1} \cdot\ldots\cdot A_1$, где $T$ - фиксировано и известно;
матрица $A_j, j=1,\ldots, T$ может принимать любое значение из множества размерности $2^{n-1}$: $\{B_1,\ldots,B_{2^{n-1}}\}$. Это множество - есть множество нижнетреугольных стохастических (сумма элементов любого столбца равна 1) матриц.
Нужно найти определить такую последовательность матриц, при перемножения которых, мы получим наибольшее значение в левом нижнем углу в итоговой матрице $Q_T$.
Возможно ли решить эту задачу кроме как перебором и какими подходами? Можно ли что-то сказать про сложность задачи?

[пианист]

urankhai
Прошу прощения, не совсем Вас понял: вопрос, формулируемый в терминах устройств, Вы снимаете, имея в виду обсуждение только задачи с матрицами?

[urankhai]

Это одна и таже задача, просто в разной формулировке. Я буду рад любым идеям и комментариям в первой или второй постановке.

[пианист]

Такие и похожие задачи изучаются в рамках теории массового обслуживания.
Посмотрите в эту сторону.

[Sender]

urankhai, становится ли устройство неактивным после неудачной попытки передачи?

[urankhai]

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

[пианист]

Я лично читал (в основном с целью само-образования)
https://books.google.ru/books/about/%D0 ... edir_esc=y
Но это исключительно потому, что у меня это книжко валялось, никаких оснований рекомендовать более других пособий по предмету у меня нет.