4511
правок
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 11:44, 12 сентября 2018
, 12 сентября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 92: | Строка 92: | ||
'''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | '''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | ||
Зная поток в сети Fv, можно вычислить максимальный поток при помощи алгоритма нахождения дополняющего пути [4]. После вычисления максимального потока оставшийся граф сети потока отключается, и соответствующий минимальный разрез (X, X0) определяется следующим образом: v 2 X0; для и 2 Nv — {v}, если оно является мостовым множеством в Fv и щ может быть достигнуто при помощи поиска в глубину по оставшемуся графу из s, то и 2 X; в противном случае u 2 X0. | |||
Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в Nv - {v}, что позволит включить вершины u с l(u) = p в вычисление разреза, и найти K-допустимый разрез с высотой p+1 аналогичным образом. | |||
Дополняющий путь вычисляется за время, линейное относительно количества ребер, и для каждого вычисления разреза существует не более K дополнений. Применяя алгоритм к каждой вершине в топологическом порядке, получим | |||
Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn). | |||
Разрез, найденный алгоритмом, имеет другое свойство: | |||
Лемма 5. Разрез (X, X0), вычисленный вышеописанным образом, представляет собой уникальный минимальный разрез максимального объема; более того, если (Y, Y0) – еще один минимальный разрез, то Y0 С X0. | |||
Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X; X0) < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X0) за счет коллапсирования всех вершин из X0, а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым. | |||
Построение K-покрытия | |||
После того как K-допустимые разрезы минимальной высоты были найдены для всех вершин, каждой вершине оказывается сопоставлен K-допустимый конус Cv, определяемый ее разрезом, имеющим минимальную глубину. После этого построение K-покрытия NM = (VM, EM) является тривиальным. Во-первых, в VM включаются все вершины, являющиеся первичными выходами. Затем для любого конуса Cv 2 VM конус Cu для каждой не являющейся первичным входом вершины u 2 input(v) также включается в VM, равно как и каждая являющаяся первичным входом вершина u 2 input(v). Точно так же hCu; Cvi 2 EM для каждой не являющейся первичным входом вершины u 2 input(Cv); hu; Cvi 2 EM для каждой являющейся первичным входом вершины u 2 input(Cv). | |||
Лемма 6. K-покрытие, построенное вышеописанным образом, является оптимальным по глубине. | |||
Эта процедура линейна по времени, следовательно: | |||
Теорема 3. Задача оптимального по глубине технологического отображения для ППВМ на основе таблиц K-LUT на булеву сеть с n вершинами и m ребрами может быть решена за время O(Kmn). | |||
== Применение == | |||