Рассмотрим задачу об отыскании одного радиоактивного шарика среди n одинаковых шариков.

Рассмотрим задачу об отыскании одного радиоактивного шарика среди n одинаковых шариков. В качестве прибора, определяющего радиоактивность, используется дозиметр, два различных показания которого (есть радиоактивность или нет радиоактивности) естественно принять за значения оценочной функции, например, значения 0 или 1. Всякое подмножество, для которого значение оценочной функции равно нулю, исключается из дальнейшего рассмотрения  ( помечено *).  На рис.4 приведено ограниченное дерево перебора для n=100.  Сравним: в алгоритме полного перебора в худшем случае пришлось бы проверить 100 шариков, т.е. осуществить 100 проб. Для ограниченного дерева таких проверок потребуется только 7.

 

 

Рис.4. ограниченное дерева перебора для поиска радиоактивного шарика

Пример решения задачи коммивояжера

Решить методом ветвей и границ задачу коммивояжера для графа, содержащего 5 вершин.

Пусть исходный ориентированный граф  задан  матрицей стоимости:

 =

Начальное приведение матрицы стоимости. Матрица стоимости называется приведенной, если она имеет в каждой строке и каждом столбце хотя бы один нуль. Операция приведения заключается в вычитании из элементов каждой строки (столбца) минимального элемента этой строки (столбца) – константы приведения. Сумма констант приведения образует нижнюю граничную оценку стоимости любого возможного тура.

 Вычисление функции штрафа.  Функция штрафа – это множество чисел, вычисленных для каждого нуля приведенной матрицы посредством  суммирования двух минимальных чисел, из той строки и из того столбца, в которых расположен нулевой элемент.

Выбор ребра ветвления.  Для ветвления необходимо выбирать ребро, которому соответствует максимальная функция штрафа. Если существует несколько одинаковых максимальных значений функции штрафа,  выбор среди них может быть произвольным.

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

Вычисление граничной оценки для ветви, соответствующей включению ребра в тур. Для  вычисления граничной оценки  необходимо:

·        вычеркнуть в матрице стоимости строку и столбец, соответствующие выбранному ребру;

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

Ссылка на основную публикацию
Adblock detector