Градиентный алгоритм — жадный алгоритм построения сравнительно короткого покрытия. На каждом шаге он выбирает строку, покрывающую максимальное число ещё не покрытых столбцов. Если несколько строк покрывают одинаковое максимальное число новых столбцов, выбирают строку с меньшим номером. Работа заканчивается, когда покрыты все
Если в каждом столбце матрицы \(M\in B^{p,s}\) не меньше γp единиц, \(0<\gamma\le1\), то длина q градиентного покрытия удовлетворяет оценке \(q\le\lceil\gamma^{-1}\ln^+(\gamma s)\rceil+\gamma^{-1}\), где \(\ln^+x=\max(\ln\) x,0). Алгоритм применяется к таблице Квайна для получения ДНФ, но не гарантирует глобальный
Что важно запомнить
- На каждом шаге выбирается строка с максимальным числом новых покрываемых столбцов.
- После t шагов доля непокрытых столбцов оценивается сверху через \((1-\gamma)^t\le e^{-\gamma t}\).
- Лемма о протыкающем множестве: все грани ранга m куба \(B^n\) можно проткнуть множеством не более \(n\cdot 2^m\)
- Для ДНФ алгоритм запускают на таблице Квайна. Выбранные строки задают выбранные простые импликанты.
Идея градиентного выбора
Полный перебор тупиковых покрытий быстро становится трудоёмким. Градиентный алгоритм вместо перечисления всех вариантов строит одно покрытие. На текущем шаге рассматривают только ещё не покрытые столбцы и выбирают строку, содержащую максимальное число единиц среди них. После выбора эти столбцы считаются
Оценка длины
Предположим, что каждый столбец исходной матрицы содержит хотя бы γp единиц. Тогда на любом промежуточном шаге среднее число ещё не покрытых столбцов, приходящееся на строку, позволяет выбрать строку, закрывающую не меньше γ-доли оставшихся столбцов. Если \(\delta_t\) — доля непокрытых столбцов после t шагов, то
\(\delta_t\le (1-\gamma)^t\le e^{-\gamma t}\).
Отсюда в курсе выводится оценка
\(q\le \lceil \gamma^{-1}\ln^+(\gamma s)\rceil+\gamma^{-1}\).
Она не говорит, что жадное покрытие кратчайшее. Это гарантированная верхняя оценка для матриц заданной плотности.
Лемма о протыкающих наборах
Множество точек куба называют протыкающим для системы граней, если оно имеет непустое пересечение с каждой гранью системы. Применяя теорему о градиентном покрытии к транспонированной матрице инцидентности, Ложкин получает: для любых m≤n в \(B^n\) существует множество мощности не более \(n\cdot 2^m\), протыкающее все грани ранга
Применение к построению ДНФ
В таблице Квайна строки — простые импликанты, а столбцы — единичные наборы функции. Градиентный выбор строк даёт набор простых импликант, покрывающий \(N_f\), то есть некоторую ДНФ функции. При необходимости после этого можно удалить избыточные выбранные члены, не увеличивая длину. Но жадность сама по себе не доказывает минимальность или кратчайшесть результата.
Пример простыми словами
Если после нескольких шагов осталось 20 непокрытых столбцов, а лучшая строка покрывает 8 из них, алгоритм выбирает именно её, даже если другая строка могла бы привести к более удачной комбинации на следующих шагах. Поэтому метод быстро уменьшает непокрытую часть, но локально лучший выбор не обязан давать глобально кратчайшее покрытие.
Частые ошибки
- Называть градиентное покрытие минимальным. Алгоритм даёт покрытие с доказанной верхней оценкой длины, но не гарантирует глобальный оптимум.
- Считать γ долей единиц во всей матрице. Условие теоремы относится к каждому столбцу отдельно.
- Путать ранг грани m с её размерностью n−m в лемме о протыкающих наборах.
