4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Материал из WEGA
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 19:25, 30 марта 2016
, 30 марта 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 114: | Строка 114: | ||
Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3. | Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3. | ||
| Строка 149: | Строка 137: | ||
Рис. 3. Оптимальное решение для экземпляра задачи | Рис. 3. Оптимальное решение для экземпляра задачи | ||
'''Варианты этой задачи и родственные ей проблемы''' широко рассматривались в литературе. | |||
1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем исполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>. | |||
2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10]. | |||
3. Можно рассмотреть другие дополнительные ограничения на графическое построение или допустимые отношения порядка; так, в [8] были рассмотрены параметризованные алгоритмы для задачи двухуровневого присваивания, в которой допустимые отношения порядка были ограничены бинарными деревьями. | |||
== Применение == | |||
Помимо рассмотрения вопроса графического построения двудольных графов как задачи, интересной самой по себе (т.е., например, для качественного изображения диаграмм отношений), этот вопрос естественным образом возникает при применении так называемого подхода Судзиямы к построению иерархических графов [12]. Этот исключительно популярный подход решает задачу укладки иерархического графа в три этапа: (1) удаление циклов, (2) присваивание вершин уровням, (3) присваивание вершин уровням. Последний этап обычно реализуется посредством алгоритма с заметающей прямой, в процессе работы решающего несколько экземпляров задачи односторонней минимизации пересечений. Третий вариант задачи, упомянутый выше, находит множество важных вариантов применения в вычислительной биологии. | |||
== Открытые вопросы == | == Открытые вопросы == | ||
