Ветви и границы

В сети рейсов 3468 аэропортов и 37 733 пары, между которыми есть прямой рейс в обе стороны. Какая самая большая группа аэропортов, где из каждого можно долететь в каждый без пересадки? Это наибольшая клика графа — задача, для которой быстрого алгоритма не знают. Метод ветвей и границ находит её и доказывает, что больше нет: 38 аэропортов. Решает всё оценка сверху. Если считать, что клика может вобрать всех оставшихся кандидатов, дерево поиска разрастается до 1 123 506 узлов. Если оценивать числом цветов в раскраске кандидатов — до 242.

Под картой — вилка. Оранжевая линия — размер лучшей найденной клики, она только растёт. Синяя — сколько ещё может дать то, что не просмотрено, она только падает. Когда они встречаются, поиск закончен: лучшего не бывает. С оценкой раскраской синяя линия с самого начала стоит низко, и ветви отсекаются уже у корня.

Идея

Перебор с возвратом строит решение по шагам: здесь — добавляет в клику аэропорт за аэропортом из тех, что связаны со всеми уже взятыми. Ветви и границы добавляют к нему два числа. Рекорд — лучшее решение, найденное до сих пор. Оценка ветви — число, которое заведомо не меньше лучшего решения внутри неё. Если оценка не больше рекорда, ветвь не открывают.

Ветвь, в которой нельзя найти лучше рекорда, можно пропустить целиком — для этого нужна оценка, которая никогда не занижает. Чем ближе оценка к правде, тем больше ветвей отсекается; дорогая, но точная оценка часто окупается многократно.

Оценка раскраской

Самая простая оценка для клики — «уже взятые плюс все кандидаты»: больше, чем кандидатов, взять нельзя. Но кандидатов сотни, а клика из них — десятки, и такая оценка почти ничего не отсекает. Точнее работает раскраска. Раскрасим кандидатов жадно: каждую вершину — в первый цвет, где у неё ещё нет соседей.

Эцудзи Томита и Томокадзу Сэки в 2003 году сделали из этого быстрый алгоритм. Кандидатов упорядочивают по цветам и перебирают с конца — с самого старшего цвета. Номер цвета вершины — оценка для всех кандидатов до неё включительно: среди них не больше стольких цветов. Как только «взято + номер цвета» не больше рекорда, весь оставшийся хвост ветви отбрасывается одним сравнением. Раскраску пересчитывают в каждом узле: она стоит дорого, но окупается тысячекратно.

Код

Аэропорты сортируются по числу связей: сильные вершины раньше дают хороший рекорд. В листинге обе оценки сравниваются на ста самых связанных аэропортах: на всей сети простая оценка на Python шла бы много секунд.

Сколько это стоит

Задача о клике NP-трудна, и худший случай ветвей и границ экспоненциален при любой оценке. Но настоящие графы обычно далеки от худшего, и разница между оценками — порядки величин.

На ста пятидесяти аэропортах простая оценка на Python тратит четыре секунды, а раскраске и на двухстах хватает 25 миллисекунд. С раскраской вся сеть из 3468 аэропортов решается на Go за 11 миллисекунд, а простая оценка уже на пятистах аэропортах тратит больше секунды.

Где легко ошибиться

• Оценка, которая занижает. Если оценка хоть раз меньше лучшего решения в ветви, отсечение выбросит оптимум, и ответ будет «хороший, но не лучший» — без всякого сообщения об ошибке.
• Сравнение со строгим знаком. Ветвь бесполезна, если оценка не больше рекорда: «≤», а не «<». Со строгим знаком ответ верен, но дерево больше.
• Плохой первый рекорд. Пока рекорд мал, отсекать нечего. Хорошее начальное решение — жадное, или порядок вершин по степени — сокращает дерево сильнее, чем кажется.
• Оценка дороже экономии. Раскраска в каждом узле стоит O(k²) сравнений; в маленьких ветвях проще и быстрее простая оценка. Хорошие решатели переключаются.
• Порядок обхода. Поиск в глубину экономит память и быстро находит рекорд; «сначала лучшая оценка» доказывает оптимальность за меньшее число узлов, но хранит всю очередь. Для огромных деревьев это разница между мегабайтами и гигабайтами.

Где работает

Решатели целочисленного программирования — главный потребитель метода: оценка ветви там — решение той же задачи без требования целых чисел, и считается она симплекс-методом. Точный коммивояжёр — нижняя оценка по остовным деревьям. Рюкзак с огромными весами, где таблица не помещается, — оценка жадностью с дробным последним предметом. Клики и раскраски — в анализе сетей, химии, расписаниях.

История

Эйлса Лэнд и Элисон Дойг описали метод в 1960 году как «автоматический способ решать задачи дискретного программирования» — для целочисленных задач с линейной оценкой. Название «ветви и границы» закрепилось после статьи Джона Литтла, Катты Мурти, Дьюры Суини и Кэролайн Карел 1963 года о задаче коммивояжёра. Ричард Карп в 1972 году включил клику в свой список 21 NP-полной задачи. Алгоритм с оценкой раскраской предложили Эцудзи Томита и Томокадзу Сэки в 2003 году, и его потомки до сих пор среди самых быстрых точных алгоритмов поиска клики.

Задачи

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