Эффективный подход в сетке
Проблема: мы должны заполнить двумерную сетку размером m * n символами из набора S так, чтобы число различных субматриц в результирующей сетке было близко к заданному числу k.
Этот вопрос является производным от http://www.codechef.com/JULY14/problems/GERALD09
Ограничения:
1<= П, м<16
1<= к <= Т * п * т * п
| S | = 4
ограничение по времени = 0,1 сек
Предположение: Две подматрицы различаются, если они не имеют одинаковые размеры или, по крайней мере, пара символов в соответствующих местах не совпадает.
Мой подход: Мы можем начать со случайной сетки и цикла, пока найдено приемлемое решение, и на каждой итерации мы можем увеличивать / уменьшать случайность в зависимости от нашего текущего состояния (но мы можем застрять в локальных оптимальных состояниях).
Но проблема в том, что я не знаю эффективного способа вычисления количества различных подматриц в подсетке. Я пробовал хеширование для подсчета, которое довольно быстро (O (n2м2) * стоимость генерации / поиска значения хеша для подсетки).
Но этот подход не дает точных ответов из-за коллизий хеш-значений, и даже после исправления этого с помощью комментария @Vaughn Cato я могу выполнить 15-25 итераций для оптимального определения состояния, и этого недостаточно.
Недавно я узнал, что имитационный отжиг можно использовать для решения подобных проблем.
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
Я ищу какой-либо эффективный подход для решения этой проблемы оптимизации.
Заранее спасибо.
Решение
Я думаю, что они опубликуют статью в какой-то момент, но вот возможная идея для этой конкретной проблемы:
Я сгенерировал локально все возможные числа подматриц, возможных для конкретного n а также m,
За n=m=3 Я получил только 11 снаружи 81 возможности.
За n=3,m=4 Я получил только 19 вне возможного 144 ценности.
Более того, когда я генерировал значения, я получил все 19 возможные варианты в самом начале — после 263000 матрицы из возможных 16M У меня уже были они. (Я сформировал в лексикографическом порядке)
Итак, я предполагаю, что одним из возможных решений может быть предварительное вычисление как можно большего числа различных значений K что может быть достигнуто для данного n а также m, сохраните или семя для генератора случайных чисел или каким-либо другим способом, который вам нужен O(1) символов в n-m-k триплет, и для конкретного теста просто проверьте два соседних значения — сначала k больше и меньше, чем дано.
Более того, так как количество возможных K значения не велики, может быть возможно генерировать их другим способом: учитывая все возможные значения K за nxm Таблица, наряду с соответствующими таблицами, мы можем только вернуться к значениям в следующей строке, и попытаться получить все возможные матрицы со всеми различными значениями K за nx(m+1),
Другие решения