4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Материал из WEGA
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 19:22, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 95: | Строка 95: | ||
• На строке 5 следует исключить <math>c_{xy} = c_{yx} \;</math>. | • На строке 5 следует исключить <math>c_{xy} = c_{yx} \;</math>. | ||
• На строке 12 следует произвольным образом включить некоторую пару <math>\{ x, y \} \subset V_2 \;</math>, которая еще не была включена, и рекурсивно | • На строке 12 следует произвольным образом включить некоторую пару <math>\{ x, y \} \subset V_2 \;</math>, которая еще не была включена, и рекурсивно повторять это действие; только если включены все пары <math>\{ x, y \} \subset V_2 \;</math>, следует вернуть значение ДА. | ||
В результате модификаций получен алгоритм решения задачи OSCM с параметром < | В результате модификаций получен алгоритм решения задачи OSCM с параметром <math>O^*(1,6182^k) \;</math>. Он составляет ядро алгоритма Джумовича и Уайтсайдза [5]. В их работе более детально обсуждаются следующие вопросы: | ||
• Как эффективно вычислить все количества пересечений cxy на этапе предварительной обработки? | • Как эффективно вычислить все количества пересечений cxy на этапе предварительной обработки? | ||
• Как интегрировать в алгоритм элементы ветвления и обрезки, полезные с практической точки зрения? | • Как интегрировать в алгоритм элементы ветвления и обрезки, полезные с практической точки зрения? | ||
• Как обобщить алгоритм для экземпляров, допускающих наличие целочисленных весов у ребер (параллельных ребер)? | • Как обобщить алгоритм для экземпляров, допускающих наличие целочисленных весов у ребер (параллельных ребер)? | ||
Дальнейшие улучшения возможны в результате более глубокого анализа локальных паттернов {x, y} | Дальнейшие улучшения возможны в результате более глубокого анализа локальных паттернов <math>\{ x, y \} \in V_2 \;</math>, таких, что <math>c_{xy} c_{yx} \le 2 \;</math>. Таким образом было показано: | ||
'''Теорема 7. Задачу односторонней минимизации пересечений можно решить за время <math>O^*(l,4656^k) \;</math>.''' | |||
Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3. | Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3. | ||
