Войти
Алгоритм SMAWK - это алгоритм для поиска минимального значения в каждой строке неявно определенной полностью монотонной матрицы. Он назван в честь инициалов его пяти изобретателей: Питер Шор, Шломо Моран, Алок Аггарвал, Роберт Уилбер и Мария Клаве.
Для целей этого алгоритма матрица определяется как монотонная, если минимальное значение каждой строки встречается в столбце, который является равно или больше столбца минимума предыдущей строки. Он полностью монотонен, если одно и то же свойство истинно для каждой подматрицы (определяемой произвольным подмножеством строк и столбцов данной матрицы). Эквивалентно, матрица полностью монотонна, если не существует подматрицы 2 × 2, минимумы строк которой находятся в верхнем правом и нижнем левом углах. Каждый массив Monge полностью монотонен, но не обязательно наоборот.
Для алгоритма SMAWK матрица для поиска должна быть определена как функция, и эта функция задается как входные данные для алгоритма (вместе с размерами матрицы). Затем алгоритм оценивает функцию всякий раз, когда ему нужно знать значение конкретной ячейки матрицы. Если эта оценка занимает O (1), тогда для матрицы с r строками и c столбцами время выполнения и количество оценок функции равны O (c (1 + log (r / c))). Это намного быстрее, чем время O (r c) наивного алгоритма, оценивающего все ячейки матрицы.
Основная идея алгоритма состоит в том, чтобы следовать стратегии сокращения и поиска, в которой проблема, которую необходимо решить, сводится к единственному рекурсивному однотипная подзадача, размер которой на постоянный коэффициент меньше. Для этого алгоритм сначала предварительно обрабатывает матрицу, чтобы удалить некоторые из ее столбцов, которые не могут содержать минимум строк, используя алгоритм на основе стека , аналогичный алгоритму в сканировании Грэма и все ближайшие алгоритмы меньших значений. После этого этапа алгоритма количество оставшихся столбцов будет не больше, чем количество строк. Затем алгоритм рекурсивно вызывает себя, чтобы найти минимумы строк четных строк матрицы. Наконец, путем поиска столбцов между положениями последовательных минимумов четных строк алгоритм заполняет оставшиеся минимумы в нечетных строках.
Основные применения этого метода, представленные в оригинальной статье Аггарвала и др. были в вычислительной геометрии, в поиске самой дальней точки от каждой точки выпуклого многоугольника и в поиске оптимальных охватывающих многоугольников. Последующие исследования выявили применение того же алгоритма в разбиении абзацев на строки, РНК вторичной структуре предсказании, ДНК и белке выравнивание последовательностей, построение префиксных кодов и пороговое значение изображения, среди прочего.
