4824
правки
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
м
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 06:43, 25 апреля 2025
, 25 апрель→См. также
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→См. также) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 90: | Строка 90: | ||
'''Теорема 3. Задача MAX TRIANGLE может быть решена за время <math>O(W \; n^{\omega} \; log \; n)</math> для графов с весами из <math>\Z [-W, W]</math>.''' | '''Теорема 3. Задача MAX TRIANGLE может быть решена за время <math>O(W \; n^{\omega} \; log \; n)</math> для графов с весами из <math>\Z [-W, W]</math>.''' | ||
Доказательство. Сначала | Доказательство. Сначала продемонстрируем, что весовая функция на вершинах и ребрах может быть преобразована в эквивалентную весовую функцию с весами только на ребрах. Пусть w – весовая функция над G. Переопределим веса следующим образом: | ||
<math>w'( \{ u, v \}) = \frac{w(u) + w(v)}{2} + w( \{u, v \}), w'(u) = 0</math>. | <math>w'( \{ u, v \}) = \frac{w(u) + w(v)}{2} + w( \{u, v \}), w'(u) = 0</math>. | ||
| Строка 97: | Строка 97: | ||
Следующим шагом будет использование быстрого произведения расстояний для поиска треугольника с максимальным весом в реберно-взвешенном графе с n вершинами. | Следующим шагом будет использование быстрого произведения расстояний для поиска треугольника с максимальным весом в реберно-взвешенном графе с n вершинами. Представим множество вершин графа G в виде множества {1, ..., n}. Определим A как матрицу размера n x n, такую, что A[i, j] = - w({i, j}), если существует ребро {i, j}, и A[i, j] = <math>\infty</math> в противном случае. Утверждение заключается в том, что треугольник с вершиной i и с весом не менее K существует тогда и только тогда, когда <math>(A \otimes_d A \otimes_d A) [i, j] \le -K</math>. Это объясняется тем, что данное неравенство выполняется тогда и только тогда, когда существуют отличные друг от друга j и k, такие, что {i, j}, {j, k}, {k, i} – ребра, и | ||
A[i, j] + A[j, k] + A[k, i] <math>\le</math> -K, то есть w({i, j}) + w({j, k}) + w({k, i}) <math>\ge</math> K. | |||
Поэтому, найдя i, такой, что <math>(A \otimes_d | |||
Поэтому, найдя i, такой, что <math>(A \otimes_d A \otimes_d A) [i, j]</math> минимизировано, мы получим вершину i, содержащуюся в максимальном треугольнике. Для получения фактического треугольника следует проверить все m ребер {j, k} на предмет того, является ли {i, j, k} треугольником. □ | |||
| Строка 108: | Строка 110: | ||
== Применение == | == Применение == | ||
Модифицировав | Модифицировав построение графа, можно решать другие задачи за время <math>O(1,732^n)</math>, такие как MAX CUT ([[Максимальный разрез]]), MINIMUM BISECTION ([[Минимальная бисекция]]) и SPARSEST CUT ([[Самое неплотное сечение]]). В целом, любая задача оптимизации с ограничениями, в которой каждое ограничение имеет не более двух переменных, может быть решена быстрее с помощью описанного выше подхода. Более подробную информацию можно найти в работе [17] и в обзоре Вёгингера [19]. Схожая с вышеприведенным алгоритмом техника была также использована Дорном [6] с целью ускорения динамического программирования для некоторых задач на планарных графах (и вообще на графах с ограниченной путевой шириной). | ||
== Открытые вопросы == | == Открытые вопросы == | ||
• Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует <math>\Theta(2^{2n/3})</math>. Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем <math>O(1,99^n)</math>, использующий только полиномиальный объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем <math>n^{k | • Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует <math>\Theta(2^{2n/3})</math>. Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем <math>O(1,99^n)</math>, использующий только ''полиномиальный'' объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем <math>n^{k - \delta}</math> для некоторых <math>\delta > 0</math> и <math>k \ge 3</math>. | ||
• Хотелось бы найти алгоритм для MAX 2-SAT | • Хотелось бы найти алгоритм для MAX 2-SAT с временем выполнения менее <math>2^n</math>, не требующий быстрого умножения матриц. Алгоритмы быстрого умножения матриц имеют печальную репутацию непрактичных. | ||
• Следует обобщить вышеприведенный алгоритм для задачи MAX k-SAT, где k – любое целое положительное число. В текущей формулировке требуется эффективный алгоритм для нахождения малой гиперклики в гиперграфе. Однако для этой задачи неизвестны какие-либо результаты общего вида. Есть гипотеза, что для всех <math>k \ge 2</math> задача MAX k-SAT решается за время <math>\tilde{O}(2^{n(1 - \frac{1}{k + 1})})</math>, исходя из предположения, что умножение матриц выполняется за время <math>n^{2+o(1)}</math> [17]. | • Следует обобщить вышеприведенный алгоритм для задачи MAX k-SAT, где k – любое целое положительное число. В текущей формулировке требуется эффективный алгоритм для нахождения малой гиперклики в гиперграфе. Однако для этой задачи неизвестны какие-либо результаты общего вида. Есть гипотеза, что для всех <math>k \ge 2</math> задача MAX k-SAT решается за время <math>\tilde{O}(2^{n(1 - \frac{1}{k + 1})})</math>, исходя из предположения, что умножение матриц выполняется за время <math>n^{2+o(1)}</math> [17]. | ||
| Строка 121: | Строка 123: | ||
* [[Максимальный разрез]] | * [[Максимальный разрез]] | ||
* [[Минимальная бисекция]] | * [[Минимальная бисекция]] | ||
* [[ | * [[Самый неплотный разрез]] | ||
== Литература == | == Литература == | ||