Постановка задачи о коммивояжере. Нахождение оптимального решения с применением метода ветвей и границ. Основной принцип этого метода, порядок его применения. Использование метода верхних оценок в процедуре построения дерева возможных вариантов.
Аннотация к работе
1.Постановка задачи о коммивояжере 2. Существует класс задач, которые не удовлетворяют принципу оптимальности, и, следовательно, для этих задач метод динамического программирования непосредственно использован быть не может. Предположим, что бродячий торговец должен, покинув город, которому мы присвоим номер 1 (рис. 1), объехать еще N-1 городов и вернуться снова в город номер 1.