Prune and search / Prune and search

Prune and search / Prune and search

I was solving a task on LeetCode (Word Search) and came across the unfamiliar term “search pruning” or “Prune and search”. A few Googlers found out that this is a method of solving optimization tasks, there is a corresponding article on Wikipedia. I didn’t find such a term in Russian, only some works on studfile and an automatic kostrubat translation on Wiki5, because of which I decided to translate the article on Wikipedia that I cited above and explain a little what this term means. The translation is amateur and free, if there are any mistakes, please correct them. I am translating for a link from my LeetCode to Russian extension and for those who come across such a term and decide to Google it in Russian. If there is a similar definition in Russian, but it is called differently, please write in the comments so that I can correct the article.

Clipping and searching – the method of solving optimization tasks proposed by Nimrod Megiddo in 1983[1].

The main idea of ​​the method is a recursive procedure, at each step of which the size of the input data is reduced (“cut off”) by a constant factor 0 < p < 1. This method is a form of the divide-and-conquer algorithm, where at each step the reduction occurs by a constant factor. Let n – Size of input data, T(n) – the time complexity of the “Cutting and searching” algorithm and S(n) – the time complexity of one cut-off. Then T(n) satisfies the following recurrence relation:

The recurrence relation above resembles the recurrence relation for binary search, but has a larger term S(n) compared to the constant term of binary search (T(n)=T(n/2)+O(1)). In “Cut and search” algorithms S(n) usually has at least linear complexity (since processing of the entire input is required). With this assumption, the relation has a solution T(n) = O(S(n)). This can be verified by applying the main theorem on recurrence relations or by noticing that the time for solving recursive subproblems decreases exponentially.

In particular, Megiddo himself used this approach in his linear time algorithm for a linear programming problem with a fixed number of variables and constraints.[2] and for the bounding sphere problem for a set of points in space[1].

A little explanation for now.

Clipping and searching is the optimization method we are looking for что-либо in большом объеме данныхat the same time cutting off a part of the options with a high probability не приведут к желаемому результату. This method saves time and resources, allowing you to focus on the right cases.

In the context of the Word Search task, let’s understand what this means: Что-либо – The word we are looking for. Большой объем данных is a matrix with letters. When recursively searching for a word, we “cut off” the cells that definitely will not help to find the word (не приведут к желаемому результату).

Solving the problem using pseudocode

Problem condition:

Given a symbol matrix board size m x n and a row wordreturn true, if word is in the matrix board.

A word can be made up of letters located in adjacent cells. Two cells are considered neighborsif they are horizontally or vertically apart from each other. In each word, each letter from the cell can be used only once. The first example from the task page:

Ввод: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Вывод: true

Let’s start the matrix visited the same size as i boardto track visited cells.

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

This code uses a recursive depth-first search method to check the existence of a word in the matrix. The use of clipping in the case consists in checking the conditions that may lead to the impossibility of constructing a word:

  • If the current cell does not correspond to the symbol of the searched word, we return false;

  • We check that the coordinates are within the boundaries of the board. If they go abroad, we return them false;

  • We check whether the current cell has already been visited. If it has already been visited, it indicates that we have already been this way, so we return false.

Checking these conditions significantly optimizes the time and memory complexity of the return search algorithm, it helps reduce the number of recursive calls and reduces the search space, which allows you to avoid excessive calculations.

At the end of the algorithm, after checking the correspondence of the current letter to the searched word in the cell of the matrix, as well as all the cut-off conditions, we check whether we have reached the end of the searched word (length k equal to the length of the word). If this condition is true, we have successfully found all the letters of the word in the matrix and the function returns trueindicating successful completion of the search.

  1. 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

  2. Nimrod Megiddo (1984) Linear Programming in Linear Time When the Dimension Is Fixed doi:10.1145/2422.322418

Related posts