но новой границей для подзадачи С будет 
вместо предыдущего значения 248. Новой границей для подзадачи 
будет 
то же, что и раньше. (Граница для В останется, конечно, неизменной, так как решение задачи В является на самом деле гамильтоновым циклом. Теперь ветвление нужно делать в узле 
как 
а не в С, как в предыдущем случае. Это ветвление приводит, как и прежде, к подзадачам 
, и наилучшее решение (подзадача 
имеет значение 251.
Рис. 10.26. Поиск с деревом решений из примера 7.2 с улучшенной границей для задачи о назначениях.
Дальнейшее ветвление в С (где решение не является гамильтоновым циклом) уже не будет необходимым, так как его нижняя граница, а именно 254, больше чем 251. Прежняя граница для С, равная 248 (меньше 251), была недостаточной для того, чтобы прекратить ветвление в этом узле. Таким образом, улучшенная граница позволяет сэкономить два узла в дереве решений поиска, как это показано на рис. 10.26. Это дает экономию только на 2/9 для этой маленькой задачи, но для задач большого размера получается большой процент экономии узлов дерева, т. е. числа задач 
на 
назначениях, которые следует решить
8. Задачи
(см. скан)
(разд. 7.2), должна тогда быть 
(Необходимо второе стягивание, и решение новой задачи о назначениях равно 13.) Подзадачи 
получены, как и раньше,
