В начале девяностых поиск схемы платы упирался в тринадцать вложенных циклов, а слишком оптимистичная оценка отсекла лучший вариант. Основатель «Школы траблшутеров», экс-директор Альфа-Банка по процессам, Олег Брагинский рисует метод ветвей и границ, который ищет лучшее решение без полного перебора, в трёх нотациях.

Рис. 1. Схема по ГОСТ 19.701: раскрыть узел, отсечь ветку или запомнить лист
В поиске систолических структур для доработки плат на процессоре Motorola DSP96002 провёл экспресс-анализ и отсёк решения, которые посчитал маловероятными. Компьютеры начала 90-х были крайне слабыми, и полный перебор за разумное время был невозможен.
Совершенствуя программу, долго размышлял над ускорением 13 вложенных циклов и случайно понял: слишком оптимистичная оценка отсекла вариант, который потом оказался лучшим.
Короткий ответ: метод ветвей и границ ищет лучшее решение и отсекает целые ветки, если честная оценка показывает, что лучше уже найденного там не будет.
Рисовать такой поиск руководителю удобнее всего схемой-деревом: видно, какие ветки раскрыли, какие отсекли и почему.
Как устроен отсев?
Метод ветвей и границ – способ перебора деревом: решение – развилка, итог – лист.
У каждого узла – оценка: результат, лучше которого в ветке не бывает.
Если оценка не лучше уже найденного или нарушено условие задачи, ветку отсекают целиком – со всем, что под ней.
По ГОСТ 19.701 – цикл по списку узлов и две проверки.
Метод предложили Эйлса Ленд и Элисон Дойг из Лондонской школы экономики в 1960 году, а название закрепилось в 1963-м после статьи Литтла о задаче коммивояжёра.
Почему оценка должна быть честной?
Граница должна быть щедрой: обещать ветке не меньше, чем та способна дать. Самоуверенное «здесь ничего не будет» – не граница, а догадка, и с ней метод выбросит лучшее.
Как это выглядит на деле?
Сервисная компания «Кедр» оснащает новый центр обслуживания: компрессор, станок и подъёмник, у каждого – надёжный и экономный вариант. Бюджет – 14 миллионов рублей, цель – меньше часов простоя по статистике отказов.

Рис. 2. Пять отсечённых веток и один лучший лист
Из восьми комбинаций метод довёл до конца только одну: надёжный компрессор, экономный станок и надёжный подъёмник – 14 миллионов и 65 часов простоя в год. Остальные ветки отсечены по бюджету или по оценке.
Где хватает отсева худших?
Выбирали банкоматы – достаточно сложные устройства. Большая география расстановки означала широкий диапазон погодных условий, и выбрать лучшую технику было трудно.
Решил действовать иначе: сосредоточился на отсеве худших вариантов по статистике инцидентов узлов. Выбрали ли лучший вариант – не уверен, зато точно отсекли худшие.
Это первая половина метода: граница убирает заведомо плохие ветки. Без поиска среди оставшихся лучший выбор не гарантирован, но риск провала уже срезан.
Как сократить само дерево?
Проводил тендер на ремонт и переоснащение банковских отделений. Их сотни, к тому же не хотелось отдавать множественным подрядчикам детальные планы.
Вместо реальных экспликаций рассчитал средние показатели помещения: площадь, высоту, число окон и дверей, расположение видеокамер и датчиков. Перебор всех вариантов был невозможен, поэтому моделирование стало выходом.
Типовое помещение заменяет сотни листьев одним: дерево сжимается до посильных размеров, а детальные планы остаются у заказчика.
Когда остановиться?
Занимался оптимизацией размещения скрытого оборудования на круизном лайнере. Надеялся расположить максимум техники наилучшим образом, но понял, что не уложусь в сроки.
Вместо «считать всё» решил остановиться на «достаточно хорошем» варианте.
Метод позволяет завершить поиск: разрыв между лучшим найденным и лучшей оценкой показывает, что ещё можно выиграть. Если это пара процентов, счёт дороже выгоды.
Сколько стоит расчёт?
Модель: у 30 решений с двумя вариантами – 1’073’741’824 комбинации. При 10 секундах на вариант перебор занял бы 340 лет.
Хорошая граница отсекает почти всё дерево, но в худшем случае метод не быстрее перебора.
Где применять отсев?
Там, где вариантов слишком много для перебора, а оценку ветки посчитать легко: выбор поставщиков, состав команды, раскрой и размещение, расписания. Чем точнее граница, тем больше веток уходит в отсев.
В следующей статье сборника – дерево решений: как выбирать, когда исход зависит от случая, а у каждого исхода есть вероятность.
Какими нотациями рисовать отсев?
ГОСТ 19.701 передаёт цикл по узлам и две проверки, его ценят разработчики и аудиторы.
Дерево решений любят руководители и закупщики: видно, где и почему отсекли ветку.
Диаграмма Насси – Шнейдермана – способ рисовать алгоритм вложенными блоками без стрелок. Ею пользуются программисты и преподаватели: цикл и развилки читаются как код.

Рис. 3. Список узлов, отсев и запоминание лучшего
Какая нотация лучше?
Лучшая нотация для отсева вариантов – дерево решений: 21 балл против 19 у Насси – Шнейдермана и 16 у ГОСТ. Руководитель за минуту видит, где и почему отсекли ветку. Вес вопроса о руководителе удвоен: сборник написан для него.

Рис. 4. Оценка трёх нотаций: 16, 21 и 19 баллов
Диаграмма Насси – Шнейдермана отстала на два балла и удобна тем, кто программирует перебор. ГОСТ остаётся для регламентов и аудита.
Что сделать руководителю?
Хватит четырёх шагов:
- Разложите решение на шаги: каждый выбор – развилка дерева.
- Придумайте честную оценку ветки – щедрую, а не самоуверенную.
- Отсекайте ветки по ограничениям и по границе, начиная с самых перспективных.
- Остановитесь, когда разрыв между найденным и лучшим возможным меньше цены дальнейшего счёта.
Что запомнить?
- ветви – возможные решения, границы – оценки, лучше которых в ветке не бывает
- одна отсечённая ветка убирает сразу все варианты под ней
- граница должна быть щедрой: самоуверенная оценка выбрасывает лучшее
- разрыв между найденным и оценкой подсказывает, когда остановиться
- отсев вариантов лучше всего рисовать деревом решений.