Алгоритм по типу АЗС с минимальными затратами? Жадный или DP?

У меня есть массив n станций обслуживания D[] на шоссе, так что D[i] - это расстояние станции i от начала шоссе.

У меня также есть ряд затрат C[], так что C[i] - это стоимость обслуживания моего автомобиля на станции i.

Мне нужно отремонтировать мою машину на первой станции, и моя машина может проехать не более 100 миль между станциями.

Какой алгоритм является наиболее эффективным, чтобы добраться от начала шоссе до конца с наименьшими затратами (мне нужно знать, на каких станциях остановиться)? Мне удалось найти жадное решение для минимизации количества остановок, но с наименьшими затратами, я думаю, DP, с оптимальной подзадачей:

bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100)

и иметь отдельный массив last[j], который содержит последнюю станцию, на которой нужно остановиться, что было бы лучшей i из подзадачи выше.

Будет ли это правильным подходом или есть лучшее решение для Greedy / DP?


algorithm dynamic-programming greedy
person Anagha    schedule 27.01.2014    source источник
comment
Жадного решения не вижу. Повторение DP верное. Вы можете получить среду выполнения O(n) с монотонной очередью, которая позволяет вам найти минимум в O(1), который является оптимальным и также имеет низкий постоянный коэффициент. Это работает даже в том случае, если запас хода вашего велосипеда непостоянен.   -  person Niklas B.    schedule 27.01.2014
comment
@NiklasB. на самом деле его решение жадное, на каждой остановке он будет искать лучший вариант, используя только стоимость .. его решение работает нормально, за исключением того, что оно не оптимально, так как он не учитывает, сколько газа существует на каждом расстоянии и сколько он может повторное заполнение этой ценой усложняет проблему и делает более дешевую цену за единицу газа не всегда лучшим вариантом для остановки   -  person Khaled.K    schedule 27.01.2014
comment
@KhaledAKhunaifer, пожалуйста, прочтите мой вопрос внимательно, я не рассматриваю, сколько газа существует, потому что это не проблема заправки, а вариант. Это проблема станции обслуживания, когда я должен оплачивать фиксированные расходы C[i] каждый раз, когда я останавливаюсь на данной станции i.   -  person Anagha    schedule 27.01.2014
comment
@Anagha, как упоминает Никлас Б., вы можете вернуться назад от конечной станции, каждый раз проходя через каждую станцию, обновите минимальную стоимость, чтобы добраться до конечной станции с этой станции. Жадных здесь не вижу.   -  person Pham Trung    schedule 27.01.2014
comment
@Anagha Понятно, но вот худший вариант вашего жадного решения ... представьте, что заправочные станции имеют возрастающую стоимость C[i] > C[j] where i > j, это то место, где вы будете останавливаться на каждой станции на дороге   -  person Khaled.K    schedule 27.01.2014
comment
@KhaledAKhunaifer чувак, прочти вопрос. Упомянутый жадный алгоритм OP даже не учитывает затраты   -  person Niklas B.    schedule 27.01.2014
comment
@NiklasB. У меня также есть массив затрат C [], такой, что C [i] - это стоимость обслуживания моего автомобиля на станции i.   -  person Khaled.K    schedule 29.01.2014
comment
@Khaled: Кто-то из нас, должно быть, чего-то упускает: я смог найти жадное решение для минимизации количества остановок, но с наименьшими затратами, я думаю, DP. Вы говорите о решении DP? Потому что это доказуемо верно (это довольно легко доказать)   -  person Niklas B.    schedule 29.01.2014
comment
Существует фиксированная стоимость обслуживания за станцию ​​i, которую вы либо платите (в этом случае ваш газ заправлен, а вы платите C[i]), либо нет (в этом случае ваш газ не заправлен, и вы платите 0).   -  person Niklas B.    schedule 29.01.2014
comment
@NiklasB. Я думал, что он придумал хороший алгоритм, но его решение было жадным, когда на каждой остановке он смотрел на станции, которые находятся в пределах 100 км оттуда, и выбирал ту, которая имеет наименьшую стоимость, а затем с этой выбранной станции он повторяться .. если он пытается минимизировать общую стоимость, этот алгоритм будет наихудшим, потому что в моем сценарии он будет платить полную стоимость всех станций   -  person Khaled.K    schedule 29.01.2014
comment
@Khaled: Извините, я думаю, вы не понимаете алгоритм. bestcost[i] - это минимальная стоимость прибытия на D[i] И обслуживания на станции i. Очевидно, вы ДОЛЖНЫ заплатить C[i], если решите это сделать. Но это не означает, что этот подрезультат когда-либо использовался, поэтому, в частности, это НЕ означает, что мы используем станцию ​​в глобально оптимальном решении. У вас есть опыт динамического программирования?   -  person Niklas B.    schedule 29.01.2014
comment
@NiklasB. Проблема, которую я вижу, заключается в том, что если вы применяете bestcost[j] = min( 0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100), начиная со станции 0 .. у вас есть один путь, он линейный и детерминированный, операция min(bestcost[i]+C[j]) эквивалентна min(C[j])   -  person Khaled.K    schedule 29.01.2014
comment
@Khaled: j является константой, если вы вычисляете bestcost[j], поэтому min(C[j]) вообще не имеет смысла. операция min(bestcost[i]+C[j]) эквивалентна min(C[j]), это просто неверно, вы перебираете массив bestcost[j] для достижимых станций и берете минимум, затем вы добавляете C[j], потому что вы решили остановиться на j. у вас есть один путь, он линейный и детерминированный. Итак, итоговый путь может выглядеть так: остановка на станции 1, пропуск станции 2, пропуск станции 3, остановка на 4, остановка на 5, пропуск 6, остановка на 7. Что вы имеете в виду линейным и детерминированным?   -  person Niklas B.    schedule 29.01.2014
comment
@Khaled: Вот пример реализации, которая, возможно, поможет вас убедить: ideone.com/gm5eit   -  person Niklas B.    schedule 29.01.2014
comment
@NiklasB. Хорошая, это динамическое программирование. но тот алгоритм, который вы написали сами, а не тот, который мы видим в вопросе.   -  person Khaled.K    schedule 29.01.2014
comment
@KhaledAKhunaifer: Да, это так. Посмотрите внимательно. Строки с 14 по 24 реализуют точное повторение OP. bestcost[j] = min(0<i<j bestcost[i] + C[j] s.t. D[j]-D[i] <= 100) Если вы этого не видите, я сомневаюсь в вашей способности читать код ...   -  person Niklas B.    schedule 29.01.2014

Ответы (2)


arrow_upward
1
arrow_downward

Повторение лучше записать как

bestcost_serviced_at[j] =
  min(0<i<j: bestcost_serviced_at[i] + C[j] s.t. D[j]-D[i] <= 100)

поскольку повторение дает оптимальные затраты при условии, что транспортное средство фактически останавливается на станции j для обслуживания.

Тогда решение проблемы

min (j: bestcost_serviced_at[j] s.t. highway_end - D[j] <= 100)

Не думаю, что сработает жадный алгоритм.

person Antti Huima    schedule 27.01.2014

arrow_upward
0
arrow_downward

Я думаю, что ваш DP немного неполный, вот повторение DP, которое является более полным: -

if(highway_end-D[i]>100) {

   minCost[i] = min(0<i<j && D[j]-D[i] <= 100 : minCost[j]+C[i])
} 

else  minCost[i]  = C[i]     

minCost[i] = minimum cost to reach destination if you have filled up at i

Отсортируйте станции по расстоянию от старта и используйте DP для увеличения расстояния между станциями. Используйте отсортированный массив, чтобы найти более близкие соседние станции ‹= 100 миль.

Изменить: -

Это можно сделать за O(NlogN), используя минимальную кучу.

person Vikram Bhat    schedule 27.01.2014
comment
Может быть реализовано в O(n), если расстояния предварительно отсортированы - person Niklas B.; 27.01.2014
comment
@NiklasB. даже если он предварительно отсортирован, как удовлетворить D [j] -D [i] ‹= 100 и min (minCost [j]) в O (1) для каждой подзадачи? - person Vikram Bhat; 27.01.2014
comment
дерево сегментов дает вам O (log n) за переход. Как я уже упоминал, монотонная очередь с алгоритмом скользящего окна даже допускает постоянные временные переходы. Ответ напишу позже. - person Niklas B.; 27.01.2014
comment
См. Мой ответ на простой алгоритм O(n) для решения проблемы повторения, если вам интересно - person Niklas B.; 27.01.2014