Метод параллельного поиска

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

Рассмотрим задачу компоновки схемы в 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.Дополнительные отсечения при использовании метода ветвей и границ.
Идея алгоритма Дейкстры

Задача: поиск маршрута (простой цепи) минимальной длины из некоторой исходной точки в заданную конечную.

Стратегия декомпозиции множества решений – по методу в ширину.

Принцип разбиения – включение во фрагмент пути некоторого ребра.

Оценочная функция в каждой вершине дерева – суммарная длина ребер уже построенного фрагмента маршрута – нижняя граница целевой функции.

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

Однако в данном случае эта оценка может выступать в качестве отсекающей в «особых» вершинах дерева решений.

Этот факт основывается на свойстве графа – результата решения:

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