Алгоритм, использующий метод ветвей и границ. С++

Нужно реализовать алгоритм, использующий метод ветвей и границ.

Язык С/С++

Точный алгоритм решения задачи аппроксимации графа A

Вход: произвольный граф G без петель и кратных рёбер, с числом вершин 20-30.

Результат: граф M* такой, что p(G,M*) = min p(G,M) // p – расстояние.

Допустимое решение – граф M – может состоять из следующих «элементов»: вершина, ребро (на 2 вершинах, соответственно), треугольник (3 вершины, 3 ребра) и никаких других. Оптимальный граф M* – граф M с наименьшей оценкой границы, т.е. с наименьшим числом удалённых рёбер.

Шаг 0. Устанавливаем для графа G оценку границы равную нулю.

Шаг 1. Если граф G не является допустимым решением, то переходим к шагу 2. Если граф G является допустимым решением, то этот граф – искомое решение. Конец.

Шаг 2. Берём в графе G произвольное ребро. В ветвлении рассматриваем следующие варианты: граф G без этого ребра (1), граф G с фиксированным этим ребром (т.е. ребро не может быть удалено на любом последующем шаге).

Граница будет оцениваться по количеству удалённых рёбер. Для (1) она увеличится на единицу, для (2) – не изменится.

Далее, среди имеющихся вариантов выбираем вариант с наименьшей границей и переходим на шаг 1.

Данный алгоритм является вариацией полного перебора, значит, очевидно, найденный граф будет оптимальным.

При необходимости могу разъяснить более подробно работу алгоритма, а также показать пример.