4511
правок
K-КНФ-алгоритмы на основе поиска с возвратом: различия между версиями
Материал из WEGA
K-КНФ-алгоритмы на основе поиска с возвратом (посмотреть исходный код)
Версия от 11:24, 25 февраля 2018
, 25 февраля 2018→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 109: | Строка 109: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Разрыв между границами для общего случая и для случая уникальной выполнимости при k | Разрыв между границами для общего случая и для случая уникальной выполнимости при <math>k \in \{ 3, 4 \}</math> связан со слабостью анализа; было высказано предположение, что асимптотические границы для случая уникальной выполнимости выполняются в общем случае для всех k. Если это предположение верно, из него следует, что '''ResolveSat''' оказывается быстрее любого существующего алгоритма и в случае k = 3. | ||
| Строка 120: | Строка 120: | ||
Таблица 1 | Таблица 1 | ||
В таблице представлен показатель c, используемый в значении границы 2c"~oW для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [ | В таблице представлен показатель c, используемый в значении границы 2c"~oW для уникального и общего случаев задачи k-КНФ, решаемой при помощи алгоритма ResolveSat, границы для k-КНФ и алгоритма Шонинга [12], его улучшенной версии для 3-КНФ [1, 5, 11] и гибридной версии из работы [6] | ||
