Алгоритм SMAWK - SMAWK algorithm

В Алгоритм SMAWK является алгоритм для нахождения минимального значения в каждой строке неявно определенного полностью монотонного матрица. Он назван в честь инициалов его пяти изобретателей, Петр Шор, Шломо Моран, Алок Аггарвал, Роберт Уилбер и Мария Клаве.[1]

Вход

Для целей этого алгоритма матрица определяется как монотонная, если минимальное значение каждой строки встречается в столбце, который равен или больше столбца минимума предыдущей строки. Он полностью монотонен, если одно и то же свойство истинно для каждой подматрицы (определяемой произвольным подмножеством строк и столбцов данной матрицы). Эквивалентно, матрица полностью монотонна, если не существует подматрицы 2 × 2, минимумы строк которой находятся в верхнем правом и нижнем левом углах. Каждый Массив Монжа абсолютно монотонный, но не обязательно наоборот.

Для алгоритма SMAWK матрица для поиска должна быть определена как функция, и эта функция задается как входные данные для алгоритма (вместе с размерами матрицы). Затем алгоритм оценивает функцию всякий раз, когда ему нужно знать значение конкретной ячейки матрицы. Если эта оценка занимает О(1), то для матрицы с р ряды и c столбцы, время выполнения и количество оценок функции являются О(c(1 + журнал (р/c))). Это намного быстрее, чем О(р c) время наивного алгоритма, оценивающего все ячейки матрицы.

Метод

Основная идея алгоритма - следовать обрезать и искать стратегия, в которой решаемая проблема сводится к единой рекурсивный однотипная подзадача, размер которой в постоянный коэффициент меньше. Для этого алгоритм сначала предварительно обрабатывает матрицу, чтобы удалить некоторые из ее столбцов, которые не могут содержать минимум строки, используя куча на основе алгоритма, аналогичного алгоритму в Сканирование Грэма и все ближайшие меньшие значения алгоритмы. После этого этапа алгоритма количество оставшихся столбцов будет не более чем равным количеству строк. Далее алгоритм рекурсивно вызывает себя, чтобы найти минимумы строк четных строк матрицы. Наконец, путем поиска столбцов между положениями последовательных минимумов четных строк алгоритм заполняет оставшиеся минимумы в нечетных строках.

Приложения

Основные приложения этого метода, представленные в оригинальной статье Aggarwal et al. были в вычислительная геометрия, в поиске самой дальней точки от каждой точки выпуклого многоугольника и в поиске оптимальных охватывающих многоугольников. Последующие исследования обнаружили применение того же алгоритма в разбиение абзацев на строки,[2] РНК вторичная структура прогноз,[3] ДНК и белок выравнивание последовательностей,[4][5] построение коды префиксов,[6] и определение порога изображения,[7] среди прочего.

Рекомендации

  1. ^ Аггарвал, Алок; Клаве, Мария М.; Моран, Шломо; Шор, Петр; Уилбер, Роберт (1987), "Геометрические приложения алгоритма поиска матрицы", Алгоритмика, 2 (2): 195–208, Дои:10.1007 / BF01840359, МИСТЕР  0895444.
  2. ^ Уилбер, Роберт (1988), «Повторное обращение к проблеме вогнутой подпоследовательности наименьшего веса», Журнал алгоритмов, 9 (3): 418–425, Дои:10.1016/0196-6774(88)90032-6, МИСТЕР  0955150
  3. ^ Лармор, Лоуренс Л.; Шибер, Барух (1991), "Он-лайн динамическое программирование с приложениями для предсказания вторичной структуры РНК", Журнал алгоритмов, 12 (3): 490–515, Дои:10.1016 / 0196-6774 (91) 90016-Р, МИСТЕР  1114923.
  4. ^ Руссо, Луис М. С. (2012), "Свойства Монжа выравнивания последовательностей", Теоретическая информатика, 423: 30–49, Дои:10.1016 / j.tcs.2011.12.068, МИСТЕР  2887979.
  5. ^ Крошмор, Максим; Landau, Gad M .; Зив-Укельсон, Михал (2003), "Алгоритм субквадратичного выравнивания последовательностей для матриц неограниченной оценки", SIAM Журнал по вычислениям, 32 (6): 1654–1673 (электронный), CiteSeerX  10.1.1.57.8562, Дои:10.1137 / S0097539702402007, МИСТЕР  2034254.
  6. ^ Брэдфорд, Фил; Golin, Mordecai J .; Лармор, Лоуренс Л.; Риттер, Войцех (2002), «Оптимальные коды без префиксов для неравных буквенных затрат: динамическое программирование со свойством Монжа», Журнал алгоритмов, 42 (2): 277–303, CiteSeerX  10.1.1.45.5501, Дои:10.1006 / jagm.2002.1213, МИСТЕР  1895977.
  7. ^ Луесси, М .; Eichmann, M .; Schuster, G.M .; Кацаггелос, А. (2006), «Новые результаты по эффективной оптимальной многоуровневой обработке изображений», Международная конференция IEEE по обработке изображений, стр. 773–776, CiteSeerX  10.1.1.461.663, Дои:10.1109 / ICIP.2006.312426, ISBN  978-1-4244-0480-3.