4430
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 43: | Строка 43: | ||
== Основные результаты == | == Основные результаты == | ||
Для задач, для которых не предполагается существования полиномиальных алгоритмов, очень желательно найти точные алгоритмы с экспоненциальным временем | Для задач, для которых не предполагается существования полиномиальных алгоритмов, очень желательно найти точные алгоритмы с экспоненциальным временем выполнения. | ||
Строка 65: | Строка 65: | ||
Нагамочи предложил алгоритм | Нагамочи предложил аппроксимационный алгоритм с коэффициентом меньше 1,4664. | ||
Далее, для любой вершины <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>\{ u, v \} \;</math> верно <math>c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали: | Далее, для любой вершины <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>\{ u, v \} \;</math> верно <math>c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали: | ||
Строка 91: | Строка 91: | ||
Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в {x, y} | Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в <math>\{ x, y \} \subset V_2 \;</math>, если <math>c_{xy} = c_{yx} \;</math>. Это позволяет внести две модификации в Алгоритм 1: | ||
• На строке 5 следует исключить <math>c_{xy} = c_{yx} \;</math>. | • На строке 5 следует исключить равенство <math>c_{xy} = c_{yx} \;</math>. | ||
• На строке 12 следует произвольным образом включить некоторую пару <math>\{ x, y \} \subset V_2 \;</math>, которая еще не была включена, и рекурсивно повторять это действие; только если включены все пары <math>\{ x, y \} \subset V_2 \;</math>, следует вернуть значение ДА. | • На строке 12 следует произвольным образом включить некоторую пару <math>\{ x, y \} \subset V_2 \;</math>, которая еще не была включена, и рекурсивно повторять это действие; только если включены все пары <math>\{ x, y \} \subset V_2 \;</math>, следует вернуть значение ДА. | ||
Строка 100: | Строка 100: | ||
В результате модификаций получен алгоритм решения задачи OSCM с параметром <math>O^*(1,6182^k) \;</math>. Он составляет ядро алгоритма Джумовича и Уайтсайдза [5]. В их работе более детально обсуждаются следующие вопросы: | В результате модификаций получен алгоритм решения задачи OSCM с параметром <math>O^*(1,6182^k) \;</math>. Он составляет ядро алгоритма Джумовича и Уайтсайдза [5]. В их работе более детально обсуждаются следующие вопросы: | ||
• Как эффективно вычислить все количества пересечений | • Как эффективно вычислить все количества пересечений <math>c_{xy} \;</math> на этапе предварительной обработки? | ||
• Как интегрировать в алгоритм элементы ветвления и обрезки, полезные с практической точки зрения? | • Как интегрировать в алгоритм элементы ветвления и обрезки, полезные с практической точки зрения? | ||
Строка 110: | Строка 110: | ||
'''Теорема 7. Задачу односторонней минимизации пересечений можно решить за время <math>O^*( | '''Теорема 7. Задачу односторонней минимизации пересечений можно решить за время <math>O^*(1,4656^k) \;</math>.''' | ||
Возможный вариант | Возможный вариант выполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3. | ||
Строка 134: | Строка 134: | ||
'''Варианты этой задачи и родственные ей проблемы''' широко рассматривались в литературе. | '''Варианты этой задачи и родственные ей проблемы''' широко рассматривались в литературе. | ||
1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем | 1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем выполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>. | ||
2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10]. | 2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10]. | ||
Строка 141: | Строка 141: | ||
== Применение == | == Применение == | ||
Помимо рассмотрения вопроса графического построения двудольных графов как задачи, интересной самой по себе ( | Помимо рассмотрения вопроса графического построения двудольных графов как задачи, интересной самой по себе (например, для качественного изображения диаграмм отношений), этот вопрос естественным образом возникает при применении так называемого подхода Судзиямы к построению иерархических графов [12]. Этот исключительно популярный подход решает задачу укладки иерархического графа в три этапа: (1) удаление циклов, (2) присваивание вершин уровням, (3) присваивание вершин уровням. Последний этап обычно реализуется посредством алгоритма с заметающей прямой, в процессе работы решающего несколько экземпляров задачи односторонней минимизации пересечений. Третий вариант задачи, упомянутый выше, находит множество важных вариантов применения в вычислительной биологии. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Как и для всех алгоритмов с экспоненциальным временем | Как и для всех алгоритмов с экспоненциальным временем выполнения, оказывается непросто улучшить это время или доказать определенную нижнюю границу времени выполнения при наличии разумных теоретико-сложностных предположений. Заметим, что негласные предположения, лежащие в основе подхода параметризованных алгоритмов, в данном сценарии полностью удовлетворяются: к примеру, графическое представление с большим количеством пересечений будет неприемлемым (если такая ситуация встретится на практике, придется прибегнуть к другому способу представления информации); таким образом, можно обоснованно предполагать, что параметр действительно окажется малым. | ||
правок