4554
правки
Остовное дерево с максимальным количеством листьев: различия между версиями
Перейти к навигации
Перейти к поиску
Остовное дерево с максимальным количеством листьев (посмотреть исходный код)
Версия от 20:53, 12 августа 2016
, 12 августа 2016нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 113: | Строка 113: | ||
Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента как мы получим дерево V, для которого выполняются все утверждения касательно структуры. В этот момент мы должны получить решение с c-аппроксимацией. | Последовательность этих действий можно применить к исходному дереву T (и его потомкам) только полиномиальное количество раз, определяемое списком индуктивных приоритетов, до того момента как мы получим дерево V, для которого выполняются все утверждения касательно структуры. В этот момент мы должны получить решение с c-аппроксимацией. | ||
Цель (г): структура, используемая для определения экологии сложности | |||
Цель заключается в том, чтобы понять, как именно каждый параметр, определяющий входные данные задачи, влияет на сложность всех других задач. В качестве примера рассмотрим таблицу 1: | |||
[[Файл:MLST_3.png]] | |||
Таблица 1. Экология сложности параметров | |||