Алгоритм движения грузовика по кругу заправок

Question

У вас есть грузовик, движущийся по круговой дорожке, а заправочные станции расположены по кругу Каждая станция имеет ограниченное количество газа. Бензобак на грузовике бесконечно большой. Расстояние между заправками требует определенного количества газа для прохождения. Вы можете двигаться только в одном направлении.

Какой алгоритм использовать? На какой заправке вы начинаете? Можете ли вы пройти весь путь до станции старта и обратно?

Answer 1

Да O (n) возможно. Определенно не TSP.

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

Требование & Sigma; x _i & ge; 0 (достаточно газа, чтобы пройти полный круг).

Рассмотрим S _i = x ₁ + x ₂ + ... + x _i

Обратите внимание, что S _n & ge; 0.

Теперь выберите наименьшее (или даже самое большое, что будет делать, чтобы было проще написать код) k, так что S _k - наименьшее, и начните со станции рядом с ним.

Теперь для k j - S _k & ge; 0.

за 1 & le; j & le; k, у нас есть газ в баке = x _{k + 1} + .. + x _n + x ₁ + x ₂ +. . + x _j = S _n - S _k + S _j & ge; 0.

Таким образом, начиная с k + 1, на каждой станции будет накоплено достаточно газа, чтобы добраться до следующей станции.

// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
    int min_S=INT_MAX, S=0, position=0;
    for(int i=0;i<gas.size();i++)
    {
        S += gas[i] - cost[i];
        if(S<min_S)
        {
            min_S = S;
            position = (i+1) % gas.size();
        }
    }
    if(S>=0)
        return position;
    else
        return -1;
}

Answer 2

Вот подход, который работает в O(n) времени и O(1) пространстве (в отличие от O(n) пространства для ответа Арьябхатты).

Начните с любой станции, назовите ее станцией 0 и двигайтесь вперед, пока не закончится бензин.Если у вас нет бензина, готово.В противном случае, если вы выбежали между станциями k и k + 1, начните снова со станции k + 1.Запишите, если вы снова передадите 0, и если после этого у вас закончится, это невозможно.

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

Вот алгоритм, заданный для массивов P (бензин) и D (расстояние):

int position = 0;
int petrol = P[0];
int distance = D[0];

int start = 0;
while (start < n) {
    while (petrol >= distance) {
        petrol += P[++position % N] - distance;
        distance = D[position % N];
        if (position % N == start)
            return start;
    }
    start = position;
    petrol = P[start];
}
return -1;

Answer 3

Пусть cost будет массивом затрат на следующую станцию, а gas будет массивом того, сколько топлива мы можем заправить

Мы вычислим разницу между gas[i] и cost[i],называется diff, где i - текущая заправка, в которой мы находимся.

Если cost[i] > gas[i] (или diff < 0), это означает, что нам нужно иметь как минимум cost[i] - gas[i] топлива при прибытии на станцию ​​iчтобы добраться до следующей остановки, я + 1. Если cost[i] <= gas[i] (diff >= 0), это допустимая отправная точка, потому что мы можем начать без газа, заправиться и отправиться на следующую станцию.В худшем случае мы дойдем до следующей остановки с пустым баком.В лучшем случае у нас останется запас топлива, когда мы достигнем i + 1 (diff > 0)

На самом деле нам не нужно начинать с одной станции, пройти через n автозаправочных станций, чтобы выяснить, есть лидействительный тур!Пока суммированное топливо> = итоговая стоимость, будет действительный тур.Так что нам просто нужно сделать O (n) проход массивов

Дополнительный анализ:

Case1: Tank опустится ниже 0

Это будетпроизойдет только на остановке, где diff < 0.После этого может быть другая отправная точка, которая собирает достаточно топлива после прохождения одного раунда, чтобы пройти эту станцию.Однако все те станции, которые мы прошли ранее, не помогут, поэтому нам не нужно их рассматривать (см. Пояснение к случаю 2).

Случай 2: танк в настоящее время> = 0, но мы столкнулись с другой действительной отправной точкой

Мы можем смело игнорировать это, потому что:

A ——B —— C. Если B может достичь C, а A может достичь B, то A может достичь C.

Случай 3: танк в настоящее время> = 0, недопустимая начальная точка

Продолжить переход к следующему

Случай 4: удалось достичь исходной начальной точки!

Ууу!

def find_starting_station(gas, cost):
    sum_gas = sum_cost = tank = start = 0

    for i in range(0, len(gas)):
        sum_gas += gas[i]
        sum_cost += cost[i]
        tank += gas[i] - cost[i]

        if tank < 0:
            tank = 0
            start = i+1

    if sum_gas < sum_cost: 
        return -1 

    return start

Answer 4

Это в основном проблема максимальной суммы подмассива. С другой стороны, мы можем взглянуть на это с несколько иной точки зрения. Давайте выясним, где у нас будет самый большой дефицит топлива, если мы начнем путешествие с самой первой заправки. Так как мы знаем, что достижение этой точки потребует большую часть топлива, мы можем сделать вывод, что грузовик должен стартовать в этой точке, чтобы минимизировать отрицательный баланс топлива. Ниже приведено решение для программы драйвера со сложностью O (N) по времени и пространству O (1), и никакой DP не требуется, поскольку все выполняется за один проход и используется только два целых числа для хранения индекса начальной точки его значение (хотя это необходимо только для печати).

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <vector>
#include <algorithm>

using namespace std;

int gasoline[] = {8, 6, 30, 9, 15, 21, 2, 18};
int stations[] = {15, 8, 2, 6, 18, 9, 21, 30};

int rnd_num(const int& low, const int& high)
{
    int rndnum = (int) (((double) rand() / (double) RAND_MAX) * (high - low + 1) + low);
    return rndnum;
}

void swap(int data[], const int& idxlow, const int& idxhigh)
{
    int tmp = data[idxlow];
    data[idxlow] = data[idxhigh];
    data[idxhigh] = tmp;
}

void print_array(const char* label, int data[], int size)
{
    printf("%-10s: ", label);
    for (int i = 0; i < size; ++i){
        printf("%-3d ", data[i]);
    }
    printf("\n");
}

void print_vector(const char* label, const vector<int>& data)
{
    printf("%-10s: ", label);
    for (vector<int>::size_type i = 0; i < data.size(); ++i){
        printf("%-3d ", data[i]);
    }
    printf("\n");
}

void shuffle(int data[], int size)
{
    for (int i = 0; i < size - 1; ++i){
        int idx = rnd_num(i + 1, size - 1);
        swap(data, i, idx);
    }
}

void run(int gas[], int dist[], int size)
{
    vector<int> path;
    int diff = 0, vidx, minidx = 0, minval = gas[0] - dist[0];

    path.resize(size);

    for (int i = 0; i < size; ++i) {
        diff += gas[i] - dist[i];
        if (i == size - 1){
            vidx = 0; //path[0] = diff;
        }
        else {
            vidx = i + 1; //path[i + 1] = diff;
        }

        path[vidx] = diff;
        if (diff < minval) {
            minval = diff;
            minidx = vidx;
        }
    }

    print_vector("PATHS   ", path);
    printf("MINIDX: %d\nMINVAL: %d\n", minidx, minval);
}

int main()
{
    int size = sizeof(stations)/sizeof(stations[0]);
    srand((unsigned)time(NULL));

    shuffle(gasoline, sizeof(gasoline)/sizeof(gasoline[0]));
    shuffle(stations, sizeof(stations)/sizeof(stations[0]));

    print_array("GASOLINE ", gasoline, sizeof(gasoline)/sizeof(gasoline[0]));
    print_array("STATIONS ", stations, sizeof(stations)/sizeof(stations[0]));

    run(gasoline, stations, size);

    return 0;
}

Answer 5

Решение этой проблемы основано на жадном алгоритме. Он основан на следующих двух наблюдениях.

1. если общая стоимость> стоимости газа, для завершения круга должен быть начальный индекс, иначе - нет;
   

2. относительно индекса i, если из i, j является первым индексом, которого мы не можем достичь, то любой индекс от i до j не может быть начальным индексом.

Для более подробного объяснения взгляните на следующую ссылку - Проблема с АЗС.

Answer 6

Вот мое решение на python. Дополнение к другому объяснено, как только мы сохраняем переменную для расчета потребности для предыдущих станций, а когда мы находимся в конце массива, мы просто проверяем, превышает ли наш остаток эту потребность, и возвращаем соответственно.

    if not gas or not cost:
        return - 1

    index = 0
    start = 0
    total = 0
    need = 0
    while index < len(gas):
        # If we can travel without any leftover.
        # What is our status since start, if total is
        # below zero that means we are in a worse situation
        # then we were.
        total += gas[index] - cost[index]
        if total < 0 :
            need -= total
            start = index + 1
            total = 0
        index += 1

    if total - need >= 0:
        return start
    else:
        return -1

Answer 7

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

    start = 0
    end = start
    amount = 0
    for i in range(n):
        if amount > 0:
            amount += (gas[end] - cost[end])
            end = (end + 1) % n
        else:
            start = (start - 1 + n) % n
            amount += (gas[start] - cost[start])

    if amount >= 0: return start    
    return -1

`