Графааналитический метод ветветй и границ

Графааналитический метод ветветй и границ относится к методу инжененрной оптимизации и он расчитан на получение квазиоптимальных решений, путём построение всех квазиоптимальных решений и нахождение в дальнейшем оптимального решение. Этот метод основан на применени дихатомичного дерева.

вставка 2

На каждом шаге построение алгоритма расматриваются все возможные образававшиеся весячие вершины.

При использования метода ветвей и границ идёт посделователньое построение дерева шаг за шагом. При этом на каждом шаге продолжение получаем из одной вершины, но для того, чтобы определить из какой продолжать построение, рассматриваются все конечные вершины.

Будем полагать, что на некоторм шаге а у нас образовались весячие вершины.

...1

Каждой вершине соответсует своя сложность Si(ri, ni), под которой мы будем понимать количество проверок, имеющих характеристический признак = 1 и лежащий в пути от нулевой вершины к вершине Xi.

...2

Вторая характеристика вершины - это модефицирования таблица покрыйти Bi (Di, Vi). она строится для каждой весячей вершины. При этом каждая таблица строится из исходной таблицы покрытий, путём вычеркивания строк, которым соотвествуют проверки в пути от корневой вершины к расматриваемой вершине. в том случае, если в пути лежит проверка с характеристическим признаком равная единице, то вычёркиваются все столбцы, которые накрываются этой прверкой. ВНИМАНИЕ по сколькро мы работает с дехатомичным деревом, то на каждом шаге может образоваться только две новых вершины, и для этих двух вершин нужно расчитать сложность построеных вершин и построить модифицированую матрицу. параметры можно использовать с предыдущего шага.

Третья характеритика - нижняя граница ожидаемых проверок для получение полного решения Inf Bi.

...3

Если предварительно проверки упорядочеть по возрастанию модуля характеристических чисел, то нижния граница....

Для продолжение хатомичного дереве..4, выбирается та вершина для которой имеются минимальные значения суммы...4. В качестве проверки выбирается превая проверка соотвествующий модефицированной теблице покрытий. На каждом шаге необходимо контралировать полное покрытие таблицы. Получаемые решения являются квазиоптимальные. Как правило этот метод не используют если идёт речь о построение алгоритма по минимальному числу проверок.

Алгоритм построение оптимального решения с учётом количества проверок и ресурсного обеспечености.

в том случае, если надо построить алгоритм который обладает минимальным количеством проверок и налиулчеми ресурсами используют ветвление границ, однако в качестве решающего правила выбирают функцию b В том случае, построение алгоритма начинают с того, что все проверки упорядычивают таким образом, чтобы...5.