Создать тему  Создать ответ 
Алгоритм Шёнинга
07-11-2012, 19:55    
Сообщение: #1
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

Алгоритм Шёнинга
Прочитал недавно статью 1999го года об алгоритме для проблемы поиска набора переменных, при котором данная 3-КНФ (а также вообще k-КНФ) истинна: homepages.cwi.nl/~rdewolf/schoning99.pdf
Возникли такие мысли: 1) действительно ли наиболее целесообразно делать именно 3n шагов? 2) Не сделает ли алгоритм более эффективным генерация не рандомных значений переменных, независимых от предыдущих попыток, а какой-либо более сложный подход? Например, выбор нескольких наборов значений переменных так, чтобы искомый набор (решение) был гарантированно близок по крайней мере к одному из них на расстояние Хэмминга, не превосходящее n/t, где t - некая специально подобранная константа.
Сейчас получены несколько лучшие асимптотики, чем в описанном алгоритме, но его относительная простота (и простота доказательства его асимптотики) делает поиск усовершенствований не таким сложным.
Найти все сообщения
Цитировать это сообщение
07-11-2012, 22:31    
Сообщение: #2
Quasus

Гоф-фурьер
Сообщений: 625
Зарегистрирован: 17.06.12

RE: Чем бы нам заняться?
Прочитал. Осмысливаю.
Найти все сообщения
Цитировать это сообщение
08-11-2012, 21:01    
Сообщение: #3
Quasus

Гоф-фурьер
Сообщений: 625
Зарегистрирован: 17.06.12

RE: Чем бы нам заняться?
Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через при . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.
Найти все сообщения
Цитировать это сообщение
09-11-2012, 22:54    
Сообщение: #4
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Чем бы нам заняться?
(08-11-2012 21:01)Quasus писал(а):  Не вникая пока в выкладки (с. 411 — мне не очень понятно, какие там используются эквивалентности и пр.), могу сказать, что не понимаю, как это вообще работает. Матожидание приращения расстояния Хэмминга при одном «флипе» оценивается через при . Если мы всё равно уходим от искомого решения, зачем вообще эти 3n итераций, и почему сразу не выбирать новую точку? Какой-то фокус.
Там получается, что вероятность прийти к решению (если конечно оно существует) за те 3n итераций не менее чем , где j - расстояние Хэмминга от сгенерённого набора переменных до ответа, и этого оказывается достаточно, чтобы побить "наивный" алгоритм по производительности.
Найти все сообщения
Цитировать это сообщение
09-11-2012, 23:00    
Сообщение: #5
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Чем бы нам заняться?
Идея подобного рода алгоритмов основывается на том, что если есть способ получить ответ за одно испытание с вероятностью не менее 1/k, то если провести k таких независимых испытаний, то вероятность, что ответ не будет получен, будет всего лишь примерно 1/e. Если повторить их C*k раз, где C - соотв. константа, можно понизить вероятность неудачи ниже нужного уровня.
Найти все сообщения
Цитировать это сообщение
09-11-2012, 23:51    
Сообщение: #6
Quasus

Гоф-фурьер
Сообщений: 625
Зарегистрирован: 17.06.12

RE: Алгоритм Шёнинга
Видимо, в первую очередь я не понимаю, какой «функционал стоимости» оптимизируется.
Найти все сообщения
Цитировать это сообщение
10-11-2012, 00:14    
Сообщение: #7
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Алгоритм Шёнинга
Оптимизуется зависимость времени поиска решения (в данном случае - времени, за которое алгоритм найдёт решение с вероятностью, близкой к единице) от числа переменных в КНФ при максимальном размере дизъюнкций, обозначенном через k. Понятно, что на поиск невыполненной дизъюнкции тоже будет каждый раз уходить время, но в данном случае им можно пренебречь, поскольку сложность всё равно будет экспоненциальная. Цель построения алгоритмов для задачи о выполнимости k-КНФ (k >= 3) - максимально приблизить к 1 основание степени в асимпотической оценке (возможно, существуют и субэкспоненциальные алгоритмы, или даже полиномиальные, но пока таких не удалось найти). Для задачи о выполнимости 2-КНФ существует простой полиномиальный алгоритм - O(N2).
Найти все сообщения
Цитировать это сообщение
10-11-2012, 00:17    
Сообщение: #8
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Алгоритм Шёнинга
Задача о выполнимости 3-КНФ - NP-полная задача, поэтому весьма вероятно, что полиномиального алгоритма для неё не существует.
Найти все сообщения
Цитировать это сообщение
10-11-2012, 01:38    
Сообщение: #9
Quasus

Гоф-фурьер
Сообщений: 625
Зарегистрирован: 17.06.12

RE: Алгоритм Шёнинга
То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая). А «флипанье» значит дорого?
Найти все сообщения
Цитировать это сообщение
10-11-2012, 10:20    
Сообщение: #10
Галл

Cōnsul
Сообщений: 1399
Зарегистрирован: 21.09.12

RE: Алгоритм Шёнинга
(10-11-2012 01:38)Quasus писал(а):  То есть начальное приближение — «дорого», нахождение невыполненной дизъюнкции — «дёшево» (a fortiori проверка тоже дешёвая)
Сам блок из 3n итераций дёшев, так как работает за полиномиальное от n время. Но его нужно повторять экспоненциальное число раз, чтобы достичь близкой к 1 вероятности нахождения ответа. От полиномиального множителя можно избавиться, промажорировав его через , где эпсилон - положительное число, сколь угодно близкое к нулю. Сложность для 3-КНФ будет тогда выглядеть как .
Найти все сообщения
Цитировать это сообщение
Создать ответ 


Переход:


Пользователи просматривают эту тему: 1 Гость(ей)