Как использовать жадный алгоритм, чтобы найти неубывающую последовательность, ближайшую к данной?

20

a1,,an0laibi0lbib i O ( n 4 max(|a1b1|,,|anbn|)biO(nl4)

Я, честно говоря, понятия не имею, как вообще начать решать этот вопрос. Мне кажется, это вопрос динамического программирования, но профессор сказал, что это должно быть решено с использованием жадного алгоритма. Было бы очень признательно, если бы кто-то указал мне правильное направление, дав небольшой намек.

Аден Донг
источник

Ответы:

9

Начнем со следующего наблюдения:

Пусть обозначает максимум последовательности , а обозначает его минимум. Если , то выбор является оптимальным.с 1 , . , , , a n m i n a 1 = m a x b 1 = b 2 = . , , = b n = ( m a x + m i n ) / 2 maxa1,...,anmina1=maxb1=b2=...=bn=(max+min)/2

Почему это так? Итак, поскольку последовательность начинается с максимума, либо мы выбираем большое значение и страдаем большим отклонением от минимума последовательности (поскольку любое последующее значение должно быть больше или равно ), либо мы выбираем значение маленькое и страдаем от отклонение до . Среднее сводит к минимуму максимальное отклонение.b i b 1 b 1 m a xb1bib1b1max

Теперь мы можем попытаться обобщить это наблюдение для использования на общих последовательностях . Например, мы можем разбить любую последовательность на подпоследовательности, чтобы каждая из них начиналась с максимума соответствующей подпоследовательности.a1,...,an

Пример: разбивается на , и .((2,6,4,1,5,2,8,7,5,1)( 6 , 4 , 1 , 5 , 2 ) ( 8 , 7 , 5 , 1 )(2)(6,4,1,5,2)(8,7,5,1)

Учитывая это разбиение, теперь мы можем решить каждую из этих подпоследовательностей отдельно и получить присвоение , что, однако, может нарушить неубывающее условие. Это можно исправить без потери оптимальности.bi

Обратите внимание, что последняя подпоследовательность всегда содержит максимальный всей последовательности (в противном случае после нее будет другая подпоследовательность). Пусть - это значения, которые мы присвоили подпоследовательностям. Теперь, чтобы достичь в , мы начинаем со спины в и продвигаемся вперед. Если больше, чем , мы просто устанавливаем . Если оно меньше, мы сохраняем его. Затем мы продолжаем сравнивать с и так далее. Обратите внимание, что снижение любого до значенияш 1 , ш 2 , . , , , Ш K к ш 1 , . , , , w k w k w k - 1 w k w k - 1 : = w k w k - 2 w k - 1 w i w i + 1 w i w i + 1maxw1,w2,...,wkkw1,...,wkwkwk1wkwk1:=wkwk2wk1wiwi+1никогда не увеличивает отклонение, так как максимальное значение в подпоследовательности, назначенной с помощью , всегда ниже максимума в подпоследовательности, назначенной с помощью .wiwi+1

Этот алгоритм должен быть правильным, я думаю. Что касается времени работы, ключевым шагом является вычисление возрастающего максимума для подпоследовательностей, что возможно в ? Не уверен, где я .lO(n)l

сизигия
источник
2

Я собираюсь придумать вслух, просто прорабатывая подсказки, которые вы дали. Давайте перейдем к первоначальному намёку о том, что - это то, что вы должны попробовать в первую очередь. Я могу думать о жадном алгоритме, который имеет это время.O(nl)

часть времени сложность означает , что вы можете сохранить список подсчета каждого совпадения каждого значения . Это просто создать набор который отслеживает количество каждого в наборе. Вы можете создать список инициализации, отсканировав входную последовательность один раз.0 .. l Count = C 0 , , C l ll0..lCount=C0,,Cll

Вы можете отсканировать этот список в чтобы получить максимальное и минимальное значение. Если бы вы заполнили весь список этой средней точкой, ваша дисперсия была бы просто разницей от этого значения и максимума / мин. Это в основном ваш худший сценарий, давайте назовем его .b b wO(l)bbw

Так что проложите свой путь к слева. Вы можете удалить этот элемент из и получить минимальное / максимальное значение в . Теперь мы можем быть жадными. Мы не выбираем поскольку это заставляет весь оставшийся список увеличиваться (чтобы удовлетворить неубывающее требование) и, таким образом, увеличивает дисперсию. Минимальное значение, которое мы можем выбрать, это . Если находится в приемлемом диапазоне, мы выбираем его, если ниже диапазона, чем использовать минимум. Это минимизирует дисперсию в учетом известных ограничений. Count b [ i + 1 ] b [ n ] O ( l )biCountb[i+1]b[n]O(l) b [ i - 1 ] a i b ibi>bwb[i1]aibi

Это всего лишь идея, возможно, мне повезло, и она указывает вам правильное направление. Этот алгоритм может не работать (он подходит для моих нескольких простых тестов), но он соответствует приведенным подсказкам, поэтому, возможно, он полезен. Если все верно, легко заметить, что часть наверняка может быть перенесена в , даже дальше, я не уверен.O ( log l )O(l)O(logl)

эд-ка морт-ора-й
источник
2

Вот решение профессора, которое он называет «редукцией»: для каждого от до попытайтесь построить решение, если мы знаем, что отклонение меньше или равно . Первый , для которого решение может быть найдено минимальное отклонение. Мы можем найти решение, учитывая отклонение в времени. Таким образом, время работы . Затем вместо линейного поиска мы можем использовать бинарный поиск, чтобы определить наименьшее отклонение, для которого возможно решение. Это сокращает время выполнения до , что удовлетворяет требованию .i0liiO(n)O(nl)O(nlogl)O(nl4)

Аден Донг
источник
4
Так что был трюк ... Но меня больше заинтриговало "Мы можем найти решение, учитывая отклонение в O (n) времени" .. как этонеинтересная часть? O(nl4)
Джмад
@jmad Учитывая , для каждого j , возьмите b j как наименьшее значение, которое по крайней мере такое же большое, как все предыдущие b k , и которое не больше, чем i от a j . Если мы не можем найти такое значение, что это значит? Это означает , что предыдущий б т больше , чем я больше , чем в J . Таким образом, предыдущая т больше , чем 2 I больше , чем в J . Так что это значение меня было невозможно. Если вы пройдете через нijbjbkiajbtiajat2iajinзначения без застревания, как это, вы нашли решение для без возврата, во время O ( n ) . iO(n)
JWG
O (n log l) было бы сильным намеком на то, что вам нужно выполнить некоторый двоичный поиск в диапазоне от 0 до l.
gnasher729
0

Я думаю, что это должно быть выполнимо в O (N).

Возьмем аналогичную задачу. Для , 1 ≤ i ≤ n и d ≥ 0 найдите b i в не убывающем порядке, чтобы | a i - b i | d для всех i или покажи, что это невозможно. Это можно сделать в O (n), а с помощью бинарного поиска исходная проблема решается в O (n log l).aibi|aibi|d

Теперь, если существует i ≤ j такое, что a_i - a_j> 2d, то решения не существует (поскольку ).biaid,bjaj+d<ai2d+d=aidbi

Но если a_i - a_j ≤ 2d для всех i ≤ j, то я думаю, что решение всегда будет найдено. Поэтому все, что нам нужно сделать, это найти m = max (a_i - a_j) для всех i ≤ j и выбрать d = floor ((m + 1) / 2). Этот максимум можно найти в O (n).

gnasher729
источник
Интригующая идея! Я могу поверить, что что-то вроде этого может сработать, но кажется, что в конце вашего ответа есть большой пробел, и мне трудно заполнить детали. Есть ли у вас доказательство того, что если для всех i j, то решение всегда существует? Что еще более важно, как мы находим это? Оригинальный вопрос говорит, что мы должны найти б я . Даже если мы предположим , решение существует, у меня проблемы со зрением , как найти соответствующие б я «с. Можете ли вы уточнить это? aiaj2dijbibi
DW