Может ли кто-нибудь помочь решить эту сложную алгоритмическую проблему?

Я получил этот вопрос в интервью, и я не смог его решить.

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

Вопрос: Создайте алгоритм, чтобы узнать, с какой автозаправочной станции вы должны начать движение, чтобы завершить полный круг.

Как упражнение для меня, я бы перевел алгоритм на C #.

6 голосов | спросил Luis Valencia 15 22011vEurope/Moscow11bEurope/MoscowTue, 15 Nov 2011 14:46:10 +0400 2011, 14:46:10

6 ответов


23

(Обновление: теперь позволяет максимально увеличить размер газового бака)

Вы можете решить это в линейном времени следующим образом:

void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;

  // Make a round, without actually caring how much gas we have.
  int minI = 0;
  int minEndValue = 0;
  int gasValue = 0;
  for (int i = 0; i < n; i++)
  {
    if (gasValue < minEndValue)
    {
      minI = i;
      minEndValue = gasValue;
    }
    gasValue = gasValue + gasOnStation[i] - gasDrivingCosts[i];
  }

  if (gasValue < 0)
  {
    Console.WriteLine("Instance does not have a solution: not enough fuel to make a round.");
  }
  else
  {
    // Try a round.
    int gas = DoLeg(0, minI, gasTankSize);
    if (gas < 0)
    {
      Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
      return;
    }
    for (int i = (minI + 1) % n; i != minI; i = (i + 1) % n)
    {
      gas = DoLeg(gas, i, gasTankSize);

      if (gas < 0)
      {
        Console.WriteLine("Instance does not have a solution: our tank size is holding us back.");
        return;
      }
    }
    Console.WriteLine("Start at station: " + minI);
  }
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}

Во-первых, мы рассмотрим случай, когда у нас нет максимального количества бензобака.

По сути, в первом for-loop мы просто ездим по кругу, не заботясь, если наш топливный бак имеет отрицательное топливо или нет. Дело в том, что независимо от того, где вы начинаете, разница между тем, сколько в вашем топливном баке в начале (0) и в конце, одинаково.

Поэтому, если мы закончим с меньшим количеством топлива, чем мы начали (так меньше 0), это произойдет независимо от того, где мы начнем, и поэтому мы не сможем пройти полный круг.

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

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

Теперь мы рассмотрим версию, где наш бензобак может содержать только столько газа.

Предположим, что наш начальный тест (описанный выше) мы выяснили, что весь круг невозможен. Предположим, что мы начинаем с бензоколонки i , мы танкуем на бензоколонке j , но наш бензобак заканчивается полным, поэтому мы пропускаем какой-то дополнительный газ, который станция имеется в наличии. Затем, до того, как мы доберемся до станции k , у нас не будет достаточного количества топлива из-за газа, который мы пропустили.

Мы утверждаем, что в этом случае это закончится тем, что вы начнете. Предположим, что мы начинаем со станции l .

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

Если l не находится между j и k , то мы либо остановимся (долго) до того, как получим j , или мы достигаем j с не более чем полным баком, а это значит, что мы не будем делать это k . В любом случае это плохо.

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

ответил Alex ten Brink 15 22011vEurope/Moscow11bEurope/MoscowTue, 15 Nov 2011 22:34:22 +0400 2011, 22:34:22
9

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

Затем вы можете использовать адаптацию Dijkstra для ее решения -> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

ответил Daniel Scocco 15 22011vEurope/Moscow11bEurope/MoscowTue, 15 Nov 2011 14:56:34 +0400 2011, 14:56:34
5

Моим первым ответом было бы: «Требования кажутся неполными, вы уверены, что хотите, чтобы я написал код только на основе этих требований, мы сделаем их по мере того, как мы идем, или вы хотите, чтобы моя помощь соответствовала требованиям прежде чем мы разработаем программное обеспечение? ».

Неполные требования, как указано в других вопросах, Емкость автомобиля. Конечная точка - это начальная точка или станция до начальной точки. (Я думаю, что вы отвечаете на это в своем комментарии «полный полный круг означает end = start, в этом случае. Я бы уточнил это, поскольку он не является явным) Вопрос подразумевает, что есть одно и только одно решение, это правильно.

Другие вопросы Является ли выполнение алгоритма проблемой, или по-другому, каков бюджет для этого проекта.

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

ответил mattnz 16 32011vEurope/Moscow11bEurope/MoscowWed, 16 Nov 2011 01:45:50 +0400 2011, 01:45:50
5

Мне кажется, что в заданной викторине отсутствуют некоторые важные части. Однако в моих рассуждениях я бы использовал следующие предположения:

  • Автоцистерна имеет неограниченную топливную емкость.
  • Можно перемещаться только по часовой стрелке
  • Автомобиль начинается с 0 газа
  • Автомобиль должен заканчиваться на той же АЗС

Учитывая эти предположения, задача может быть легко грубо вынуждена с помощью O (n ** 2) сложности, пытаясь все автозаправочные станции.

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

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

Второй шаг - применить алгоритм максимальной подпоследовательности. Алгоритм основан на двух предположениях:

  • , если счетчик газа опустился ниже 0, что всегда лучше перезапустить с текущей АЗС
  • в противном случае лучше просто заполнить резервуар, так как здесь больше 0 газа

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

Третий шаг - убедиться, что цель достижима с заданным количеством топлива и заданной начальной станцией, сложностью o (n)

ответил Valera Kolupaev 16 32011vEurope/Moscow11bEurope/MoscowWed, 16 Nov 2011 01:48:11 +0400 2011, 01:48:11
4

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

На самом деле я считаю, что во время интервью это слишком сложно.

Приведенная иллюстрация показывает общую идею. Переменная x представляет текущий исследуемый узел. введите описание изображения здесь>> </p>

<p> Используйте эту формулу, если вы используете первый узел. </p>

<p> <img src =

ответил NoChance 15 22011vEurope/Moscow11bEurope/MoscowTue, 15 Nov 2011 20:24:33 +0400 2011, 20:24:33
1

Немного поздно, но я бы предложил метод проб и ошибок. (Я не рассматриваю контекст интервью и вопрос о разъяснении требований.)

Начнем с станции k и дойдем до самой дальней станции. Если мы снова вернемся к N + k = k (мы находимся в модульной арифметике по модулю N , поэтому 0 = N , 1 = N + 1 и т. д.), то мы преуспели.

Но предположим, что мы не сможем снова достичь k , но только l с k <= l & Lt; N + к . Плохой. Мы должны были начать работу до k . Попробуем от k-1 . Если мы не сможем достичь k , попробуйте выполнить k-2 , k-3 , ...

Есть две возможности:

(1) К несчастью, мы не можем достичь k из k-1 , из k-2 , ... и, наконец, из kN = k . Мы не смогли добиться успеха, мы пробовали все возможные стартовые автозаправочные станции дороги.

(2) Или мы найдем a k ' k , что дает нам достаточно газа для достижения k . Из k мы достигаем l и, возможно, даже l '> l (если бы у нас было достаточно газа на станции k ). Возможно, мы сможем снова достичь k ': нам удалось (a) . Если это не так, [k ', l'] , тем не менее, является надлежащим надмножеством [k, l] , потому что k ' & Lt; k и l '> = l (b) .

Если мы не обескуражены, то мы можем применить тот же метод снова и снова (сохраняя границу N + k ), и мы найдем последовательность маршрутов, каждый из которых будет длиннее (имеет больше заправочных станций), чем предыдущие. Пока мы не выполним условие (1) (отказ) или условие (2) (a) (успех).

Когда мы думаем о кодировании этого простого алгоритма, мы видим, что стоимость маршрута от k до l вычисляется только один раз. Поэтому нам просто нужно вычислить стоимость новой части маршрута (от k ' до k и от l до l ') на каждом шаге. Я думаю, что это достаточно быстро.

Примечание : как указано в некоторых других ответах, эта проблема представляет собой простую версию более сложной задачи, которая включает в себя графики, см. https://cs.stackexchange.com/questions/25906/understanding-an-algorithm-for-the-gas-station-problem .

Надеюсь, что это поможет.

EDIT : вот реализация вышеупомянутого решения с ограниченным газовым баком. Он использует только один цикл, поэтому он немного медленнее, когда на станциях недостаточно газа, но быстрее в любом другом случае. Я уверен, что это более понятно, чем буквальное объяснение.

int FindStartingPointInOneLoop(int[] gasOnStation, int[] gasDrivingCosts, int gasTankSize)
{
  // Assume gasOnStation.length == gasDrivingCosts.length
  int n = gasOnStation.length;
  bool move_forward = true;
  int k = 0;
  int l = 0;
  int gas = 0;
  while (true) {
    if (move_forward) { // try to move forward
      gas = DoLeg(gas, l, gasTankSize);
      if (gas < 0) { // we're out of gas : let's try a new start
        move_forward = false;
      }
      l = (l+1) % n;
    } else { // try to start from a previous gas station
      k = (k-1) % n;
      if (k == 0) { // that was a complete round without any adequate start
        Console.WriteLine("Instance does not have a solution.");
        return -1;
      }
      gas = DoLeg(gas, k, gasTankSize);
        if (gas >= 0) { // we reached our start point, let's try to move forward with the optional extra gas
          move_forward = true;
      }
    }
    if (l == k && gas >= 0) { // we joined "head" and "tail"
      return k;
    }
  }  
}
int DoLeg(int gas, int i, int gasTankSize)
{
  gas += gasOnStation[i];
  if (gas > gasTankSize) gas = gasTankSize;
  gas -= gasDrivingCosts[i];
  return gas;
}
ответил jferard 1 ThuEurope/Moscow2016-12-01T22:52:13+03:00Europe/Moscow12bEurope/MoscowThu, 01 Dec 2016 22:52:13 +0300 2016, 22:52:13

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132