Метод параллельного поиска
В зависимости от специфики задачи подмножества разных ветвей могут быть как пересекающимися, так и непересекающимися. Рассмотрим задачу компоновки схемы в n конструктивных модулей. Множество элементов схемы Э поставлено во взаимнооднозначное соответствие множеству вершин Х гиперграфа Э «Х. Указанная задача может быть решена алгоритмом, реализующим метод параллельного поиска. Результатом его работы будет разбиение множества Х вершин гиперграфа на n подмножеств Xi, i =1, n. Так как один и тот же элемент схемы не может входить в разные конструктивные модули и состав X i определяется по методу поиска в глубину последовательным включением вершин x Î X в Xji (Xji соответствует Mji), то Xji Ç X jp =Æ для всех i, p Î I ={1, n }. Таким образом, в данной задаче подмножества, принадлежащие разным ветвям дерева решений, должны быть непересекающимися. Если подмножества вариантов 1-го уровня содержат все варианты решения, т.е. удовлетворяют условию È M 1 i = M и оценка выбора подмножества в каждой ветви является отсекающей, то метод обеспечивает получение точного решения. 36.Дополнительные отсечения при использовании метода ветвей и границ. Задача: поиск маршрута (простой цепи) минимальной длины из некоторой исходной точки в заданную конечную. Стратегия декомпозиции множества решений – по методу в ширину. Принцип разбиения – включение во фрагмент пути некоторого ребра. Оценочная функция в каждой вершине дерева – суммарная длина ребер уже построенного фрагмента маршрута – нижняя граница целевой функции. Поскольку гарантия, что эта оценка является отсекающей отсутствует, она может использоваться как оценка перспективности, т. е. для выбора очередной вершины ветвления. Однако в данном случае эта оценка может выступать в качестве отсекающей в «особых» вершинах дерева решений. Этот факт основывается на свойстве графа – результата решения: маршруты, как простые цепи, могут проходить через одну и ту же вершину графа и иметь разную длину до этой вершины.
|
