4430
правок
Остовное дерево с максимальным количеством листьев: различия между версиями
Материал из WEGA
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 13:58, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 6 промежуточных версий этого же участника) | |||
| Строка 43: | Строка 43: | ||
(в) Градиенты и правила преобразования для эвристик локального поиска. | (в) Градиенты и правила преобразования для эвристик локального поиска. | ||
(г) | (г) Аппроксимационные алгоритмы с полиномиальным временем выполнения и границы эффективности, доказанные систематическим образом. | ||
(д) Структура, используемая для решения других задач. | (д) Структура, используемая для решения других задач. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 53: | Строка 54: | ||
'''Цель (а): FPT-алгоритмы''' | '''Цель (а): FPT-алгоритмы''' | ||
Цель заключается в нахождении правил предварительной обработки (кернелизации) с полиномиальным временем выполнения, где g(k) насколько возможно мало. Это будет важно впоследствии в контексте цели (б). | |||
| Строка 61: | Строка 62: | ||
Если перефразировать задачу в терминах | Если перефразировать задачу в терминах теории структур, важнейший вопрос будет звучать следующим образом: какова структура графов, не имеющих подграфа с k листьями? Результат Клейтмана и Веста из теории графов показывает, что граф с минимальной степенью не менее 3, не включающий подграф с k листьями, имеет не более 4(k - 3) вершин. На рис. 1 показано, что это лучший возможный результат для данной гипотезы. Однако исследование структуры при помощи экстремальных методов выявляет необходимость в применении правила редукции, показанного на рис. 2. Примерно двадцати различных правил редукции с полиномиальным временем выполнения (некоторые из них являются намного более сложными и «глобальными» по своей структуре, чем приведенное для примера простое локальное правило редукции) будет достаточно для кернелизации графа с минимальной степенью 2, имеющего не более 3,5k вершин. | ||
| Строка 69: | Строка 70: | ||
В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или | В общем случае экземпляр параметризованной задачи состоит из пары (x, k) и «границы», которая вычисляется посредством фиксации x и изменения k с последующим определением, какой ответ имеет [[задача разрешимости]] – «да» или «нет». Представляет интерес величина границы при редукции x. Типичная граничная лемма выглядит следующим образом. | ||
'''Лемма 2.''' Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда <math>|G| \le ck \;</math> (где c – небольшая константа, значение которой будет вычислено в результате | '''Лемма 2.''' Пусть (G, k) – экземпляр задачи построения остовного дерева с максимальным количеством листьев после редукции, для которого (G, k) является «да-экземпляром», а (G, k + 1) – «нет-экземпляром». Тогда <math>|G| \le ck \;</math> (где c – небольшая константа, значение которой будет вычислено в результате исследования). | ||
Доказательство граничной леммы выполняется при помощи минимального контрпримера. Контрпримером будет служить граф, такой, что (1) (G, k) – экземпляр задачи ОДМЛ после редукции; (2) (G, k) является «да-экземпляром»; (3) (G, k + 1) является «нет-экземпляром»; (4) |G| | Доказательство граничной леммы выполняется при помощи минимального контрпримера. Контрпримером будет служить граф, такой, что (1) (G, k) – экземпляр задачи ОДМЛ после редукции; (2) (G, k) является «да-экземпляром»; (3) (G, k + 1) является «нет-экземпляром»; (4) |G| > ck. | ||
Доказательство граничной леммы будет производиться последовательным образом. Изначально неизвестно, при каком значении границы будет достигнут успех, а также точно неизвестно, что подразумевается под редукцией. В ходе доказательства эти аспекты станут ясны. По мере раскрытия аргументов особенности структуры подскажут формулировки новых правил редукции. При доказательстве граничной леммы необходимо будет принимать следующие стратегические решения: | Доказательство граничной леммы будет производиться последовательным образом. Изначально неизвестно, при каком значении границы будет достигнут успех, а также точно неизвестно, что подразумевается под ''редукцией''. В ходе попытки доказательства эти аспекты станут ясны. По мере раскрытия аргументов особенности структуры подскажут формулировки новых правил редукции. При доказательстве граничной леммы необходимо будет принимать следующие стратегические решения: | ||
(1) Определение полярности границы и формулировка граничной леммы. | (1) Определение полярности границы и формулировка граничной леммы. | ||
| Строка 88: | Строка 89: | ||
(4) Разработка серии утверждений по поводу структуры, описывающих ситуацию на границе. | (4) Разработка серии утверждений по поводу структуры, описывающих ситуацию на границе. | ||
(5) Определение правил редукции, выполняющихся за полиномиальное время над релевантными | (5) Определение правил редукции, выполняющихся за полиномиальное время над релевантными структурными ситуациями на границе. | ||
(6) По мере уточнения структуры на границе – заполнение неизвестных компонентов границы кернелизации. | (6) По мере уточнения структуры на границе – заполнение неизвестных компонентов границы кернелизации. | ||
Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из | Общая структура аргумента вычисляется при помощи минимального контрпримера согласно приоритетам, заданным в результате выбора (3), который обычно ссылается на выбор (2). Доказательство развивается посредством серии небольших шагов, состоящих из утверждений по поводу структуры, которые в сумме ведут к получению детальной структурной картины на «границе» и, следовательно, позволяют определить границу размера G, которая и представляет собой заключение леммы. Полное доказательство объединяет серию утверждений по поводу дерева-свидетеля, различных множеств вершин и индуктивных приоритетов и формулирует основное неравенство, на основе которого производится доказательство по индукции, и ядро задачи размера 3,5k. | ||
'''Цель (б): предварительная обработка с полиномиальным временем выполнения и подпрограммы редукции данных''' | '''Цель (б): предварительная обработка с полиномиальным временем выполнения и подпрограммы редукции данных''' | ||
Ниже приводится пример таблицы, используемой для отслеживания каждого возможного состояния границы для возможного решения. Можно привести примеры, демонстрирующие исключительно успешное каскадное применение правил редукции данных к реальным распределениям данных и описывающие разнообразие математических феноменов, относящихся к правилам редукции. Например, некоторые правила редукции – такие как правило разложения на составляющие Клейтмана-Веста для задачи ОДМЛ (рис. 2) – имеют фиксированный «размер границы» (в данном случае равный 2), тогда как правила редукции типа «корона» не имеют такового. | Ниже приводится пример таблицы, используемой для отслеживания каждого возможного состояния границы для возможного решения. Можно привести примеры, демонстрирующие исключительно успешное каскадное применение правил редукции данных к реальным распределениям данных и описывающие разнообразие математических феноменов, относящихся к правилам редукции. Например, некоторые правила редукции – такие как ''правило разложения на составляющие Клейтмана-Веста'' для задачи ОДМЛ (рис. 2) – имеют фиксированный «размер границы» (в данном случае равный 2), тогда как правила редукции типа «корона» не имеют такового. | ||
| Строка 106: | Строка 107: | ||
'''Цель (г): алгоритмы | '''Цель (г): аппроксимационные алгоритмы с полиномиальным временем выполнения''' | ||
Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению алгоритма | Теория использования экстремальных структур с полиномиальным временем выполнения напрямую приводит к получению аппроксимационного алгоритма ОДМЛ с константным множителем и полиномиальным временем выполнения. Вначале выполним редукцию G при помощи правил кернелизации. Правила редукции сохраняют параметры аппроксимации. Возьмем любое дерево T (не обязательно остовное) в графе G. Если выполняются все утверждения касательно структуры, тогда (согласно рассуждениям граничной леммы) дерево T должно иметь не менее n/c листьев для c = 3,75. Таким образом, восстановив T с учетом произведенной редукции, получим c-аппроксимацию. | ||
Если по меньшей мере одно утверждение касательно структуры не выполняется, то дерево T можно улучшить, опираясь на один из индуктивных приоритетов. Заметим, что каждое утверждение | Если по меньшей мере одно утверждение касательно структуры не выполняется, то дерево T можно улучшить, опираясь на один из индуктивных приоритетов. Заметим, что каждое утверждение доказывается посредством рассуждения, которое можно интерпретировать как подпрограмму улучшения T с полиномиальным временем выполнения в случае противоречия утверждению. | ||
Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента, как мы получим дерево | Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента, как мы получим дерево T', для которого выполняются все утверждения касательно структуры. В этот момент мы должны получить решение с c-аппроксимацией. | ||
| Строка 127: | Строка 128: | ||
Здесь используются следующие сокращения: TW – это древесная ширина дерева (TREEWIDTH), BW – ширина полосы (BANDWIDTH), VC – вершинное покрытие (VERTEX COVER), DS – доминирующее множество (DOMINATING SET), G – род (GENUS), а ML – максимальное количество листьев (MAX LEAF). Обозначение во второй строке и четвертом столбце говорит о том, существует | Здесь используются следующие сокращения: TW – это древесная ширина дерева (TREEWIDTH), BW – ширина полосы (BANDWIDTH), VC – вершинное покрытие (VERTEX COVER), DS – доминирующее множество (DOMINATING SET), G – род (GENUS), а ML – максимальное количество листьев (MAX LEAF). Обозначение во второй строке и четвертом столбце говорит о том, что существует FPT-алгоритм для решения задачи DOMINATING SET на графе G с шириной полосы не более k. Обозначение в четвертой строке и втором столбце говорит о том, что неизвестно, может ли задача BANDWIDTH быть оптимально решена FPT-алгоритмом, если параметром является граница числа доминирования входного графа. | ||
MAX LEAF применяется к последней строке таблицы. Для графов с максимальным количеством листьев, ограниченным k, максимальный размер независимого множества может быть вычислен за время <math>O^* (2,972^k) \;</math> на основе редукции ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным. | MAX LEAF применяется к последней строке таблицы. Для графов с максимальным количеством листьев, ограниченным k, максимальный размер независимого множества может быть вычислен за время <math>O^* (2,972^k) \;</math> на основе редукции до ядра размером не более 7k. Использование результата решения одной задачи в качестве исходных данных для другой задачи оказывается весьма практичным. | ||
== Применение == | == Применение == | ||
Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [5]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [6]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [7]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13]. | Задача построения остовного дерева с максимальным количеством листьев применяется в расчетах компьютерной графики с целью создания представлений полосы треугольников для быстрого интерактивного рендеринга [5]. Также она находит применение в области перераспределения трафика и проектирования сетей – например, для проектирования оптических сетей и распределения используемых длин волн для снижения стоимости сети – в терминах оконечного оборудования либо электронных переключателей [6]. Задача о минимальной энергии в беспроводных сетях заключается в нахождении радиус-вектора передачи для всех станций таким образом, чтобы полная мощность излучения всей сети была насколько возможно малой. Ограниченная версия этой задачи эквивалентна задаче нахождения остовного дерева с максимальным количеством листьев [7]. Задача поиска остовных деревьев с большим числом листьев эквивалентна задаче поиска небольших связных доминирующих множеств и в связи с этим также носит название задачи о минимальном связном доминирующем множестве [13]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 147: | Строка 149: | ||
'''Алгоритмические формы подхода на базе граничной леммы''' | '''Алгоритмические формы подхода на базе граничной леммы''' | ||
Из гипотезы граничной леммы о том, что (G, k) является «да-экземпляром», следует, что существует структура, являющаяся свидетелем для данного факта. Не делается предположений о том, что к этой структуре имеется алгоритмический доступ, а когда будут найдены правила редукции, они должны представлять собой преобразования, которые могут быть применены к (G, k) и структуре, которая может быть найдена в (G, k) за полиномиальное время. Иными словами, правила редукции не могут быть определены относительно структуры-свидетеля. Возможно ли описать более общие подходы к кернелизации, при которых структура-свидетель, используемая в ходе доказательства граничной леммы, может быть вычислена за полиномиальное время, и эта структура предоставит условный контекст для некоторых правил редукции? Как эти подходы изменят метод использования экстремальной структуры? | Из гипотезы граничной леммы о том, что (G, k) является «да-экземпляром», следует, что существует структура, являющаяся свидетелем для данного факта. Не делается предположений о том, что к этой структуре имеется алгоритмический доступ, а когда будут найдены правила редукции, они должны представлять собой преобразования, которые могут быть применены к (G, k) и структуре, которая может быть найдена в (G, k) за полиномиальное время. Иными словами, правила редукции не могут быть ''определены'' относительно структуры-свидетеля. Возможно ли описать более общие подходы к кернелизации, при которых структура-свидетель, используемая в ходе доказательства граничной леммы, может быть вычислена за полиномиальное время, и эта структура предоставит условный контекст для некоторых правил редукции? Как эти подходы изменят метод использования экстремальной структуры? | ||
'''Задача с аннотациями''' | '''Задача с аннотациями''' | ||
Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины должны быть листьями ( | Можно рассмотреть обобщенную задачу построения остовного дерева с максимальным количеством листьев (MAX LEAF), в которой вершины и ребра имеют различные аннотации, говорящие о том, какие вершины ''должны'' быть листьями (или внутренними вершинами) в решении, и т.д. В общем случае подобная обобщенная форма задачи будет сложнее вышеописанной более простой формы. Однако некоторые из «наиболее известных» FPT-алгоритмов для решения различных задач основаны на таких обобщенных формах с аннотациями. В качестве примеров можно привести алгоритмы нахождения доминирующего множества для планарного графа (PLANAR DOMINATING SET) и разрывающего множества вершин (FEEDBACK VERTEX SET) [4]. Должны ли аннотации быть непременным компонентом рецепта наилучшего возможного алгоритма кернелизации с полиномиальным временем выполнения? | ||
== См. также == | == См. также == | ||
