Математические модели задачи размещения. Метод ветвей и границ

Если есть n элементов и n посадочных мест, то число возможных вариантов размещения равно n!. Уже для 15 элементов полный перебор дает время порядка 40 лет (на ЕС ЭВМ, видимо). Метод ветвей и границ позволяет делать ограниченный перебор вариантов путем отсечения неоптимальный ветвей. Возможно два порядка ветвления:
           

При построении каждого уровня дерева происходит оценка. Выбирается ветвь с наилучшей (наименьшей) оценкой и далее идет анализ только этой ветви.
Оценка складывается из трех компонентов (L = L₁ + L₂ + L₃):
L₁: суммарная длина связей между размещаемыми элементами
L₂: оценка суммарной длины связей между размещенными и еще не размещенными эл-тами
L₃: оценка суммарной длины между неразмещенными элементами

Метод обратного размещения.

E = {e₁,..., e_n} - множество элементов; L = {l₁,..., l_n} - множество позиций

Имеем матрицу соединений R = ||r_ij||_nxn и матрицу расстояний D = ||d_ij||_nxn.
Суммарное количество связей элемента e_i: r_i = Σ(j:1..n) r_ij.
Суммарная длина связей от элемента e_i до остальных элементов: d_i = Σ(j:1..n) d_ij.

Алгоритм:
1) Упорядочить вектор {r_i} по убыванию.

2) Упорядочить вектор {d_i} по возрастанию.

3) Соотнести упорядоченные таким образом элементы и позиции (пример):