Ответ 1

Я рассмотрел несколько проблем, которые были чем-то вроде этого.

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

Если вам нужен точный ответ, вам нужно будет искать грубую силу для большого количества данных. Предполагая, что указана начальная точка кэша, у вас будет 2 ²⁴= 16,777,216 возможных наборов точек кеша для поиска. Это дорого.

Трюк, чтобы сделать это дешевле (обратите внимание, не дешево, просто дешевле) находит способы сократить ваш поиск. Примите к сведению тот факт, что если вы выполняете в 100 раз больше работы над каждым набором, на который вы смотрите, вы можете удалить в среднем 10 баллов из рассмотрения в качестве точек кеша, тогда ваш общий алгоритм будет посещать 0,1% столько наборов, и ваш код будет работать В 10 раз быстрее. Поэтому стоит потратить удивительное количество энергии на обрезку рано и часто, даже если шаг обрезки довольно дорог.

Часто вам нужны несколько стратегий обрезки. Один из них, как правило, "лучшее, что мы можем сделать здесь, хуже всего того, что мы нашли ранее". Это работает лучше, если вы уже нашли довольно хорошее лучшее решение. Поэтому часто стоит потратить немного усилий на локальную оптимизацию в поиске решений.

Обычно эти оптимизации не изменят тот факт, что вы выполняете огромную работу. Но они позволяют вам делать на порядок меньше работы.

Моя первоначальная попытка при этом использовала бы следующие наблюдения.

• Предположим, что x является точкой кэша, а y является ближайшим соседним кешированием. Тогда вы всегда можете сделать какой-то путь от x до y cache "бесплатно", если вы просто проложите трафик обновления кэша от x до y по этому пути. Поэтому без потери общности набор точек кэша подключен к сетке.
• Если бы минимальная стоимость могла завершиться с превышением текущей лучшей стоимости, которую мы нашли, мы не на пути к глобальному решению.
• Как только сумма скорости доступа из всех точек на расстоянии больше 1 из точек кеша плюс максимальная частота доступа соседа к точке кеша, которую вы все еще можете использовать, меньше частоты кеша, добавьте больше точки кеша всегда будут потерей. (Это было бы "дорогостоящим условием, которое позволяет нам остановиться на 10 минут раньше".)
• Наивысший доступ к совпадению текущего набора точек кеша является разумным кандидатом для следующей точки кеша, чтобы попробовать. (Есть несколько других эвристик, которые вы можете попробовать, но это разумно.)
• Любая точка, полная частота доступа которой превышает частоту кеша, абсолютно должна быть точкой кэширования.

Это может быть не лучший набор наблюдений. Но это, вероятно, будет довольно разумным. Чтобы воспользоваться этим, вам понадобится хотя бы одна структура данных, с которой вы, возможно, не знакомы. Если вы не знаете, что такое приоритетная очередь, посмотрите на эффективный вариант на выбранном вами языке. Если вы не можете найти его, heap довольно легко реализовать и хорошо работает как приоритетная очередь.

Имея это в виду, предполагая, что вам была предоставлена ​​информация, которую вы описали, и исходный кеш node 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

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

Удачи!

Update

Когда я подумал об этом больше, я понял, что лучше заметить, что если вы можете вырезать "не кеш node, а не заблокированный node" на две части, то вы можете решить эти штук независимо. Каждая из этих подзадач на порядок быстрее решать, чем вся проблема, поэтому постарайтесь сделать это как можно быстрее.

Хорошей эвристикой для этого является соблюдение следующих правил:

• Пока никакого края не достигнуто:
  • Двигайтесь к ближайшему краю. Расстояние измеряется по краткости кратчайшего пути по не кешу, неблокированному набору.
  • Если два ребра равноудалены, разломайте привязки в соответствии со следующим порядком предпочтений: (1, x), (x, 1), (5, x), (x, 5).
  • Разделите все оставшиеся галстуки в соответствии с предпочтением двигаться по направлению к центру края.
  • Случайно разбить любые оставшиеся связи.
• Пока достигнут край, и ваш компонент по-прежнему имеет края, которые могут стать частями кеша:
  • Если вы можете сразу переместиться в край и разделить куски краев на два компонента, сделайте это. Как для "края в кеш-наборе", так и "край не в наборе кеша" вы получите две независимые подзадачи, которые более удобны.
  • Повторяйте движение по кратчайшему пути к куску в середине вашего участка кусков края.
  • Если есть галстук, разделите его в пользу того, что делает линию от добавленной части добавленной кеше максимально приближенной к диагонали.
  • Случайно разбить любые оставшиеся связи.
• Если вы провалитесь сюда, выберите случайным образом. (На данный момент у вас должна быть небольшая подзадача. Не нужно быть умным.)

Если вы попытаетесь начать с (3, 3) в качестве точки кеша, вы обнаружите, что в первых нескольких решениях вы обнаружите, что 7/16 времени, которое вам удалось разрезать на две четные проблемы, 1/16 из того времени, когда вы блокируете точку кеша и заканчиваете, 1/4 времени, когда вам удается вырезать блок 2x2 в отдельную проблему (чтобы общее решение выполнялось в 16 раз быстрее для этой части) и 1/4 из время, которое вы набираете хорошо на своем пути к решению, которое находится на пути к тому, чтобы быть в коробке (и быстро исчерпано), или быть кандидатом на решение с большим количеством точек кеша, которое обрезается, чтобы быть на пути к тому, чтобы быть плохое решение.

Я не буду давать псевдокод для этого варианта. У него будет много общего с тем, что у меня было выше, с целым рядом важных деталей. Но я был бы готов поспорить, что на практике он будет работать на порядки быстрее, чем ваше оригинальное решение.

Ответ 2

Решение - это множество, поэтому это не проблема линейного программирования. Это особый случай подключения объекта. У Bardossy и Raghavan есть эвристика, которая выглядит многообещающе: http://terpconnect.umd.edu/~raghavan/preprints/confl.pdf

Ответ 3

является спиральным кэшем аналогично решению? http://strumpen.net/ibm-rc24767.pdf