Метод уменьшения задачи

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

1. 
   Улучшение поиска с возвратом для оптимизационных
   

задач

2. 
   Для каждого узла (частично построенного решения) в
   

дереве пространства состояний метод вычисляет оценку
величины оптимизируемой функции во всех потомках
этого узла (расширений этого частичного решения)

3. 
   Оценка используется для
   

• 
  отбрасывания бесперспективных вершин
  
• 
  определения порядка построения дерева (узел с лучшей оценкой обычно исследуется раньше остальных)
  

Исполнитель алгоритма - это человек или автомат (в частности, им может быть процессор ЭВМ), умеющий выполнять некоторый, вполне определенный набор действий. Исполнителя характеризуют: • среда; • элементарные действия; • система команд; • отказы. Исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды, не задавая вопросов «почему» и «зачем». Про компьютер говорят, что он универсальный исполнитель алгоритмов, созданных для обработки информации. Компьютер может исполнять алгоритм, если он написан на одном из языков программирования. Такой алгоритм называют компьютерной программой. Программу можно ввести в память компьютера и запустить её. Тогда она может быть автоматически исполнена компьютером. В этом случае исполнителем алгоритма является компьютер.