4652
правки
Автоматическая генерация дерева поиска: различия между версиями
Материал из WEGA
Автоматическая генерация дерева поиска (посмотреть исходный код)
Версия от 09:29, 5 мая 2012
, 5 мая 2012→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | Используя усовершенствованный метод поиска места для всех возможных вариантов и для различения всех ветвлений одного варианта, Грэмм и коллеги [3] разработали несколько алгоритмов поиска по дереву для задач модификации графов. | ||
[[Файл:ASTG_pic1.png]] | |||
Автоматическая генерация дерева поиска, рис. 1 | Автоматическая генерация дерева поиска, рис. 1 | ||
Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные дуги обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска O(2. | |||
Ветвление для варианта в алгоритме CLUSTER EDITING с использованием только базового ветвления на парах вершин (двойные круги) и применения правил редукции (звездочки). Неизменные дуги обозначены жирной линией, запрещенные – пунктирной. Числа около подграфов обозначают изменение размера задачи k. Вектор ветвления имеет значение (1,2,3,3,2), что соответствует размеру дерева поиска <math>O(2.27^k) \, </math> | |||
