Изменения

Пусть задана последовательность из <tex>n</tex> запросов к внешней памяти. Необходимо решить для каждого запроса: сохранить его значение в кэш размера <tex>k</tex> или оставить его во внешней памяти.

'''Кэш попадание''' (англ. ''cache hit'') {{---}} результат обрабатываемого запроса уже хранится в кэше и его можно вернуть мгновенно. Будем считать, что время обработки такого запроса равно 0.

'''Кэш промах''' (англ. ''cache miss'') {{---}} результат обрабатываемого запроса отсутствует в кэше и чтобы его получить необходимо обращаться к внешней памяти. При получении ответа мы так же можем сохранить новое значение в кэш, вытеснив(удалив) некоторое старое. Будем считать, что время обработки такого запроса равно 1.

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

'''<tex>\alpha</tex>-оптимальность''' {{---}} свойство онлайн алгоритма, означающее что время работы этого алгоритма на любых входных данных не более чем в <tex>\alpha</tex> раз больше, чем у любого оптимального оффлайновогоалгоритма, с точностью до аддитивной константы.

== Ограничение Проблема детерминированных алгоритмов ==

<tex>k</tex> {{---}} размер кэша. Любой <tex>\alpha</tex>-оптимальный детерменированный онлайн детерминированный алгоритм кэширования имеет <tex>\alpha \geq geqslant k</tex>.

ГаОбозначим <tex>T_\text{opt}(\sigma)</tex> и <tex>T_\text{det}(\sigma)</tex> как время работы оптимального и детерминированного алгоритма на входе <tex>\sigma</tex>. По определению <tex>\alpha</tex>-гаоптимальности имеем <tex>\forall\sigma \; T_\text{det}(\sigma) < \alpha \cdot T_\text{opt}(\sigma) + C</tex>. Покажем, что достаточно построить для любого <tex>n</tex> такую последовательность запросов <tex>\sigma_n</tex>, что <tex>T_\text{det}(\sigma_n) \geqslant k \cdot T_\text{opt}(\sigma_n) + C_0</tex>. Так как <tex>\lim\limits_{n-га>\infty}T = \infty</tex>, получаем <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \geqslant k</tex>. С другой стороны можно подставить в неравенство с квантором значение <tex>\sigma_n</tex> и получить <tex>T_\text{det}(\sigma_n) < \alpha \cdot T_\text{opt}(\sigma_n) + C</tex>, а потом снова перейти к пределу <tex>\lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>. Перепишем неравенства в следующем виде <tex>k \leqslant \lim\limits_{n->\infty}\frac{T_\text{det}(\sigma_n)}{T_\text{opt}(\sigma_n)} \leqslant \alpha</tex>, откуда очевидно, что <tex>\alpha \geqslant k</tex>.

Теорема доказана.}}  == Алгоритм ==Пусть нам дан граф Теперь построим <tex>G = \{V, E\}sigma_n</tex>.<code> '''int''' minCut(G): answer = В последовательности будем использовать только <tex>\inftyk + 1</tex> '''for''' i = 1 '''to''' count curCut = getCut(G) '''if''' curCut < answer answer = curCut '''return''' answer</code>Так как алгоритм вероятностный и функция различных запросов. Первыми <tex>\mathrm{getCut}k</tex> возвращает вес случайного потоказапросами возьмём любые различные, а не минимальногодальше, то для того, чтобы наверняка найти вес минимального, необходим вызвать эту функцию <tex>count</tex> раз. Какое конкретное значение <tex>count</tex> выбрать будет описано ниже.Реализация функции <tex>\mathrm{getCut}</tex> {{---}} это и есть основа алгоритма. Будем действовать каждым следующим образом: пока вершин больше двухзапросом поставим тот, будем выбирать случайное ребро и стягивать его. Когда в графе останется две вершины, то количество ребер между этими вершинами будет равно весу некоторого разреза исходного графа. <code> '''int''' getCut(graph): G = graph vertexCount = количество вершин результата которого нет в G '''while''' vertexCount > 2 edge = случайное ребро из G contract(edge) <font color="darkgreen">//стягиваем ребро edge</font> vertexCount-- edgeCount = количество ребер данный момент в G '''return''' edgeCount</code>== Корректность алгоритма ==Докажем корректность кэше детерминированного алгоритма. Для удобства доказательства Это хоть и оценок вероятностей, будем считать, что мы ищем не просто вес минимального разреза, а величину конкретного минимального разреза. То есть зафиксируем какой-то один из минимальных разрезов, и если функция <tex>\mathrm{getCut}</tex> вернет правильный весявное, но посчитает его на другом минимальном разрезе, то будем считатькорректное задание последовательности, потому что ответ получен неверный. Это условие не ухудшает оценки вероятностей и время работы алгоритма.{{Лемма|about = 1|id = Лемма1|statement = Пусть <tex>w</tex> {{---}} некоторая мультивершинаимея алгоритм, <tex>u</tex> и <tex>v</tex> - какие-то две из вершин, которые были стянуты мы можем вычислить каждый запрос в вершину <tex>w</tex>. Тогда существует такой путь <tex>p</tex> в исходном графе <tex>G</tex> между вершинами <tex>u</tex> и <tex>v</tex>, что ко всем ребрам этого пути была применена операция стягивания.  |proof =Рассмотрим подграф <tex>G'</tex> исходного графа <tex>G</tex> в который входят все ребра, которые были стянуты в вершину <tex>w</tex>. Очевидно, что <tex>G'</tex> связен, а значит в нем существует путь между его любыми двумя вершинами. Следовательно, существует путь между <tex>u</tex> и <tex>v</tex>, состоящий из стянутых ребер. Лемма доказана.}}  {{Лемма|about = 2|id = Лемма2|statement = Если стянуть некоторое ребро <tex>e = uv</tex> в графе G, то вес минимального разреза в графе <tex>G' = G\setminus e</tex> будет не меньше чем вес минимального разреза в исходном графе <tex>G</tex>. |proof =Составим биекцию между ребрами графов <tex>G</tex> и <tex>G'</tex>, не рассматривая ребра между вершинами <tex>u</tex> и <tex>v</tex> в графе <tex>Gsigma_n</tex>на основе предыдущих. Очевидно, что это возможно, исходя из следующих соображений. Все ребра в <tex>G</tex>, не инцидентные вершинам <tex>u</tex> и <tex>v</tex>, остались без изменений, а всем ребрам, инцидентным этим вершинам, по определению стягивания можно сопоставить новое ребро в <tex>G'</tex>. Пусть <tex>\langle A', B' T_\rangle</tex> text{{---det}} минимальный разрез в графе <tex>G'</tex>, и, не уменьшая общности, <tex>w \in A'</tex>. Рассмотрим разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex>. Исходя из биекции между ребрами и тем, что все ребра вида <tex>uv</tex> не пересекают разрез (так как <tex>u \in A, v \in A</tex>), то <tex>w(A', B'sigma_n) = w(A, B')</tex>. Тогда если разрез <tex>\langle A, B' \rangle</tex> в графе <tex>G</tex> {{---}} минимален, вес минимального разреза в <tex>G'</tex> совпадает с весом минимального размера в <tex>G</tex>. Если в <tex>G</tex> существует разрез меньшего веса, то вес минимального разреза в <tex>G'</tex> больше чем в <tex>G</tex>. Лемма доказана.}}  {{Лемма|about = 3|id = Лемма3|statement = Пусть <tex>c</tex> {{---}} вес минимального потока в графе <tex>G</tex>. Тогда <tex>m \geqslant nc/2</tex>.  |proof =Заметим, что, чтобы выполнялось условие, степень каждой вершины должна быть не менее, чем <tex>c</tex>. Действительно, пусть <tex>\deg(v) < c</tex> для некоторой вершины <tex>v \in V</tex>. Тогда <tex>w(v, G \setminus v) = \deg(v) < c</tex>, что противоречит условию. Далее, по [[Лемма_о_рукопожатиях|лемме о рукопожатиях]] имеем, что <tex>m \geqslant nc/2</tex>. Лемма доказана.}}  {{Лемма|about = 4|id = Лемма4|statement = Функция <tex>\mathrm{getCut}</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> тогда и только тогда, когда ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex>, не будет стянуто. |proof =Необходимость. От противного. Если некоторое ребро <tex>uv</tex>, принадлежащее разрезу <tex>\langle A, B \rangle</tex> в <tex>G</tex> будет стянуто, то обе вершины <tex>u</tex> и <tex>v</tex> будут принадлежать одной мультивершине, а значит <tex>G'</tex> не соответствует разрезу <tex>\langle A, B \rangle</tex>. Противоречие. Достаточность. Пусть ни одно ребро, принадлежащее разрезу <tex>\langle A, B \rangle</tex> не было стянуто. Рассмотрим произвольную пару вершин <tex>u \in A</tex> и <tex>v \in B</tex> в графе <tex>G</tex>. Если алгоритм стянул <tex>u</tex> и <tex>v</tex> в одну мультивершину в <tex>G'</tex>, тогда по [[#лемма1|лемме 1]] существует путь <tex>p</tex> между вершинами <tex>u</tex> и <tex>v</tex>, и все ребра этого пути были стянуты. Но <tex>p</tex> пересекает разрез <tex>\langle A, B \rangle</tex>, что противоречит предположению, что ни одно ребро не было стянуто. Значит, вершины из любой пары <tex>u \in A</tex>, и <tex>v \in B</tex> были стянуты в разные мультивершины. А так, как стянутый граф состоит только из двух мультивершин, значит одна из них была получена стягиванием всех вершин из <tex>A</tex>, а другая {{---}} из <tex>B</tex>. Лемма доказана.}}  {{Теорема|statement =Для вероятности <tex>p</tex> того, что функция <tex>\mathrm{getCut}</tex> после своего выполнения получит стянутый граф <tex>G'</tex> соответствующий конкретному разрезу <tex>\langle A, B \rangle</tex> исходного графа <tex>G</tex> верна следующая оценка снизу {{---}} <tex>p(\langle A, B \rangle) \geqslant</tex> <tex dpi="150">\frac{2}{n^2}</tex>.|proof =По [[#Лемма4|лемме 4]] искомый стянутый граф будет получен тогда и только тогда, когда ни одно из ребер разреза не будет стянуто. Так как на каждой итерации алгоритма мы случайно выбираем ребро для стягивания, то можно оценить вероятность того, что ни одно из ребер разреза не будет стянуто. Каждое стягивание уменьшает количество ребер на <tex>1</tex>. Таким образом после <tex>i</tex>-ой итерации алгоритма количество вершин в текущем графе будет равно <tex>n - i + 1</tex>. Рассчитаем вероятность того, что на <tex>i</tex>-ой итерации будет стянуто ребро из разреза <tex>\langle A, B \rangle</tex>. Пусть <tex>w = w(A, B)</tex>. По [[#Лемма2|лемме 2]] величина минимального потока в текущем графе будет не меньше, чем <tex>w</tex>, и в нем будет не менее <tex dpi="150">\frac{w(n-i+1)}{2}</tex> вершин по [[#Лемма3|лемме 3]]. Тогда вероятность того, что будет стянуто ребро из разреза <tex>\langle A, B \rangle</tex>, при условии, что до этого не было стянуто ни одно из ребер разреза, будет не более

Посмотрим как на входе <tex dpi="150">\frac{2\cdot wsigma_n</tex> будет работать следующий, возможно оптимальный оффлайн алгоритм (Aиндекс mopt). Первые k элементов алгоритм добавит в кэш,B)так как они все различные. Когда случается промах, алгоритм среди значений в кэше и только что обработанного запроса вытесняет то, которое в последующих запросах встречается первый раз как можно позже или не встречается совсем. При таком выборе, следующий кэш промах случится не менее чем через <tex>k</tex> запросов. Предположим, что это не так, и кэш промах случился через <tex>m < k</tex> запросов. Так как количество различных запросов на 1 больше размера кэша, то этот промах произошёл на запросе, который мы вытеснили из кэша в предыдущий раз. Из <tex>m < k</tex> следует, что есть запросы, которые мы не встретили среди первых <tex>m</tex>, а значит их первое вхождение будет после того значения, которое мы вытеснили. Получили противоречие, а значит предположение не верно. Оценим время работы возможно оптимального оффлайн алгоритма <tex>T_\text{mopt}\leqslant k + \lceil\frac{w\cdot (n-ik}{k+1}\rceil \leqslant \frac{n}{k}</tex>. Последнее неравенство выполнено, т.к. <tex>n \gg k</tex>. Очевидно <tex>T_\text{opt}(\sigma_n) \leqslant T_\text{mopt}(\sigma_n)</tex>, откуда <tex>T_\text{opt}=(\sigma_n) \leqslant \frac{2n}{n-i+1k}.</tex>

Обозначим за <tex>T_\xi_i</tex> событие, что на <tex>i</tex>-ой итерации случайным образом будет выбрано ребро из разреза <tex>\langle A, B \rangle</tex>. Тогда мы только что установили, что <tex dpi="140">p(\xi_i | \overlinetext{\xi_1det} (\wedge \ldots \wedge \overline{\xi_{i-1}}sigma_n) = n = k \leqslant cdot \frac{2}{n-i+1}.</tex> <tex dpi="140">p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}k}) = 1 - p(\xi_i | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}) \geqslant 1 - k \frac{2}{n-i+1} = cdot T_\frac{n-i-1}text{n-i+1opt}.</tex> Тогда вероятность того, что во время работы функции не будет стянуто ни одно ребро оценивается следующим образом: <tex dpi="140">p(\overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{n-2}}sigma_n) = \prodRightarrow T_\limits_{i=1}^text{n-2det} p(\overline{\xi_i} | \overline{\xi_1} \wedge \ldots \wedge \overline{\xi_{i-1}}sigma_n) \geqslant </tex> <tex dpi="140">\geqslant \prod\limits_{i=1}^{n-2} \frac{n-i-1}{n-i+1} = \frac{n - 2}{n} k \cdot T_\fractext{n-3opt}{n-1} \cdot \frac{n-4}{n-2} \cdot \ldots \cdot \frac{2}{4} \cdot \frac{1}{3} = (\frac{2}{n(n-1sigma_n)} \geqslant \frac{2}{n^2}.+ 0</tex>

<tex> e^x \geqslant 1 + x</tex> для любого вещественного <tex>x</tex>Когда в кэш поступает запрос:* Если кэш попадание, то просто помечаем значение.* Если кэш промах*# Если все элементы уже помечены, снимаем пометки со всех значений.*# Берём случайное не помеченное значение и вытесняeм его, а новое значение помечаем.

Вероятность того== Оценка времени работы алгоритма ==Будем рассматривать только те запросы, которые ставят метку в кэше. Из алгоритма понятно, что мы если запрос не получим правильный ответ после ставит метку, то кэш работает с уже помеченным значением, а значит это кэш попадание. Разобьём эти запросы на фазы так, чтобы границей между фазами был запрос, который сбрасывает все пометки. Так, первый запрос в первой фазе {{---}} это первый запрос во всей последовательности, а первый запрос в других фазах {{---}} это запрос, выполняющий сброс всех пометок. Пронумеруем фазы от <tex>1</tex> до <tex>p</tex>. Рассмотрим фазу <tex>counti</tex> независимых запусков равна . Разделим все значения на 2 множества: старые {{---}} которые были в фазу <tex dpi="140">(i-1</tex> и новые {{---\frac{2}{n^2})^cвсе остальные. Обозначим количество новых значений в фазе <tex>i</tex> как <tex>m_i</tex>. Тогда количество старых будет <tex>k-m_i</tex>.

Пусть Посчитаем матожидание количества промахов на фазе <tex>count i</tex>. Оно максимально, когда в фазе сначала идут новые значения, а потом старые, потому что тогда каждое новое значение имеет больший шанс вытеснить старое, и при обращении к нему случится кэш промах. Так как на начало фазы <tex>i</tex> в кэше хранятся только значения фазы <tex>i-1</tex>, то понятно, что все новые запросы фазы <tex>i</tex> приведут к кэш промаху. Рассмотрим <tex>j</tex>-й среди старых запросов. Посмотрим на те значения фазы <tex>i-1</tex>, которые к текущему моменту были вытеснены или помечены. Заметим, что если значение было помечено, то его уже невозможно вытеснить, а если было вытеснено, то чтобы его пометить, необходимо вытеснить другое значение. <tex>j-1</tex> старых значений пометили сами себя, потому что они были в предыдущей фазе, а <tex>m_i</tex> пометить себя не могли, а поэтому вытеснили случайное подмножество из остальных <tex>k - (j-1)</tex>. Возможно они вытеснили кого-то из первых <tex>j-1</tex> старых значений, которые при обработке вытеснили кого-то другого. Главное, что распределение это не меняет. Вероятность того, что <tex>j</tex>-й старый запрос приведёт к кэш промаху, равена тому, что он был вытеснен из кэша <tex>P_j = n^2\lnfrac{m_i}{k - (nj - 1)}</tex>. Тогда в силу указанного выше неравенства:

В итоге, матожидание времени работы алгоритма не превосходит суммы матожиданий кэш промахов на каждой фазе, которое мы ограничили сверху суммой <tex dpi="140">(1-\frac{2}{n^2})^{count} \leqslant e^{count \cdot (-\frac{2}{n^2})} = e^{-2 \ln(n)} = \frac{1}{n^2}m_i</tex>и матожиданием промахов на старых значениях.

То есть, если вызвать функцию <tex>\mathrmbegin{getCutalign}T_\text{rnd} &\leqslant \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j}E(\text{кэш промах на}\; j)\right) = \\ &= \sum\limits_{i=1}^p\left(m_i + \sum\limits_{j=1}^{k-m_i}\frac{m_i}{k-j+1}\right) = \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=1}^{k-m_i}\frac{1}{k-j+1}\right) = \\ &= \sum\limits_{i=1}^p m_i\left(1 + \sum\limits_{j=m_i+1}</tex> <tex>n^2{k}\frac{1}{j}\lnright) = \sum\limits_{i=1}^p m_i(n1 + H_k - H_{m_i+1})</tex> раз, и после каждой итерации запоминать минимум, то вероятность того, что найденный ответ будет неверен <tex> \leqslant \fracsum\limits_{i=1}^p m_iH_k = H_k\sum\limits_{ni=1}^2p m_i\end{align}</tex>. Даже при небольших значениях <tex>n</tex> алгоритм практически гарантированно выдает правильный ответ.

== Оценка времени Теперь оценим снизу время работы оптимального алгоритма ==Время работы функции . Рассмотрим фазы <tex>\mathrm{getCut}i</tex> {{---}} и <tex>O(n^2)i-1</tex>. Функция работает Среди запросов этих фаз всего <tex>O(n^2\log(n))k + m_i</tex> раз. Итоговое время работы {{---}} различных значений, а потому оптимальный алгоритм обязан промахнуться хотябы <tex>O(n^4 \log(n))m_i</tex>раз.

<tex>\begin{align}T_\text{opt} &=\sum\limits_{i= Оптимизация алгоритма 1}^{p}E(\text{кэш промах на}\; i) =\\ &=Каргер совместно со Штейном (англ. ''Stein'') придумали оптимизацию алгоритма Каргера, значительно ускоряющую время его работы. Новый алгоритм называется в честь обоих создателей \frac{1}{---2}} алгоритм Каргера-Штейна \left(E(англ. ''Karger-Stein algorithm''). Его суть заключается в следуюшем. Заметим, что вероятность стягивания вершины, принадлежащей минимальному разрезу, в начале выполнения функции <tex>\mathrmtext{getCutкэш промах на}</tex> довольно мала, в то время, как вероятность стянуть ребро, которое не следует стягивать, ближе к концу работы функции существенно возрастает. Тогда будем использовать следующую рекурсивную версию алгоритма:# Запускаем функцию <tex>\mathrm; 1) + E(\text{getCutкэш промах на}</tex> и стягиваем ребра до тех пор, пока не останется <tex>\frac; p) + \sum\limits_{ni=1}^{p-1}\sqrtleft(E(\text{2кэш промах на}\; i) + E(\text{кэш промах на}</tex> вершин.\; i+1)\right)\right) \geqslant \\# Запускаем независимо эту же функцию для получившегося графа дважды и возвращаем минимальный из ответов.Такая модификация алгоритма выдает правильный ответ с точностью, не менее <tex> &\geqslant \frac{1}{2}\log(n)sum\limits_{i=1}^{p}</tex>. Время работы функции <tex>m_i\mathrmend{getCutalign}</tex> вычисляется рекурсивной функцией:

Это медленнее, чем оригинальный алгоритм, однако вероятность нахождения разреза минимального веса экспоненциально выше. Достаточно запустить алгоритм <tex>cT_\log^2(n)</tex> раз, где <tex>ctext{rnd} \leqslant 2H_k \cdot T_\text{opt}</tex> - некоторая константа. Действительно, рассчитаем вероятность неправильного ответа также, как раньше:

Алгоритм является <tex dpi="160">(12H_k</tex>-оптимальным, или, что более практично, <tex>\frac{1}mathcal{log(n)O})^{c\log^2(n)} \leqslant e^{c\log^2ln(nk) \cdot -\frac{1}{log(n)}} = \frac{1}{n^c}.</tex>-оптимальным.