[Перевод] Отсечение и поиск / Prune and search
Решал задачу на LeetCode (Word Search) и наткнулся на незнакомый мне термин «search pruning», либо «Prune and search». Немного погуглив узнал, что это метод решения задач оптимизации, на Википедии есть соответствующая статья. На русском языке я не нашел такого термина, только некоторые работы на studfile и автоматический корявый перевод на Wiki5, из-за чего решил перевести статью на Википедии, которую привел выше и немного пояснить, что этот термин означает. Перевод любительский и вольный, если будут ошибки, то поправьте, пожалуйста. Перевожу для ссылки из своего расширения LeetCode to Russian и для тех, кто наткнется на такой термин и решит погуглить его на русском языке. Если в русском языке существует похожее определение, но называется по-другому, то прошу написать в комментариях, чтобы я поправил статью.
Отсечение и поиск — метод решения задач оптимизации, предложенный Нимродом Мегиддо в 1983 году[1].
Основная идея метода заключается в рекурсивной процедуре, на каждом шаге которой размер входных данных уменьшается («отсекается») на постоянный коэффициент 0 < p < 1. Этот метод представляет собой форму алгоритма разделяй и властвуй, где на каждом шаге уменьшение происходит на постоянный коэффициент. Пусть n — размер входных данных, T(n) — временная сложность алгоритма «Отсечение и поиск» и S(n) — временная сложность одного отсечения. Тогда T(n) удовлетворяет следующему рекуррентному соотношению:
Рекуррентное соотношение выше напоминает рекуррентное соотношение для двоичного поиска, но имеет более крупный член S(n) по сравнению с константным членом двоичного поиска (T(n)=T(n/2)+O(1)). В алгоритмах «Отсечение и поиск» S(n) обычно имеет как минимум линейную сложность (так как требуется обработка всего входа). С этим предположением соотношение имеет решение T(n) = O(S(n)). В этом можно убедиться, применив основную теорему о рекуррентных соотношениях или заметив, что время решения рекурсивных подзадач уменьшается в геометрической прогрессии.
В частности, сам Мегиддо использовал этот подход в своем алгоритме линейного времени для задачи линейного программирования при фиксированном числе переменных и ограничений[2] и для задачи об ограничивающей сфере для набора точек в пространстве[1].
Теперь небольшое пояснение.
Отсечение и поиск — это метод оптимизации, при котором мы ищем что-либо в большом объеме данных, одновременно отсекая часть вариантов, которые с высокой долей вероятности не приведут к желаемому результату. Этот метод экономит время и ресурсы, позволяя сконцентрироваться на подходящих вариантах.
В контексте задачи Word Search поймем, что это означает: Что-либо — слово, которое мы ищем. Большой объем данных — это матрица с буквами. Когда рекурсивно ищем слово, мы «отсекаем» ячейки, которые точно не помогут найти искомое слово (не приведут к желаемому результату).
Решение задачи на псевдокоде
Условие задачи:
Даны матрица символов board размера m x n и строка word, верните true, если word есть в матрице board.
Слово может быть составлено из букв, находящихся в соседних ячейках. Две ячейки считаются соседними, если они находятся горизонтально или вертикально друг от друга. В каждом слове каждая буква из ячейки может использоваться только один раз. Первый пример со страницы задачи:
Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: trueЗаведем матрицу visited того же размера, что и board, чтобы отслеживать посещенные ячейки.
function exist(board, word):
m = размер строк в board
n = размер столбцов в board
for i from 0 to m - 1:
for j from 0 to n - 1:
if board[i][j] == word[0]:
visited = создать матрицу размером m x n, все элементы установлены в false
if search(board, word, visited, i, j, 0):
return true
return false
function search(board, word, visited, i, j, k):
// Проверяем условие выхода из рекурсии
// k - индекс текущей буквы в искомом слове word,
// инкрементируется каждый раз, как мы находим подходящую букву
if k == length(word):
return true
// Проверяем, что координаты находятся в пределах матрицы и ячейка не была посещена
if i < 0 or i >= m or j < 0 or j >= n or visited[i][j]:
return false
// Проверяем, соответствует ли текущая ячейка символу в слове
if board[i][j] != word[k]:
return false
// Помечаем текущую ячейку как посещенную
visited[i][j] = true
// Рекурсивно ищем следующую букву слова в соседних ячейках
if (
search(board, word, visited, i + 1, j, k + 1) or
search(board, word, visited, i - 1, j, k + 1) or
search(board, word, visited, i, j + 1, k + 1) or
search(board, word, visited, i, j - 1, k + 1)
):
return true
// Отмечаем текущую ячейку как непосещенную перед возвратом
visited[i][j] = false
return falseЭтот код использует рекурсивный метод поиска в глубину для проверки существования слова в матрице. Применение отсечения в данном случае заключается в проверке условий, которые могут привести к невозможности построения слова:
Если текущая ячейка не соответствует символу искомого слова, возвращаем
false;Проверяем, что координаты находятся в пределах доски. Если они выходят за границы, возвращаем
false;Проверяем, была ли уже посещена текущая ячейка. Если она уже посещена, это указывает на то, что мы уже были на этом пути, поэтому возвращаем
false.
Проверка этих условий существенно оптимизирует сложности по времени и памяти алгоритма поиска с возвратом, она помогают сократить количество рекурсивных вызовов и сокращают пространство поиска, что позволяет избежать избыточных вычислений.
В конце алгоритма, после проверки соответствия текущей буквы искомому слову в ячейке матрицы, а также всех условий отсечения, мы проверяем, достигли ли мы конца искомого слова (длина k равна длине слова). Если это условие выполняется, то мы успешно нашли все буквы слова в матрице, и функция возвращает true, указывая на успешное завершение поиска.
Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12:759–776 doi:10.1109/SFCS.1982.24
Nimrod Megiddo (1984) Linear Programming in Linear Time When the Dimension Is Fixed doi:10.1145/2422.322418
