Алгоритм перечисления

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

Формальные определения

Проблема с перечислением $P$ определяется как отношение $R$ над строками произвольного алфавита $\Sigma$:

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}$

Алгоритм решает $P$ если для каждого входа $x$ алгоритм создает (возможно, бесконечную) последовательность $y$ такой, что $y$ не имеет дубликатов и $z\in y$ тогда и только тогда, когда $(x,z)\in R$. Алгоритм должен остановиться, если последовательность $y$ конечно.

Общие классы сложности

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

Очень общий такой класс — EnumP . класс задач, для которых правильность возможного результата можно проверить за полиномиальное время на входе и выходе. Формально для такой проблемы должен существовать алгоритм A, который принимает в качестве входных данных входную задачу x , выходной сигнал-кандидат y и решает проблему принятия решения о том, является ли y правильным выходным сигналом для входного x , за полиномиальное время по x и й . Например, этот класс содержит все задачи, которые сводятся к перечислению свидетелей проблемы в классе NP .

Другие определенные классы включают следующие. В случае проблем, которые также есть в EnumP , эти проблемы упорядочены от наименее к наиболее конкретным:

• Выходной полином — класс задач, полный результат которых можно вычислить за полиномиальное время.
• Инкрементальное полиномиальное время — класс задач, в которых для всех i -й результат i может быть получен за полиномиальное время по входному размеру и по числу i .
• Полиномиальная задержка — класс задач, в которых задержка между двумя последовательными выходными данными является полиномиальной на входе (и не зависит от выхода).
• Сильно полиномиальная задержка — класс задач, в которых задержка перед каждым выходом полиномиальна по размеру этого конкретного выхода (и не зависит от входа или других выходов). Обычно предполагается, что предварительная обработка является полиномиальной.
• Постоянная задержка — класс задач, в которых задержка перед каждым выходом постоянна, т. е. не зависит от ввода и вывода. Обычно предполагается, что фаза предварительной обработки имеет полиномиальный входной сигнал.

Общие методы

• Поиск с возвратом . Самый простой способ перечислить все решения — систематически исследовать пространство возможных результатов ( разделяя его на каждом последовательном шаге). Однако выполнение этого может не дать хороших гарантий относительно задержки, т. е. алгоритм обратного отслеживания может потратить много времени на исследование частей пространства возможных результатов, которые не приводят к полному решению.
• Поиск с фонариком : этот метод улучшает возврат назад, исследуя пространство всех возможных решений, но решая на каждом этапе проблему того, можно ли расширить текущее частичное решение до частичного решения. Если ответ отрицательный, то алгоритм может немедленно вернуться назад и избежать потери времени, что упрощает предоставление гарантий по задержке между любыми двумя полными решениями. В частности, этот метод хорошо применим к саморедуцируемым задачам.
• Замыкание при операциях над множествами . Если мы хотим перечислить непересекающееся объединение двух множеств, то мы можем решить проблему, перечислив первый набор, а затем второй набор. Если объединение не является непересекающимся, но множества можно перечислять в отсортированном порядке , то перечисление можно выполнять параллельно для обоих наборов, устраняя дубликаты на лету. Если объединение не является непересекающимся и оба множества не отсортированы, то дубликаты можно устранить за счет более высокого использования памяти, например, с помощью хеш-таблицы . Аналогично, декартово произведение двух наборов можно эффективно пересчитать, перечислив один набор и объединив каждый результат со всеми результатами, полученными при перечислении второго шага.

Примеры задач перечисления

• Задача перечисления вершин , где нам дан многогранник, описываемый как система линейных неравенств , и мы должны перенумеровать вершины многогранника.
• Перечисление трансверсалей гиперграфа . минимальных Эта проблема связана с монотонной дуализацией и связана со многими приложениями в теории баз данных и теории графов .
• Перечисление ответов на запрос к базе данных , например, конъюнктивный запрос или запрос, выраженный в монадическом втором порядке . были описаны В теории баз данных способы перечисления конъюнктивных запросов с линейной предварительной обработкой и постоянной задержкой.
• Задача перебора максимальных клик во входном графе, например, с помощью алгоритма Брона–Кербоша.
• Перечисление всех элементов структур, таких как матроиды и гридоиды.
• Несколько задач на графах, например, перечисление независимых множеств , путей , разрезов и т. д.
• Перечисление удовлетворяющих назначений представлений булевых функций , например, булевой формулы, записанной в конъюнктивной нормальной форме или дизъюнктивной нормальной форме , двоичной диаграммы решений , такой как OBDD , или булевой схемы в ограниченных классах, изучаемых при компиляции знаний , например, NNF .

Связь с теорией вычислимости

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