У меня есть запрос на оптимизацию затрат, который я не знаю, как, если есть литература. Это немного сложно объяснить, поэтому я заранее прошу прощения за длину вопроса.
Есть сервер, к которому я обращаюсь, который работает следующим образом:
- запрос сделан на записи (r1, ... rn) и поля (f1, ... fp)
- Вы можете запросить только декартово произведение (r1, ..., rp) x (f1, ... fp)
- Стоимость (время и деньги), связанная с таким запросом, является аффинной в размере запроса:
T((r1, ..., rn)x(f1, ..., fp) = a + b * n * p
Без потери общности (просто путем нормализации) мы можем предположить, что b=1 так что стоимость:
T((r1, ...,rn)x(f1,...fp)) = a + n * p
- Мне нужно только запросить подмножество пар
(r1, f(r1)), ... (rk, f(rk)), запрос от пользователей. Моя программа действует как посредник между пользователем и сервером (который является внешним). У меня много таких запросов (десятки тысяч в день).
Графически мы можем рассматривать ее как разреженную матрицу n x p, для которой я хочу покрыть ненулевые значения прямоугольной подматрицей:
r1 r2 r3 ... rp
------ ___
f1 |x x| |x|
f2 |x | ---
------
f3
.. ______
fn |x x|
------
Имея:
- количество подматриц, сохраняемых разумным из-за постоянных затрат
- все 'x' должны находиться в подматрице
- общая покрытая площадь не должна быть слишком большой из-за линейных затрат
Я назову g коэффициент разреженности моей задачи (количество необходимых пар на общее количество возможных пар, g = k / (n * p). Я знаю коэффициент a.
Есть несколько очевидных наблюдений:
- если a мало, лучшее решение - запросить каждую пару (запись, поле) независимо, а общая стоимость:
k * (a + 1) = g * n * p * (a + 1)
- если a большое, лучшим решением будет запрос всего декартова произведения, а общая стоимость:
a + n * p
- второе решение лучше, как только
g > g_min = 1/ (a+1) * (1 + 1 / (n * p))
- Конечно, заказы в декартовых произведениях не важны, поэтому я могу транспонировать строки и столбцы моей матрицы, чтобы сделать ее более удобной, например:
f1 f2 f3
r1 x x
r2 x
r3 x x
можно изменить как
f1 f3 f2
r1 x x
r3 x x
r2 x
И есть оптимальное решение, которое можно запросить (f1,f3) x (r1,r3) + (f2) x (r2)
- Испытывать все решения и искать более низкую стоимость не вариант, потому что комбинаторика взрывается:
for each permutation on rows: (n!)
for each permutation on columns: (p!)
for each possible covering of the n x p matrix: (time unknown, but large...)
compute cost of the covering
поэтому я ищу приблизительное решение. У меня уже есть какой-то жадный алгоритм, который находит покрытие для данной матрицы (оно начинается с унитарных ячеек, а затем объединяет их, если доля пустых ячеек в слиянии ниже некоторого порога).
Чтобы запомнить некоторые цифры, мой n находится где-то между 1 и 1000, а мой p где-то между 1 и 200. Структура покрытия действительно «блочная», потому что записи приходят в классах, для которых запрашиваемые поля похожи , К сожалению, я не могу получить доступ к классу записи ...
Вопрос 1 : Есть ли у кого-нибудь идея, умное упрощение или ссылка на статью, которая может быть полезной? Поскольку у меня много запросов, то алгоритм, который хорошо работает в среднем , - это то, что я ищу (но я не могу позволить, чтобы он работал очень плохо в некоторых экстремальных случаях, например, для запроса всей матрицы когда n и p большие, а запрос действительно довольно редкий).
Вопрос 2 : На самом деле проблема еще более сложна: стоимость на самом деле больше похожа на форму: a + n * (p^b) + c * n' * p', где b - это константа <1 (после запроса записи поле, не слишком дорого запрашивать другие поля), а <code>n' * p' = n * p * (1 - g) - это количество ячеек, которые я не хочу запрашивать (потому что они недействительны, и при запросе недопустимых вещей взимается дополнительная плата). Я даже не могу мечтать о быстром решении этой проблемы, но все же ... идея кого-нибудь?