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

Постановка задачи

Дан некоторый граф. Найти на нем путь минимальной длины при условиях:

1) необходимо выйти из начального пункта, обойти все остальные и вернуться в исходный пункт;

2) в каждом пункте, кроме начального, можно побывать ровно один раз.

Методы решения

Данную задачу можно решать различными методами:

1) простым перебором;

2) методом ветвей и границ;

3) жадным алгоритмом.

Существует также множество других алгоритмов.

Алгоритмы

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

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

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

Метод перебора является самым медленным, но при этом позволяет отыскать путь с наименьшей длиной.

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

Жадный алгоритм является самым быстрым, но при этом не всегда позволяет найти путь минимальной длины.