Поиск динамического алгоритма для определения оптимальной последовательности

Это домашнее задание, данное в классе, и мне было интересно, могу ли я получить некоторую помощь.

Проблема в том, что есть старик. А он в парке. Парк состоит из c_1, c_2, c_3, ....c_n скамеек на длинном одиночном маршруте, где c_1 находится ближе всего к старику, а c_n — последняя скамья, на которой старик хочет сесть.

В идеале он может пройти 120 футов без посторонней помощи. Однако, если он проедет больше 120 футов, он быстро устанет, а если он проедет меньше, у него будет недостаток времени, чтобы сидеть на скамейке и вставать. Таким образом, за каждую прогулку штраф за прогулку будет равен (120-x)^4, где x — это продолжительность прогулки, пройденной до сих пор после того, как он в последний раз отдыхал на скамейке.

Если скамейки расположены через каждые 120 футов друг от друга, это не даст ему никакого штрафа, поскольку он может просто отдохнуть на каждой скамейке, с которой столкнется, и это составит 120 футов перемещения с нулевым штрафом. Очевидно, он может пропустить скамью, если считает, что проехал не 120 футов, а только 10 или 20 футов.

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

Как вы думаете, можно ли добиться большей временной сложности, чем O (n ^ 2)? Я думаю, что это очень похоже на проблемы с монетами или проблемы с подсчетом очков в американском футболе, но его штраф «(120-x) ^ 4» за каждое перемещение между двумя скамейками вызывает у меня головную боль.


algorithm dynamic-programming
person user482594    schedule 21.02.2012    source источник
comment
Я помню подобный вопрос здесь около года назад, но я не могу его найти. :(   -  person biziclop    schedule 22.02.2012
comment
Я нашел очень похожую проблему на stackoverflow.com/questions/4950956/ и это мне очень помогло   -  person user482594    schedule 22.02.2012

Ответы (2)


arrow_upward
0
arrow_downward

Давно я ничего не делал с динамическим программированием, но я попробую.

Пусть P[i] будет минимальным штрафом, начиная со скамейки c_i.

Пусть cost(i) будет штрафом за старт со скамейки c_i и переход на c_n. Для i=n это будет 0, иначе (120-x)^4, где x будет расстоянием между скамейками.

for i = n to 1
    P[i] = cost(i)
    for j = i + 1 to n
        P[i] = min(P[i], P[j])

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

Это работает с временной сложностью O (n ^ 2).

person Lester    schedule 21.02.2012
comment
Да, это то, что я узнал до сих пор, но мне было интересно, смогу ли я сделать это за время O (n log n) с помощью мемоизации. - person user482594; 22.02.2012
comment
Я думаю, что может быть оптимизация с мемоизацией во втором цикле. Создавая штрафы по принципу «снизу вверх», последней скамейке запасных не нужно было бы рассчитывать все возможные штрафы. - person user482594; 22.02.2012

arrow_upward
0
arrow_downward

Другое решение состоит в том, чтобы построить граф с каждым стулом в качестве узла. Узлы i и j (ij), если расстояние между ними меньше или равно 120 футам. Каждое ребро взвешивается в соответствии со штрафной функцией.

Теперь найдите кратчайшее расстояние между начальным и конечным узлами.

Если граф разреженный (т. е. скамейки расположены редко), вы можете достичь O (nlogn), предполагая, что количество ребер равно O (n).

person ElKamina    schedule 21.02.2012
comment
Если бы скамья не была разреженной, было бы O (n ^ 2) ребер? - person user482594; 22.02.2012