Отрывки из этой статьи можно найти на странице 57 Справочника конкурентоспособного программиста. Прочие исключения и материалы, взятые из Видео Полилога на YouTube по теме.

Введение

В экспоненциальной временной сложности есть что-то, что меня действительно беспокоит. Если вы часто посещаете тренировочные полигоны leetcode, вам знакомо это чувство: часто они являются результатом какого-то неприятного метода грубой силы (тьфу), например, проверки каждого состояния какой-либо комбинации.

Это не следует путать с полиномиальной временной сложностью, где показатель степени является постоянным значением (и, следовательно, его можно переварить); с экспоненциальной временной сложностью экспоненциальный член растет с размером ввода (т.е. O (n²) против O (2ⁿ)).

Таким образом, бывают случаи, когда я смотрю на вопрос leetcode более часа, с руками на моей голове, отчаянно пытаясь вызвать «правильный» ответ в моем уме. Тем временем редактор кода пуст; глядя назад с шаблоном кода по умолчанию, оставленным нетронутым рядом с мигающим курсором. Потерпев поражение, я всегда удивляюсь, когда в конце концов нажимаю вкладку «решение» и первое, что вижу: Подход 1: грубая сила (принято).

Как и во многих других проблемах, иногда грубая сила является единственным решением. И если этот метод грубой силы требует экспоненциальной временной сложности, пусть будет так; ничего не поделаешь.

Или есть?

Поиск в ширину

Давайте сначала сделаем шаг назад и представим, что мы пытаемся разработать алгоритм для сборки кубика Рубика. Мы можем предположить, что каждая уникальная конфигурация куба представляет состояние; и что разные состояния связаны физически возможными ходами.

Мы можем использовать алгоритм поиска в ширину для поиска состояний смежной связности. Таким образом, мы исследуем все состояния, которых мы можем достичь из нашей исходной зашифрованной конфигурации за один ход, затем все состояния, которых мы можем достичь за два хода, и так далее. Количество состояний, которые нам придется исследовать с каждым ходом, увеличивается экспоненциально: если есть 18 возможных ходов для каждого состояния, то количество состояний будет умножаться на 18 для каждого хода (на самом деле немного меньше, поскольку определенные ходы могут отменять предыдущие). движется).

Мы можем продолжать исследовать состояния из нашей зашифрованной конфигурации, пока не придем к решенному состоянию конфигурации. Таким образом, мы нашли некоторый путь или некоторую последовательность ходов, которая собирает куб. Проблема с этим подходом в том, что он мучительно медленный.

Следует отметить, что наш подход работает и в обратном направлении. Поиск из решенного состояния и попытка найти нашу исходную зашифрованную конфигурацию — это эквивалентное решение, которое также работает; хотя так же медленно.

Чтобы исследовать все состояния, которых мы можем достичь всего за 5 ходов, нам нужно рассчитать примерно 2 миллиона состояний; за 10 ходов это число увеличивается до 3 триллионов состояний.

Иногда вам просто нужно принять это. В нашем поиске скорости; мы можем вообще ничего не решить. В конце концов, у некоторых проблем нет лучшего решения, чем медленное. К счастью, это не одна из тех проблем.

Встреча в середине

Вместо того, чтобы начинать с нашей известной зашифрованной конфигурации и выполнять BFS (поиск в ширину), пока мы не изучим решенную конфигурацию, мы можем попробовать два отдельных экземпляра BFS; один начинается с зашифрованной конфигурации, а другой начинается с решенной конфигурации. Затем мы будем выполнять одну итерацию BFS за раз для каждого экземпляра, пока они, так сказать, не «встретятся посередине». По сути, мы будем выполнять исходный алгоритм дважды, за половину хода.

Причина, по которой это настолько мощно, заключается в том, что наше пространство поиска растет в геометрической прогрессии. Сократив количество ходов наполовину, наше пространство поиска точно так же экспоненциально уменьшится; даже если мы проделаем всю операцию дважды. На самом деле мы можем доказать, что временная сложность с помощью этого метода улучшается.

Называть «встречу посередине» алгоритмом было бы слишком сложно. Более подходящим ярлыком может быть подход. У нас может возникнуть соблазн уменьшить масштаб этого подхода; возможно, мы можем сделать вывод, что для выполнения «встречи посередине» требуется некоторое начальное и целевое состояние. Мы рассмотрим еще один совершенно другой пример, который продемонстрирует обратное.

Сумма комбинации

Наш следующий пример взят из Справочника конкурентоспособного программиста. Нам дан список из n чисел и некоторое целевое число x, и мы хотим выяснить, есть ли в списке какая-то комбинация чисел, которая в сумме составляет x, иначе называемая комбинационной суммой.

Учитывая список [2, 4, 5, 9] и цель 15, мы можем выбрать [2, 4, 9] из списка, чтобы получить 15. Если бы нашей целью было 10, решения не было бы.

Грубое решение этой проблемы включает генерацию каждого подмножества чисел и проверку, равна ли сумма каждого подмножества целевому x. Мы можем сгенерировать все подмножества списка и выполнить проверку за время сложности O(2ⁿ). И снова мы пришли к решению, которое хотели бы оптимизировать.

Справочник конкурентоспособного программиста описывает реализацию «встречи посередине» следующим образом:

Идея состоит в том, чтобы разделить список на два списка A и B так, чтобы оба списка содержали примерно половину чисел. Первый поиск генерирует все подмножества A и сохраняет их суммы в список Sa. Соответственно, второй поиск создает список Sb из B. После этого достаточно проверить, можно ли выбрать один элемент из Sa и другой элемент из Sb такие, что их сумма равна x. Это возможно именно тогда, когда есть способ составить сумму x, используя числа исходного списка.

Например, предположим, что список равен [2, 4, 5, 9] и x = 15. Сначала мы разделим список на A = [2,4] и B= [5,9]. После этого создаем списки SA=[0,2,4,6] и SB=[0,5,9,14]. В этом случае возможно образование суммы x= 15, так как SAсодержит сумму 6, SBсодержит сумму 9 и 6 + 9 = 15. Это соответствует решению [2,4,9].

По сути, нам предлагается разделить входной список пополам; создание списка всех возможных сумм комбинаций для каждой половины списка. С этими двумя списками сумм задачу можно рассматривать как модифицированную задачу двух сумм. Это очень известная проблема, и ее можно решить с помощью линейной временной сложности. Детали проблемы двух сумм подробно обсуждаться не будут, но реализация, скорее всего, сохранит один из списков сумм в словаре и проверит ключи, перебирая другой список сумм.

В результате наше решение теперь намного быстрее по причинам, объясненным ранее. Мы применяем наш алгоритм суммирования комбинаций O(2ⁿ) для двух списков вдвое короче. Дополнительные линейные вычисления поверх наших сгенерированных списков несущественны.

Следовательно, мы можем взять алгоритм с экспоненциальной временной сложностью и резко повысить его скорость, выполнив один и тот же алгоритм дважды на двух половинах входных данных. В этом примере мы не пытаемся найти путь между двумя выборочными состояниями, поэтому «встреча посередине» не имеет здесь визуальной аналогии. Соответственно, мы должны обобщить «встречу посередине» как подход, при котором мы делим входное пространство на две равные части, объединяя два решения вместе, используя некоторую математическую или логическую тактику.

Я должен упомянуть, что, хотя большую часть этой статьи я посвятил критике экспоненциальной временной сложности, вы обнаружите, что «встреча посередине» также является эффективным подходом для оптимизации решений полиномиальной временной сложности. Доказательство этого, конечно, оставлено читателю в качестве упражнения.

Закрытие и благодарности

Встретиться посередине — это мощный инструмент, который вы должны добавить в свой арсенал. Способность распознать, когда этот подход является жизнеспособным решением, может иметь огромное значение между тем, какие программные решения могут быть реализованы в реальном мире; да, даже помимо решения проблем с литкодом (См.: DES/3DES, и почему 2DES не вещь).

Естественно, эти идеи также применимы к leetcode и любым проблемам, с которыми вы можете столкнуться на технических собеседованиях. Надеемся, что эта статья сыграла ключевую роль в том, чтобы помочь вам с любым из вышеперечисленных.

Эта статья была бы невозможна без видеоролика Polylog на YouTube о встрече посередине, и их видео является частью того, что вдохновило меня на написание этой статьи. Если у вас есть время, загляните на их канал, чтобы узнать больше интересного контента, связанного с математикой/логикой/программированием.