4817
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 10:47, 29 марта 2025
, 29 март→Далее
Irina (обсуждение | вклад) (→Далее) |
Irina (обсуждение | вклад) (→Далее) |
||
| Строка 83: | Строка 83: | ||
На следующем шаге выберем такое число <math>x</math>, чтобы из суммы произвольных степеней <math>x</math> было легко определить наибольшую степень <math>x</math>, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум <math>A[i, k] + B[k, j]</math>. Каждый <math>C[i,j]</math> – это полином от <math>x</math> с коэффициентами из <math>\Z [0, n]</math>. Предположим, что каждый <math>C[i, j]</math> оценивается при <math>x = n + 1</math>. Тогда каждый элемент <math>C[i, j]</math> можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум <math>A[i, k] + B[k, j]</math>. | На следующем шаге выберем такое число <math>x</math>, чтобы из суммы произвольных степеней <math>x</math> было легко определить наибольшую степень <math>x</math>, встречающуюся в сумме; эта наибольшая степень сразу же дает минимум <math>A[i, k] + B[k, j]</math>. Каждый <math>C[i,j]</math> – это полином от <math>x</math> с коэффициентами из <math>\Z [0, n]</math>. Предположим, что каждый <math>C[i, j]</math> оценивается при <math>x = n + 1</math>. Тогда каждый элемент <math>C[i, j]</math> можно рассматривать как (n + 1)-арное число, а положение старшей значащей цифры этого числа дает минимум <math>A[i, k] + B[k, j]</math>. | ||
Суммируя все вышесказанное, | |||
Суммируя все вышесказанное, <math>A \otimes_d B</math> можно вычислить, построив <math>A'[i, j] = (n + 1)^{3W-A[i, j]]}, B'[i, j] = (n + 1)^{3w - B[i, j]}</math> за время O(W log n) на каждый элемент, вычисляя C = A' x B' за время <math>O(n^{\omega} \cdot (W \; log \; n))</math> (так как размеры элементов равны O(W log n)), а затем извлекая минимум из каждого элемента <math>C</math> за время <math>O(n^2 \cdot W \; log \; n)</math>. Заметим, что если минимум для элемента <math>C[i,j]</math> равен хотя бы <math>2W + 1</math>, то <math>C[i, j] = \infty</math>. □ | |||
за время O( | |||
Используя быстрый алгоритм произведения расстояний, можно решить задачу MAX TRIANGLE быстрее, чем простым перебором. Нижеследующее изложение основывается на алгоритм Итаи и Роде [ ] для выявления наличия треугольника в невзвешенном графе менее чем за n3 шагов. Результат может быть обобщен на подсчет количества k-клик для произвольного k > 3. (Для простоты изложения результат подсчета опущен. Что касается работы с k-кликами, то, к сожалению, не существуетасимптотического преимущества во времени выполнения от использования алгоритма на k-кликах вместо алгоритма на треугольниках – по крайней мере, если говорить о лучших на сегодня алгоритмах для решения этих задач). | Используя быстрый алгоритм произведения расстояний, можно решить задачу MAX TRIANGLE быстрее, чем простым перебором. Нижеследующее изложение основывается на алгоритм Итаи и Роде [ ] для выявления наличия треугольника в невзвешенном графе менее чем за n3 шагов. Результат может быть обобщен на подсчет количества k-клик для произвольного k > 3. (Для простоты изложения результат подсчета опущен. Что касается работы с k-кликами, то, к сожалению, не существуетасимптотического преимущества во времени выполнения от использования алгоритма на k-кликах вместо алгоритма на треугольниках – по крайней мере, если говорить о лучших на сегодня алгоритмах для решения этих задач). | ||