4.6.4 Метод ветвей и границ.

Пусть есть задача, имеющая решений: U = (u₁, ..., u_n). С каждым решением связан некоторый показатель , где - оценка эффективности решения. В гамильтоновом цикле в качестве эффективности выбирается длина цикла. Оптимальным будет решение, которое обеспечивает наименьшую из по всем : , т.е. будет минимальный гамильтонов цикл.

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

Разобьём множество решений на два непересекающихся подмножества решений и : . В каждом из этих подмножеств решений есть свои оценки эффективности: - оценка эффективности подмножества решений ; - оценка эффективности подмножества решений ; - общая оценка эффективности.

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

Данный метод удобно иллюстрировать с помощью дерева решений:

Рисунок 4.24 – Нахождение минимальной оценки

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

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