Алгоритм SMAWK
Алгоритм SMAWK — это алгоритм поиска минимального значения в каждой строке неявно определенной полностью монотонной матрицы . Он назван в честь инициалов пяти его изобретателей: Питера Шора , Шломо Морана , Алока Аггарвала, Роберта Уилбера и Марии Кло . [1]
Вход
[ редактировать ]Для целей этого алгоритма матрица считается монотонной, если минимальное значение каждой строки находится в столбце, который равен или превышает столбец минимума предыдущей строки. Он полностью монотонен, если одно и то же свойство справедливо для каждой подматрицы (определяемой произвольным подмножеством строк и столбцов данной матрицы). Эквивалентно, матрица является полностью монотонной, если не существует подматрицы 2 × 2, минимумы строк которой находятся в верхнем правом и нижнем левом углах. Каждый массив Монжа полностью монотонен, но не обязательно наоборот.
Для алгоритма SMAWK искомая матрица должна быть определена как функция, и эта функция задается в качестве входных данных алгоритма (вместе с размерами матрицы). Затем алгоритм оценивает функцию всякий раз, когда ему необходимо узнать значение конкретной ячейки матрицы. Если эта оценка занимает O ( 1 ), то для матрицы с r строками и c столбцами время выполнения и количество оценок функции равны O ( c (1 + log( r / c ))). Это намного быстрее, чем O ( rc время ) простого алгоритма, который оценивает все ячейки матрицы.
Метод
[ редактировать ]Основная идея алгоритма состоит в том, чтобы следовать стратегии сокращения и поиска , в которой решаемая проблема сводится к одной рекурсивной подзадаче того же типа, размер которой меньше в постоянный коэффициент. Для этого алгоритм сначала предварительно обрабатывает матрицу, чтобы удалить некоторые из ее столбцов, которые не могут содержать минимум строки, используя алгоритм на основе стека , аналогичный алгоритму сканирования Грэма и всех алгоритмов ближайших меньших значений . После этого этапа алгоритма количество оставшихся столбцов будет не более чем равно количеству строк.Затем алгоритм рекурсивно вызывает себя, чтобы найти минимумы четных строк матрицы. Наконец, просматривая столбцы между позициями последовательных минимумов четных строк, алгоритм заполняет оставшиеся минимумы в нечетных строках.
Приложения
[ редактировать ]Основные применения этого метода представлены в оригинальной статье Aggarwal et al. были в вычислительной геометрии , в поиске самой дальней точки от каждой точки выпуклого многоугольника и в поиске оптимальных охватывающих многоугольников. Последующие исследования нашли применение того же алгоритма для разбиения абзацев на строки . [2] РНК , вторичной структуры предсказание [3] ДНК и белков Выравнивание последовательностей , [4] [5] построение префиксных кодов , [6] и пороговая обработка изображений , [7] среди других.
Ссылки
[ редактировать ]- ^ Аггарвал, Алок; Клове, Мария М .; Моран, Шломо ; Шор, Питер ; Уилбер, Роберт (1987), «Геометрические приложения алгоритма матричного поиска», Algorithmica , 2 (2): 195–208, doi : 10.1007/BF01840359 , MR 0895444 .
- ^ Уилбер, Роберт (1988), «Возвращение к проблеме вогнутой подпоследовательности наименьшего веса», Journal of Algorithms , 9 (3): 418–425, doi : 10.1016/0196-6774(88)90032-6 , MR 0955150
- ^ Лармор, Лоуренс Л .; Шибер, Барух (1991), «Онлайн-динамическое программирование с приложениями для предсказания вторичной структуры РНК», Journal of Algorithms , 12 (3): 490–515, doi : 10.1016/0196-6774(91)90016-R , МР 1114923 .
- ^ Руссо, Луис М.С. (2012), «Свойства Монжа выравнивания последовательностей», Theoretical Computer Science , 423 : 30–49, doi : 10.1016/j.tcs.2011.12.068 , MR 2887979 .
- ^ Крошмор, Максим; Ландау, Гад М.; Зив-Укельсон, Михал (2003), «Алгоритм субквадратичного выравнивания последовательностей для неограниченных оценочных матриц», SIAM Journal on Computing , 32 (6): 1654–1673 (электронный), CiteSeerX 10.1.1.57.8562 , doi : 10.1137/S0097539702402007 , МР 2034254 .
- ^ Брэдфорд, Фил; Голин, Мордехай Дж.; Лармор, Лоуренс Л .; Риттер, Войцех (2002), «Оптимальные коды без префиксов для неравной стоимости букв: динамическое программирование со свойством Монжа», Journal of Algorithms , 42 (2): 277–303, CiteSeerX 10.1.1.45.5501 , doi : 10.1006/ ягм.2002.1213 , МР 1895977 .
- ^ Луесси, М.; Эйхман, М.; Шустер, генеральный директор; Кацаггелос, АК (2006), «Новые результаты по эффективной оптимальной многоуровневой пороговой обработке изображений», Международная конференция IEEE по обработке изображений , стр. 773–776, CiteSeerX 10.1.1.461.663 , doi : 10.1109/ICIP.2006.312426 , ISBN 978-1-4244-0480-3 .