4551
правка
Автоматическая генерация дерева поиска: различия между версиями
Перейти к навигации
Перейти к поиску
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 16:31, 5 мая 2012
, 5 мая 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 38: | Строка 38: | ||
Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные дуги обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска <math>O(2.27^k) \, </math> | Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные дуги обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска <math>O(2.27^k) \, </math> | ||
[[Файл:ASTG tab1.png]] | |||
Автоматическая генерация дерева поиска, таблица 1 | Автоматическая генерация дерева поиска, таблица 1 | ||
Сводные данные по размерам деревьев поиска, в которых автоматизация привела к улучшению. Сравниваются тривиальные, известные и новые алгоритмы. Под «известным» понимается лучшее из ранее опубликованных деревьев поиска, созданных вручную. Здесь m обозначает количество дизъюнктов, а l – длину формулы | |||
== Применение == | == Применение == | ||