Cтраница 1
Нижняя оценка стоимости L ( пу), сопоставленная каждой вершине яу, записывается слева над соответствующей вершиной. Для упрощения записи вместо обозначен. [1]
Выбирается текущая активная вершина с наименьшей нижней оценкой стоимости. В случае, если этому критерию удовлетворяет несколько вершин, то выбирается вершина, порожденная первой. [2]
Лемма 6.3. ( Алгоритм ветвей и границ всегда дает нижнюю оценку стоимости оптимального решения; если известно некоторое полное решение, то он также дает величину отклонения стоимости этого решения от оптимальной. [3]
Теорема 6.1. ( Потребности в вычислительных ресурсах не увеличиваются ( но могут уменьшиться), если исключаются вершины, у которых нижняя оценка стоимости превышает верхнюю оценку стоимости. [4]
Рассмотрены вопросы экономного кодирования слов контекстно свободного языка, порожденного грамматикой с неразложимой матрицей первых моментов. Получена неулучшаемая нижняя оценка стоимости двоичного кодирования. Построен алгоритм асимптотически оптимального кодирования, имеющий квадратичную временную сложность. [5]
БВЬ оказывается, по меньшей мере, такой же, а часто и превышает оценку, достигнутую алгоритмом ВВг. Поскольку мы исполь-зуем правило ветвления LLB, то активная вершина, имеющая наименьшую нижнюю оценку стоимости, всегда является текущей вершиной ветвления. Эта нижняя оценка стоимости, обозначенная L, совместно с окончательной верхней оценкой 0 может быть использована для оценки точности приближения к оптимальному решению. [6]
Допуском BR называется действительное число, O BjR l, представляющее собой желаемую величину максимального относительного отклонения оптимальной стоимости от стоимости приемлемого решения. На каждой стадии алгоритма U представляет собой стоимость лучшего из известных полных решений, a L - известную нижнюю оценку стоимости оптимального решения. [7]
ЕТ - что время счета равно или превышает TIMELIMIT; EN - что число активных вершин равно MAXSZAS. Если алгоритм завершается с превышением предельных ресурсов ( ЕТ или EN в колонке S), то в качестве минимальной нижней оценки стоимости заносится наименьшая нижняя оценка, взятая по активным вершинам. [8]
Сценарии 1 и 2 имеют те же тенденции, за исключением темпов роста. Эта 50 % - я разница в росте смертности от обычных загрязнителей означает 35 тыс. предотвращенных смертей ежегодно к 2010 г. Если использовать коэффициент дисконтирования 10 % и нижнюю оценку стоимости статистической жизни в России 300 тыс. дол. [9]
БВЬ оказывается, по меньшей мере, такой же, а часто и превышает оценку, достигнутую алгоритмом ВВг. Поскольку мы исполь-зуем правило ветвления LLB, то активная вершина, имеющая наименьшую нижнюю оценку стоимости, всегда является текущей вершиной ветвления. Эта нижняя оценка стоимости, обозначенная L, совместно с окончательной верхней оценкой 0 может быть использована для оценки точности приближения к оптимальному решению. [10]
Такие методы по сути перечислительные, но они выигрывают в эффективности в результате отсечения больших областей пространства возможных решений. Это делается путем вычисления нижней оценки стоимости каждого маршрута, включающего некоторые связи и исключающего некоторые другие; если нижняя оценка достаточно велика, то отсюда следует, что такой маршрут не может быть оптимальным. После длинной серии безуспешных экспериментов мы с Хелдом случайно обнаружили сильный метод получения нижних оценок. Эта техника ограничений позволила нам сильно сокращать пространство поиска, так что мы сумели решать задачи даже с 65 городами. Я не думаю, что какой-нибудь из моих теоретических результатов потряс меня столь же сильно, как вид чисел, появляющихся из компьютера ночью, когда Хелд и я впервые испытывали наш метод ветвей и границ. Позднее мы обнаружили, что наш метод - не что иное, как вариант старой техники, именуемой релаксациями Лагранжа, которая теперь рутинно используется для построения нижних оценок в методе ветвей и границ. [11]
Они показаны на схеме только для наглядности. В этом случае LOFs изменяется всякий раз, когда вершина, имеющая меньшую нижнюю оценку стоимости, чем текущее значение LOPS вызывает переполнение AS или DB. На рис. 6.8 представлена детальная блок-схема, описывающая процесс непосредственного применения правил исключения. Можно использовать и более - эффективные в вычислительном аспекте методы, но простота данного способа придает ему значительные преимущества. [12]
Статистика размеров максимального множества активных вершин может быть принята в качестве оценки минимального объема памяти, требуемого для выполнения алгоритма. Средний объем требуемой памяти для задач данного размера п может быть найден путем усреднения этих данных. При л10 средний объем памяти для алгоритма ВВг составляет только 15 % от требуемого объема памяти для алгоритма ВБ2, а среднее время счета ВВг составляет всего лишь 13 % от времени счета ВВ. Улучшение характеристик по времени и по памяти возникло за счет того, что все потомки вершины nd, имеющие нижнюю оценку стоимости L ( nd), превышающую верхнюю оценку U, немедленно исключались посредством правила U / DE. Эти потомки никогда не стали бы активными, и для них не было необходимости проверять с помощью правила AS / DB, доминируют ли над ними текущие активные вершины. [13]
Предельное количество ресурсов RB представляет собой вектор, компонентами которого являются верхние границы общего времени, отведенного для расчетов, и объем памяти для хранения активных вершин и непосредственных потомков вершины ветвления. В частности, RB ( TIMELIMIT, MAXSZAS, MAXSZDB), где TIMELIMIT обозначает заранее заданное максимальное время счета, MAXSZAS1 - максимальный разрешенный размер множества активных вершин и MAXSZDB 1 - максимальный разрешенный размер множества потомков каждой вершины ветвления. Когда требуемое время счета превышает TIMELIMIT, выполнение алгоритма останавливается и выводится последнее состояние процесса поиска. Если превышается предел по памяти, то теряются одно или несколько частичных решений, потомки которых могли бы стать оптимальными решениями. Нижняя оценка стоимости всех потомков устанавливается с учетом наименьшей нижней оценки вершин, отброшенных в результате переполнения. [14]