Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Посмотрите ещё более внимательно... 04.03.05 22:14 Число просмотров: 3520
Автор: Партизан Статус: Незарегистрированный пользователь
Отредактировано 06.03.05 17:54 Количество правок: 1
|
>>> Потом смотрим основную теорему №5. Там сказано, что число
>>> шагов алгоритма не может превышать m, число строк таблицы.
>> Не число шагов алгоритма, а число вариантов анализа
>> таблицы.
> Ну это я так для краткости обозвал. Ну хорошо, пусть будет
> число вариантов анализа таблицы.
> Но сложность каждого варианта нигде не раскрыта!
Каждый вариант - это фактически прохождение какой-либо ветви дерева
расщепления формулы.
Если ветвь дерева "закрылась" (исход 1 у Тельпиза),
т. е. не получили ни пустого дизъюнкта (нулевой вектор у Тельпиза),
ни выполняющего набора, то переходим к следующему варианту анализа.
При каждом варианте анализа до получения результата "невыполнимость"
или до получения первого выполняющего набора в резолюционном выводе
участвует какой-нибудь дополнительный дизъюнкт, который в предыдущих
вариантах (в предыдущих ветвях дерева) не участвовал, поэтому
количество вариантов анализа (количество пройденных ветвей в дереве
расщепления) ограничено не 2^n, а количеством дизъюнктов m.
Каждый анализ состоит из нескольких шагов. На каждом шаге анализируется
какая-либо переменная (столбец в таблице).
Всего переменных (столбцов) - n, значит количество шагов - не больше n.
Таким образом, при каждом анализе таблица просматривается не более
одного раза, сложность - не больше O(m*n), или если использовать разреженную
таблицу - O(l), где l - общее число вхождений всех переменных в формулу
(общее число непустых ячеек в таблице).
>>> Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n
>>> - число переменных.
>> Решаем задачу ВЫП, её размеры - это не n.
> Ладно, сознаюсь. Я не знаю как измеряются размеры задачи
> ВЫП, расскажите если не сложно.
А тут не надо ни чего знать, или Вы КНФ никогда не видели? Какие у КНФ размеры?
Количество переменных - n,
количество дизъюнктов (клозов) - m,
общее число l вхождений всех переменных в формулу.
Для k-ВЫП ещё: k - максимальный размер дизъюнкта.
l в общем-то определяет длину всей формулы F, поэтому можно сказать,
что l - определяет размер формулы КНФ в целом.
Ясно, что l<=m*n, а конкретно для задачи k-ВЫП l<=m*k.
Если l сравнимо с m*n, т. е. близко к m*n (не знаю, бывает ли такое в
реальности), тогда можно хранить формулу КНФ в памяти в виде 2-мерной таблицы
размерами m*n, как это сделано у Тельпиза. Тогда и оценивать сложность можно
относительно произведения m*n.
Если же l много меньше m*n, тогда разумнее хранить КНФ в разреженной таблице,
её размеры как раз и определяются количеством непустых ячеек, т. е. числом l.
К тому же разреженная таблица и ускорит обработку - не надо будет
просматривать пустые ячейки, т. е. и время однократного прочтения всей
таблицы тоже будет пропорционально числу l.
> Но мне всетаки казалось что
> количество переменных - определяющий фактор. Т.к. верхняя
> граница скорости выполнения как раз и задается полным
> перебором 2^n вариантов.
Угу. Но сложность алгоритма нужно оценивать относительно размеров задачи.
Известно, что для k-ВЫП случайного вида некий "фазовый переход", в смысле
есть некое число, зависящее от k, что если m/n заметно превышает это число,
то вероятность того, что КНФ выполнима, резко падает, стремится к нулю.
Если m/n меньше этого числа, то, наоборот, скорее всего КНФ выполнима.
Для 3-ВЫП, если не ошибаюсь фазовый переход происходит при отношении m/n
равном чуть больше 4 (4.2 или 4.25 - не помню).
Т. е. реально m имеет размеры сравнимые с n. И если сложность решения
относительно n полиномиальна, тогда и относительно l будет полиномиальна,
если относительно n - экспоненциальна, тогда и относительно l будет
экспоненциальна.
Если, как Вы говорите, m экпоненциально зависит от n (что почти невероятно в
реальных задачах), тогда оценивать сложность задачи ВЫП относительно n -
неразумно. Да и сведение других NP-полных задач размера n к задаче ВЫП не
будет полиномиальным, что не есть правда.
Обычно, оценивают сложность решения ВЫП относительно m или l.
>> На каждом шаге анализа таблицы просматриваем один
>> столбец.
>> Следовательно на одном шаге просматривается не более m
>> ячеек таблицы. Для каждого варианта столбцы
>> просматриваются
>> последовательно, двигаясь в левую сторону,
>> следовательно
>> при каждом варианте анализа просматривается не больше
>> n столбцов и не больше m*n ячеек, то есть таблица
>> просматривается при каждом варианте не более одного
>> раза.
>> До получения ответа на вопрос о выполнимости таблицы
>> просматриваем её не более m раз.
> Ладно. Допустим на каждом шаге мы просматриваем один
> столбец.
> Тогда получается, что для каждого "вывода" нужно
> просмотреть всю таблицу.
Не "вывод", "вариант анализа" у Тельпиза, фактически - это прохождение
одной ветви дерева расщепления.
> Вывод - это выход на вариант 1-3. НО! выход на вариант 1 -
> это еще не конец "анализа"
У Тельпиза как раз выходом на исходы 1 или 2-3 и заканчивается
"текущий вариант анализа".
> таблицы, после получения варианта 1, мы должны снова
> проанализировать часть таблицы,
Пусть даже всю таблицу - O(l). Общее число этих вариантов анализа будет не
больше количества дизъюнктов m.
> а потом снова и снова. Нигде не показана сложность
> вытекающая из этой рекурсии.
См. теорему 5. Сложность O(m) * сложность одного варианта анализа, общая
сложность до находения первого выполняющего набора - O(m*l) или
O(m*m*n), если таблица неразрежена (т. е. хранятся и обрабатываются пустые
ячейки).
> А если внимательно присмотреться к приводимым примером
> легко можно заметить, что
> чаще всего происходит ПОЛНЫЙ перебор некоторого
> подмножества переменных, и только
> часть переменных отсеивается в дальнейшем.
Что Вы называете ПОЛНЫМ перебором некоторого подмножества переменных?
O(n) - это не экспоненциальная сложность. ;-)
Экспоненциальная сложность - это, например, ПОЛНЫЙ перебор
_всех_наборов_значений_ переменных O(2^n)
или подмножества переменных, в случае, если это
подмножество имеет размеры O(n).
Составление третьей служебной строки в процессе одного анализа
таблицы - это и есть фактически составление набора значений переменных:
на каждом шаге запись номера исхода 2, 4, T или 3, 5, T* в третью служебную
строку означает, что соответствующей переменной присваивается значение
1 или 0 (см. внизу страницы 14 ) и исключаются из рассмотрения
выполненные (принявшие значение =1) дизъюнкты (строки таблицы),
а в оставшихся вычёркивается эта переменная. Кроме исхода 6б - в этом случае
соответствующая переменная в набор не входит (т. е. получается неполный набор)
Причём расщепление формулы ("ветвление", "разбиение таблицы на две подтаблицы"
у Тельпиза) осуществляется только при выходе на исход 6б, а при исходах 4 и 5, 6а
ветвления не происходит.
Посмотрите ещё более внимательно: где-нибудь количество вариантов анализа,
а значит и число рассмотренных наборов превышает m?
Чтобы доказать, что Тельпиз неправ, достаточно придумать пример простейшей
таблицы, на которой его алгоритм будет давать больше, чем m вариантов анализа,
или будет зацикливаться...
Кстати, вот ссылка на работу (институт Стеклова) 2001 года , где описаны и
проанализированы на русском языке некоторые алгоритмы выполнимости:
http://cs.roosevelt.edu/~dantsin/ps/DHIV01b.ps
|
|
|
подробно о проекте
Анализ криптографических сетевых...
