Я решил несколько проблем, которые похожи на это.
Во-первых, если вам не нужен точный ответ, я бы обычно предлагал изучить что-то вроде генетического алгоритма или сделать жадный алгоритм. Это не будет правильно, но в целом это тоже не будет плохо. И это будет намного быстрее, чем точный алгоритм. Например, вы можете начать со всех точек в качестве точек кэширования, а затем найти точку, которая больше всего снижает ваши затраты, сделав ее точкой без кэширования. Продолжайте, пока удаление следующего не приведет к увеличению стоимости, и используйте это в качестве решения. Это не будет лучше. Как правило, это будет достаточно хорошо.
Если вам нужно нужен точный ответ, вам потребуется грубый поиск большого количества данных. Предполагая, что указана начальная точка кэша, у вас будет 2 24 = 16 777 216 возможных наборов точек кэша для поиска. Это дорого.
Хитрость в том, чтобы сделать это дешевле (обратите внимание, не дешево, а просто дешевле) - найти способы сократить поиск. Примите к сведению тот факт, что если выполнение в 100 раз больше работы с каждым набором, на который вы просматриваете, позволяет убрать в среднем 10 точек из рассмотрения в качестве точек кэширования, то ваш общий алгоритм посетит на 0,1% больше наборов и ваш код будет работать В 10 раз быстрее Следовательно, стоит отложить удивительное количество энергии на обрезку рано и часто, даже если этап обрезки довольно дорогой.
Часто вам нужно несколько стратегий обрезки. Один из них, как правило, «лучшее, что мы можем сделать отсюда, хуже, чем лучшее, что мы нашли ранее». Это работает лучше, если вы уже нашли довольно хорошее лучшее решение. Поэтому часто стоит потратить немного усилий, чтобы провести локальную оптимизацию в поиске решений.
Как правило, эти оптимизации не изменят тот факт, что вы выполняете огромный объем работы. Но они позволяют вам выполнять работу на порядок меньше.
Моя первоначальная попытка была бы основана на следующих наблюдениях.
- Предположим, что
x - это точка кэширования, а y - ее ближайший сосед кэширования. Тогда вы всегда можете сделать какой-нибудь путь из x в y кеш "бесплатно", если просто направите трафик обновления кеша от x до y по этому пути. Поэтому без потери общности множество точек кеша подключается к сетке.
- Если минимальная стоимость может превысить текущую лучшую стоимость, найденную нами, мы не на пути к глобальному решению.
- Как только сумма скорости доступа из всех точек на расстоянии, превышающем 1 от точек кеша, плюс наибольшая частота доступа соседа к точке кеша, которую вы все еще можете использовать, станет меньше частоты кеша, добавив больше Кэширование точек всегда будет потерей. (Это будет «дорогое состояние, которое позволит нам остановиться на 10 минут раньше».)
- Самый верхний сосед доступа из текущего набора точек кэширования является разумным кандидатом для следующей точки кэширования. (Есть несколько других эвристик, которые вы можете попробовать, но это разумно.)
- Любая точка, чья общая частота доступа превышает частоту кеша, обязательно должна быть точкой кеширования.
Возможно, это не лучший набор наблюдений для использования. Но это может быть довольно разумно. Чтобы воспользоваться этим, вам понадобится как минимум одна структура данных, с которой вы, возможно, не знакомы. Если вы не знаете, что такое приоритетная очередь 1038 *, найдите эффективную очередь на вашем языке. Если вы не можете его найти, heap довольно легко внедрить и хорошо работает как очередь с приоритетами.
Имея это в виду, предполагая, что вы получили информацию, которую вы описали, и начальный узел кэша P, здесь приведен псевдокод алгоритма для поиска лучшего.
# Data structures to be dynamically maintained:
# AT[x, n] - how many accesses x needs that currently need to go distance n.
# D[x] - The distance from x to the nearest cache node.
# CA[x] - Boolean yes/no for whether x is a cache node.
# B[x] - Boolean yes/no for whether x is blocked from being a cache node.
# cost - Current cost
# distant_accesses - The sum of the total number of accesses made from more than
# distance 1 from the cache nodes.
# best_possible_cost - C * nodes_in_cache + sum(min(total accesses, C) for non-cache nodes)
# *** Sufficient data structures to be able to unwind changes to all of the above before
# returning from recursive calls (I won't specify accesses to them, but they need to
# be there)
# best_cost - The best cost found.
# best_solution - The best solution found.
initialize all of those data structures (including best)
create neighbors priority queue of neighbors of root cache node (ordered by accesses)
call extend_current_solution(neighbors)
do what we want with the best solution
function extend_current_solution (available_neighbors):
if cost < best_cost:
best_cost = cost
best_solution = CA # current set of cache nodes.
if best_cost < best_possible_cost
return # pruning time
neighbors = clone(available_neighbors)
while neighbors:
node = remove best from neighbors
if distant_accesses + accesses(node) < C:
return # this is condition 3 above
make node in cache set
- add it to CA
- update costs
- add its immediate neighbors to neighbors
call extend_current_solution
unwind changes just made
make node in blocked set
call extend_current_solution
unwind changes to blocked set
return
Это займет много работы, чтобы написать это, и вы должны быть осторожны, чтобы поддерживать все структуры данных. Но я держу пари, что, несмотря на то, как это выглядит тяжеловесно, вы обнаружите, что оно сокращает пространство поиска настолько, чтобы оно работало быстрее, чем существующее решение. (Это все еще не будет быстро).
Удачи!
Обновление
Когда я больше думал об этом, я понял, что лучше заметить, что если вы можете разрезать «не узел кэша, не заблокированный узел» на две части, то вы можете решить эти части независимо. Каждая из этих подзадач решается на несколько порядков быстрее, чем вся проблема, поэтому постарайтесь сделать это как можно быстрее.
Хорошая эвристика для этого - следовать следующим правилам:
- Пока не было достигнуто никакого края:
- Двигайтесь к ближайшему краю. Расстояние измеряется по тому, насколько короткий кратчайший путь проходит по неблокируемому неблокируемому набору.
- Если два ребра равноудалены, разорвать связи в следующем порядке предпочтения:
(1, x), (x, 1), (5, x), (x, 5).
- Разорвите все оставшиеся связи, предпочитая двигаться к центру ребра.
- Случайно разорвать все оставшиеся связи.
- Пока ребро достигнуто, а у вашего компонента все еще есть ребра, которые могут стать частями кэша:
- Если вы можете сразу перейти к ребру и разделить ребра на два компонента, сделайте это. И для «ребра в наборе кеша» и для «ребра не в наборе кеша» вы получите 2 независимых подзадачи, которые более поддаются решению.
- В противном случае двигайтесь по кратчайшему пути к фигуре в середине вашего отрезка ребер.
- Если есть связь, разбейте ее в пользу того, что делает линию от добавленной части к добавленному элементу кэша как можно ближе к диагонали.
- Случайно разорвать все оставшиеся связи.
- Если вы провалились здесь, выберите случайным образом. (У вас должна быть довольно маленькая подзадача на этом этапе. Не нужно быть умным.)
Если вы попробуете это, начав с (3, 3) в качестве точки кеширования, вы обнаружите, что в первых нескольких решениях вы обнаружите, что 7/16 времени вам удастся разделить на две четные проблемы, 1 / 16 раз вы блокируете в точке кеша и завершаете, 1/4 времени вам удается вырезать блок 2x2 в отдельную задачу (что делает общее решение для этой части в 16 раз быстрее) и 1/4 от время, когда вы хорошо ориентируетесь на пути к решению, которое находится на пути к тому, чтобы либо быть помещенным в коробку (и быстро исчерпанным), либо быть кандидатом на решение с большим количеством точек кеша, которое сокращается за то, что оно находится на пути к плохое решение.
Я не буду давать псевдокод для этого варианта. Он будет иметь много общего с тем, что я имел выше, с некоторыми важными деталями. Но я бы поспорил, что на практике он будет работать на порядки быстрее, чем ваше оригинальное решение.