Более эффективный по затратам пространства способ построения путей

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

Впоследствии этот прием был заложен в основу сокращения затрат пространства в задаче выравнивания последовательностей.

Наш план, как и прежде, основан на умном повторном использовании пространства — откровенно говоря, за счет возрастания затрат времени. Как поиск в глубину, так и поиск в ширину не проявляет достаточного рвения в повторном использовании пространства; оба должны постоянно вести большой исторический список. Нам нужен способ решить половину задачи, отбросить почти всю промежуточную работу, а затем решить другую половину задачи.

Ключевая роль в этом алгоритме отводится процедуре, которую мы назовем Path(C1, C2, L). Процедура определяет, существует ли последовательность операторов, состоящая не более чем из L шагов, которая приводит из конфигурации C1 в конфигурацию C2. Итак, исходной задачей является определение результата (да или нет) для Path(C0, C*, 2n).

Поиск в ширину может рассматриваться как следующая реализация этой процедуры средствами динамического программирования: чтобы определить Path(C1, C2, L), мы сначала определяем все C’, для которых выполняется Path(C1, C’, L − 1); затем мы проверяем для всех таких C’, ведет ли какой-нибудь оператор напрямую из C’ в C2.

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

Эффективнее было бы попытаться определить, существует ли какая-либо конфигурация C’, которая служит срединной точкой пути из C1 в C2. Можно сначала сгенерировать все возможные срединные точки C’.

Затем для всех C’ можно рекурсивно проверить, можно ли перейти из C1 в C’ не более чем за L/2 шагов и можно ли перейти из C’ в C2 не более чем за L/2 шагов.

Для этого потребуются два рекурсивных вызова, но нас интересуют только результаты «да/нет» для каждого из них; в остальном пространство можно использовать повторно.