Сложность задачи о раскраске дуг
Из этого не следует, что задача о раскраске дуг является ЖP-полной, — мы всего лишь свели ее к известной ЖP-полной задаче, что ничего не говорит о ее сложности. Для задачи о раскраске путей на обобщенных графах легко выполнить сведение задачи о раскраске графа к раскраске путей, тем самым устанавливая ЖP-полноту задачи о раскраске путей. Однако это прямолинейное сведение не работает, когда используемый граф представляет собой простой цикл.
Итак, что же можно сказать о сложности задачи о раскраске дуг? Рис. 10.1. Экземпляр задачи о раскраске дуг с шестью дугами (a, b, c, d, e, f) для цикла из четырех узлов |
Как выясняется, ЖР-полнота задачи о раскраске дуг доказывается с использо- ванием очень сложного сведения. Это огорчит людей, работающих с оптоволо- конными сетями, потому что означает, что задача оптимального распределения длин волн вряд ли имеет эффективное решение. Однако все известные сведения, демонстрирующие ЖР-полноту задачи о раскраске дуг, обладают одним интерес- ным свойством: сложные экземпляры задачи о раскраске дуг, создаваемые ими, всегда имеют достаточно большое множество длин волн.
Итак, эти сведения не доказывают, что задача о раскраске дуг сложна при малом количестве длин волн; они оставляют возможность того, что для любого фиксированного, постоянного количества длин волн к задача распределения длин волн может быть решена за время, полиномиальное по n (размер цикла) и m (количество путей). Другими словами, мы можем надеяться на время выполнения в форме, приведенной для задачи о вершинном покрытии в разделе 10.1: O(f (к) · p(n, m)), гдеf () может быть быстрорастущей функцией, но p(·,·) имеет полиномиальную скорость роста.Такое время выполнения выглядит заманчиво (если f () не растет с совсем запредельной скоростью), так как оно делает распределение длин волн потенци- ально приемлемым при малом их количестве. Чтобы понять, насколько непросто добиться такого времени выполнения, приведем аналогию: общая задача о рас- краске графа сложна уже для трех цветов. Если бы задача о раскраске дуг была разрешима для любого фиксированного количества длин волн (то есть цветов) к, это означало бы, что она является частным случаем раскраски графа с качественно иной сложностью.
В этом разделе мы постараемся создать алгоритм с временем выполнения такого типа, O(f (к) · p(n, m)). Как упоминается в начале раздела, сам алгоритм строится на принципах, приводившихся в разделе 10.2 при решении задачи о не- зависимом множестве с максимальным весом для деревьев. Сложность поиска, присущая поиску независимого множества с максимальным весом, была сокра- щена тем фактом, что для каждого узла v в дереве T задачи в компонентах T - {v} становились полностью изолированными, когда мы принимали решение о вклю- чении (или невключении) v в независимое множество. Это конкретный пример общего принципа фиксирования малого множества решений, а следовательно, разделения задачи на меньшие подзадачи, которые могут решаться независимо.
В данном случае аналогичная идея заключается в выборе конкретной точки цикла и решении о том, как раскрашивать дуги, проходящие через эту точку; за- крепление этих степеней свободы позволяет определять серии меньших подзадач для оставшихся дуг.
Еще по теме Сложность задачи о раскраске дуг:
- СЛОЖНОСТЬ КОГНИТИВНАЯ
- 5.6.3. Сложность - первое условие прозренний
- Классификация по сложности и оперативности
- СЛОЖНОСТЬ
- Сложность структуры организации.
- Сложность интровертного поведения
- Сложность вредоносного агента (предмета, средства)
- Сложность вредоносного агента (предмета, средства)
- 3. Сложность метода не служит гарантией его эффективности.
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА