Вариант алгоритма кратчайшего пути Дейкстры

Я застрял в этой проблеме (мое решение слишком медленное). Я опишу проблему, а затем свое решение.

Проблема: учитывая N станцию, каждая из которых находится в позиции x_i в числовой строке, мы хотим переместить робота с первой станции на последнюю (станции сортируются в неубывающем x_i порядке) в самая низкая денежная стоимость. У нас есть робот, который начинает работу с максимально заряженной батареей с K (не обязательно целыми) единицами мощности и может перемещать E (не обязательно целых) единиц длины на единицу затраченной энергии. На любой станции между первой и последней станциями мы можем подзарядить. Каждая станция взимает одинаковую фиксированную ставку F долларов за начало зарядки плюс c_i долларов за единицу восполненной мощности. Робот ТОЛЬКО может заряжаться, если его мощность в данный момент равна или ниже K/2 ИЛИ, он не может добраться до следующей станции без зарядки; каждый раз, когда робот заряжается, он должен заряжаться до 100% (т.е. K).

Мое решение: я почти уверен, что это вариант задачи кратчайшего пути, за исключением того, что мы оптимизируем денежные затраты. Я использую Dijkstra SSSP. Однако для каждого штата нам необходимо отслеживать как денежные затраты, так и оставшуюся энергию, потому что повышение затрат на более раннем этапе с помощью зарядки на дешевой станции может быть лучше, чем экономия ваших денег до конца. Поэтому вместо того, чтобы поддерживать cost[i]=cheapest known way to get to station i, я поддерживаю cost[i][energy]=cheapest known way to get to station i with a certain energy. В очереди приоритетов я упорядочиваю состояния по стоимости только потому, что не уверен, что есть способ создать эвристику как для стоимости, так и для оставшейся энергии. Этот алгоритм очень медленный в некоторых тестовых примерах, потому что если E и K были большими, то каждая станция потенциально могла бы перемещаться к каждой станции перед ней, создавая массивный график. Я думаю, что мне нужно сократить границы поиска, но я не знаю, как это сделать. Любые идеи?


algorithm shortest-path dijkstra
person user4272934    schedule 20.11.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Двигайтесь назад по станциям. Для станции i рассмотрите все станции j > i, до которых вы можете добраться оттуда (вы уже вычислили их оптимальную стоимость). Выберите среди них оптимальное.

В псевдокоде:

opt[N-1] = 0                                        // cost of the last station is 0
for i = N-2 down to 0                               // loop backwards over the stations
    opt[i] = infinity
    for j = i+1 to N-1 where (x_j - x_i) * E <= K   // loop over all next stations that can be reached without a flat battery
        energyToJ = (x_j - x_i) * E
        if (energyToJ >= K/2                        // we are allowed to recharge
          or j == N-1                               //  or we cannot reach the next station because there is none
          or x_{j+1} - x_i) * E > K)                //   or because it is too far
            costJ = F + energyToJ * c_j + opt[j]    // total cost via j is cost to j + cost from j
            if (costJ < opt[i])                     // keep track of the optimal cost
                opt[i] = costJ                      

return opt[0]

изменить

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

От станции i вы можете перейти непосредственно к каждой станции j, для которой выполняется одно из следующих условий:

  • K/2 <= x_j - x_i <= K
  • 0 <= x_j - x_i < K/2 и нет j' > j, для которого x_j' - x_i <= K

Создайте граф с N вершинами, по одной для каждой станции. Существует направленная кромка e_ij от станции i к станции j тогда и только тогда, когда выполняется одно из двух вышеуказанных условий. Вес e_ij - это просто стоимость подзарядки, которая составляет F + (x_j - x_i) * c_j.

Теперь вы можете просто запустить Дейкстру на этом графике, чтобы найти наиболее экономичный способ добраться до конечной станции. Причина, по которой нам не нужно отслеживать расстояние и деньги, заключается в том, что расстояние уже закодировано в структуре графа: ребра графа - это в точности все возможные перемещения от одной станции к Другая.

person Vincent van der Weele    schedule 20.11.2014
comment
Мы еще не рассмотрели динамическое программирование в классе, и это часть нашего модуля хеширования / графиков / теории чисел. Инструктор также явно упомянул очереди с приоритетом. - person user4272934; 20.11.2014