Найти локальный минимум в n x n матрице в O (n) времени

Итак, это не мой домашний вопрос работы, но он взят из неклассифицированной домашней работы курса coursera по алгоритмам и структурам данных (которые теперь завершены).

Вам предоставляется n на n сетку различных чисел. Число является локальным минимумом, если оно меньше всех его соседей. (Сосед числа - это тот, что находится выше, внизу, слева или справа. В большинстве номеров есть четыре соседи, цифры на стороне имеют три, четыре угла - два.) Используйте алгоритм алгоритма разделения и покоя парадигма для вычисления локального минимума с использованием только O (n) сравнений между парами чисел. (Примечание: поскольку на входе есть n ² чисел, вы не можете позволить себе взглянуть на все из них. Подсказка: подумайте о том, какие типы повторений дадут вам желаемую верхнюю границу.)

Так как числа не в каком-либо порядке, я не вижу, как мы можем уйти с чем-либо, кроме сравнений O (n ²).

Ответ 1

Мы можем адаптировать слова как Джаред, посмотрев, как это может пойти не так.

Идея в этом ответе, которая является хорошей, - это "свернуть вниз". Это означает, что если вы находитесь на элементе, проверьте, является ли он локальным минимумом. Если это так, вы готовы; в противном случае, шаг к самому маленькому из его ближайших соседей. В конце концов, это должно завершиться, потому что каждый шаг относится к меньшему элементу и не может продолжаться вечно в конечном массиве.

Проблема с этим подходом заключается в том, что "перекатывание" может зависеть повсюду:

20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5

Если вы начинаете в левом верхнем углу и "свертываете вниз", вы увидите около половины элементов в массиве. Это слишком много, поэтому нам нужно немного ограничить его.

Начните с изучения среднего столбца и средней строки. Найдите наименьший элемент среди всех и начните там.

Сбросьте один шаг "под гору" оттуда, чтобы войти в один из четырех квадрантов. Вы войдете в один из квадрантов, потому что соседние элементы в среднем столбце и/или строке больше, поэтому только один из двух соседних квадрантов может быть "под гору".

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

Таким образом, в линейном времени мы определили квадрант, который должен содержать локальный минимум, и мы разрезаем n пополам. Теперь просто отчитайтесь.

Этот алгоритм принимает время 2n + 2n/2 + 2n/4 +..., что равно 4n, что равно O (n), поэтому мы делаем.

Интересно, что мы вообще не использовали "скатывание под гору", за исключением критической части: Доказательство того, что алгоритм работает.

[Обновление]

Как Инкассатор указывает на, этот ответ не совсем корректен, потому что после того, как вы "просто переучитесь", вы снова можете выкатиться из квадранта...

Самое простое исправление - найти наименьший элемент среди средней строки, среднего столбца и границы, прежде чем "скатиться вниз".

Ответ 2

Принятый ответ Nemo хорош, но не совсем корректен:

Таким образом, в линейном времени мы определили квадрант, который должен содержать локальный минимум, и мы разрезаем n пополам. Теперь просто отчитайтесь.

Я имею в виду бит "только рекурсия". Проблема в том, что мы не можем сделать этого напрямую, потому что на следующей итерации мы можем найти локальный минимум, который не является локальным минимумом для исходной сетки (x ниже означает некоторые произвольные большие числа):

 x  x 39  x  x 50  x  x  x  x  x
 x  x 38  x  x 49  x  x  x  x  x
37 36 33 34 35 48  x  x  x  x  x
 x  x 32  x  1 10  x  x  x  x  x
 x  x 31  x  x 47  x  x  x  x  x
46 45 30 44 43 60 51 52 53 54 55
 x  x  2  x  x 56  x  x  x  x  x
 x  x  x  x  x 57  x  x  x  x  x
 x  x  x  x  x 58  x  x  x  x  x
 x  x  x  x  x 59  x  x  x  x  x

Сначала итерацию мы находим как минимум среднюю и среднюю. Идем влево (как 1 меньше 10). Итак, наша следующая итерация находится в верхнем левом квадранте. Но теперь минимальная средняя строка и столбец будет 31 (или 30, если границы квадранта считаются ее частью). Затем вы сделаете вывод, что это локальный минимум. Но это не для полной сетки.

Мы можем исправить этот несчастный дефект различными способами. Я решил это так:

На каждой итерации в дополнение к самой сетке мы отслеживаем текущий минимальный кандидат (то есть 1 в примере выше после первой итерации, в начальном состоянии мы можем сказать, что минимальный кандидат равен плюс бесконечность). Мы вычисляем минимум средних строк и столбцов и сравниваем их с минимальным кандидатом. Если последнее меньше, мы возвращаемся в квадрант, содержащий минимальный кандидат. В противном случае мы забываем о предыдущем кандидате и только затем проверяем, является ли новый средний минимальный столбец/столбец минимальным. И если нет, то, как обычно, переходите к любому квадранту, который мы наклоняем от него (и отслеживаем нового минимального кандидата).

В качестве альтернативы вы можете изменить процедуру, описанную в эту предположительно лекцию MIT: на каждой итерации вместо просмотра средней строки/столбца вы можете посмотрите на среднюю строку/столбец и границу сетки. Тогда алгоритм снова правильный.

Вы выбираете, как вам нравится.

Ответ 3

Я думаю, что это действительно очень просто.

Превратите проблему в трехмерную, чтобы понять, почему работает алгоритм. Поместите матрицу на стол. Притворяются, что из каждой ячейки выходят столбы, а высота столба прямо пропорциональна его значению. Положите мяч на любой столп. Пусть мяч всегда падает на соседний столб, который является самой низкой высотой, пока он не достигнет локального минимума.

Ответ 4

Хорошо, вот как вы его разделяете и побеждаете.

1) Разделите n x n матрицу на четыре n/2 x n/2 подматрицы.

2) Продолжайте делить субматрицы рекурсивно, пока не получится матрица 2 x 2

3) Проверьте, не является ли какой-либо элемент матрицы 2 x 2 локальным минимумом.

Рекуррентное уравнение: T (n) = 4 * T (n/2) + O (1)

4 * T (n/2) для 4 n/2 x n/2 подматриц и O (1) для проверки, имеет ли 2 x 2 подматрица локальный минимум

Основная теорема утверждает, что это худшая оценка O (n ^ 2).

Но я думаю, что мы можем получить лучший случай O (n),

( "RED ALERT! --- ЛУЧШИЙ СЛУЧАЯ - БОГУС, ТОЛЬКО БОГУС --- КРАСНЫЙ АЛЕРТ!" ).

если мы выйдем из стека рекурсии после того, как мы нашли локальный минимум на шаге 3.

псевдокод:

private void FindlocalMin(matrix,rowIndex,colIndex,width){
    if(width == 1){ checkForLocalMinimum(matrix,rowIndex,colIndex); return;} //2x2 matrix
    FindlocalMin(matrix,rowIndex,colIndex,width/2);  
    FindlocalMin(matrix, (rowIndex + (width/2) + 1) ,colIndex,width/2);
    FindlocalMin(matrix,rowIndex, (colIndex + (width/2) + 1) ,width/2);
    FindlocalMin(matrix,(rowIndex + (width/2) + 1), (colIndex + (width/2) + 1) ,width/2);
}

private void checkForLocalMinimum(.........){
    if(found Local Minimum in 2x2 matrix){ exit recursion stack;} 
}

Вот java-реализация

Ответ 5

Извините, это просто вызвало мой интерес так долго. Я сомневаюсь в ответах. Вот почему.

Чтобы получить O (n), решение должно гарантировать, что мы никогда не вернемся в наш поиск, то есть с разворотом. Однако, поскольку числа все разные (на самом деле нечеткость делает проблему более жесткой), это может произойти.

Представьте себе винтовую лестницу, которая начинается в одном углу как самая высокая точка, а затем спирали внутрь и вниз. Если лестница квадратная, то центр - это только локальные минимумы, а также глобальные минимумы. В этом случае, поскольку мы начинаем центр, нам может просто повезти. Однако поперечное сечение лестницы может быть несимметричным, и в этом случае решение не будет работать. Потому что мы не можем избежать разворота во время нашего поиска.