Минимальное количество остановок на вокзале

Во-первых, спросите, можете ли вы вернуться назад. Это звучит так, как будто вы не можете, но как представлено здесь (что может не отражать вопрос, как вы его получили), проблема никогда не дает явного направления для любого из этих поездов. (Я вижу, теперь вы отредактировали свой вопрос, чтобы сказать, что вы не можете вернуться назад.)

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

Предположим, что вы находитесь на остановке s, и поезд с наивысшим номером, который останавливается в вашем текущем местоположении и не перегружается, - это поезд k. Путешествие один раз на поезде k приведет вас к остановке s + 2^(k-1). Нет более быстрого способа добраться до этой остановки, и нет способа пропустить эту остановку - никакие поезда с более низким номером не пропускают ни одну из остановок поезда k, и никакие поезда с более высоким номером не останавливаются между остановками поезда k, поэтому вы не можете сесть на поезд с более высоким номером, прежде чем вы туда доберетесь. Таким образом, поезд k - это ваш лучший немедленный ход.

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

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

Алгоритм таков:"садитесь на самый быстрый поезд, который не опережает пункт назначения".

Сколько это остановок, немного сложно.

Кодируйте обе остановки как двоичные числа. Я утверждаю, что идентичным префиксом можно пренебречь; проблема перехода от a к b та же, что и проблема перехода от a+2^n к b+2^n, если 2^n > b, поскольку остановки между 2^n и 2^(n+1) являются просто остановками между 0 и 2^n.]} сдвинулся с места.

Из этого мы можем сократить путь от a до b, чтобы гарантировать, что высокий бит b установлен, и тот же самый "высокий" бит a не установлен .

Чтобы решить переход от 5 (101) к 7 (111), нам просто нужно решить переход от 1 (01) к 3 (11), а затем сдвинуть наши стоп-номера вверх на 4 (100).

Чтобы перейти от x к 2^n + y, где y < 2^n (и, следовательно, x), мы сначала хотим перейти к 2^n, потому что нет поездов, которые пропускают 2^n, которые также не пропускают 2^n+y < 2^{n+1}. Таким образом, любой набор остановок между x и y должен остановиться на 2^n. Таким образом, оптимальным числом остановок от x до 2^n + y является число остановок от x до 2^n, за которым следует число остановок от 2^n до 2^n+y включительно (или от 0 до y, что одно и то же). Алгоритм, который я предлагаю получить от 0 до y, состоит в том, чтобы начать с набора битов высокого порядка и сесть на поезд, который доставит вас туда, а затем идти дальше по списку.

Утверждение: для того чтобы сгенерировать число с k 1s, Вы должны взять по крайней мере k поезда. В качестве доказательства, если вы едете на поезде, и это не вызывает переноса номера остановки, он устанавливает 1 бит. Если вы берете поезд, и он действительно вызывает перенос, результирующее число имеет не более чем на 1 бит больше, чем было начато.

Добраться от x до 2^n немного сложнее, но можно сделать проще, отслеживая поезда, которые вы берете назад .

Сопоставляя s_i с s_{2^n-i} и обращая шаги поезда вспять, любое решение для перехода от x к 2^n описывает решение для перехода от 0 к 2^n-x. И любое решение, которое оптимально для прямого, оптимально для обратного, и наоборот.

Используя результат для получения от 0 до y, мы получаем, что оптимальный маршрут от a до b, где b наивысший набор битов равен 2^n и a не имеет этого набора битов, является #b-2^n + #2^n-a, где # означает "число битов, установленных в двоичном представлении". И вообще, если a и b имеют общий префикс, просто отбросьте этот общий префикс.

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

Для части, идущей от 2^n к 2^n+y, мы сделали это явно в нашем доказательстве выше. Для части, идущей от x к 2^n, это сложнее. видеть.

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

Во-вторых, представьте себе, что x имеет некоторую коллекцию несетевых младших битов, скажем m из них. Если бы мы играли в игру с поездом, идущим от x/2^m до 2^(n-m), а затем масштабировали номера остановок, умножая их на 2^m, мы получили бы решение для перехода от x к 2^n.

И #(2^n-x)/2^m = #2^n - x. Таким образом, это "масштабированное" решение является оптимальным.

Исходя из этого, мы всегда берем поезд, соответствующий нашему младшему разряду набора в этом оптимальном решении. Это самый длинный доступный поезд дальности, и он не промахивается 2^n.

QED

Эта задача не требует динамического программирования.

Вот простая реализация решения с использованием GCC:

uint32_t min_stops(uint32_t start, uint32_t end)
{
    uint32_t stops = 0;
    if(start != 0) {
        while(start <= end - (1U << __builtin_ctz(start))) {
            start += 1U << __builtin_ctz(start);
            ++stops;
        }
    }
    stops += __builtin_popcount(end ^ start);
    return stops;
}

Схема поезда - это карта степеней двух. Если вы визуализируете железнодорожные линии как битовое представление, вы можете увидеть, что наименьший набор битов представляет железнодорожную линию с наибольшим расстоянием между остановками, которое вы можете взять. Вы также можете взять линии с меньшими расстояниями.

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

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

Пример перехода от 5 к 39:

000101 5        // Start
000110 5+1=6
001000 6+2=8
010000 8+8=16
100000 16+16=32 // 32+32 > 39, so start reversing the process
100100 32+4=36  // Optimized with __builtin_popcount in code
100110 36+2=38  // Optimized with __builtin_popcount in code
100111 38+1=39  // Optimized with __builtin_popcount in code

Как указывали некоторые, поскольку все остановки кратны степени 2, поезда, которые останавливаются чаще, также останавливаются на тех же остановках более скоростных поездов. Любая остановка находится на пути первого поезда, который останавливается на каждой станции. Любая остановка находится не более чем в 1 единице от маршрута второго поезда, останавливаясь на каждой второй станции. Любая остановка находится не более чем в 3-х единицах от третьего поезда, который останавливается на каждой четвертой станции, и так далее.

Итак, начните с конца и проследите свой маршрут назад во времени-прыгайте дальше ближайший поезд кратности мощности 2 и продолжайте переключаться на самый высокий поезд кратности мощности 2, который вы можете как можно скорее (проверьте положение наименее значимого установленного бита - почему? кратные степени 2 можно разделить на две, то есть сдвинуть бит вправо, не оставляя остатка, логарифмировать 2 раза или столько же ведущих нулей в битовом представлении), до тех пор, пока его интервал не пропустит начальную точку после одной остановки. Когда последнее имеет место, выполните обратный переключатель, прыгайте на следующий более низкий поезд кратной мощности 2 и оставайтесь на нем до тех пор, пока его интервал не пропустит начальную точку после одной остановки, и так далее.

Мы можем выяснить это, не делая ничего, кроме небольшого подсчета и манипуляции массивом. Как и все предыдущие ответы, мы должны начать с преобразования обоих чисел в двоичные и заполнения их одинаковой длины. Таким образом, 12 и 38 становятся 01100 и 10110.

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

Если мы находимся на станции 0010110100, наша последовательность будет:

0010110100  2^2
0010111000  2^3
0011000000  2^6
0100000000  2^7
1000000000

Здесь мы можем исключить все биты, меньшие, чем самый значительный бит набора, и получить то же самое число.

00101101  2^0
00101110  2^1
00110000  2^4
01000000  2^6
10000000

Обрезая концы на каждом этапе, мы получается так:

00101101  2^0
 0010111  2^0
    0011  2^0
      01  2^0
       1

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

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

1000000000 2^7
1010000000 2^5
1010100000 2^4
1010110000 2^2
1010110100

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

Затем добавьте результат из частей 1 и 2

Немного скорректировав алгоритм, чтобы получить все интервалы движения поездов, вот пример, написанный на javascript, чтобы его можно было запустить здесь.

function calculateStops(start, end) {
  var result = {
    start: start,
    end: end,
  	count: 0,
  	trains: [],
    reverse: false
  };
  
  // If equal there are 0 stops
  if (start === end) return result;

  // If start is greater than end, reverse the values and
  // add note to reverse the results
  if (start > end) {
    start = result.end;
    end = result.start;
    result.reverse = true;
  }    

  // Convert start and end values to array of binary bits
  // with the exponent matched to the index of the array
  start = (start >>> 0).toString(2).split('').reverse();
  end = (end >>> 0).toString(2).split('').reverse();

  // We can trim off any matching significant digits
  // The stop pattern for 10 to 13 is the same as
  // the stop pattern for 2 to 5 offset by 8
	while (start[end.length-1] === end[end.length-1]) {
    start.pop();
    end.pop();
  }

  // Trim off the most sigificant bit of the end, 
  // we don't need it
  end.pop();

  // Front fill zeros on the starting value
  // to make the counting easier
  while (start.length < end.length) {
    start.push('0');
  }

  // We can break the algorithm in half
  // getting from the start value to the form
  // 10...0 with only 1 bit set and then getting
  // from that point to the end.

  var index;
	var trains = [];
  var expected = '1';

  // Now we loop through the digits on the end
  // any 1 we find can be added to a temporary array
  for (index in end) {
    if (end[index] === expected){
    	result.count++;
      trains.push(Math.pow(2, index));
    };
  }

  // if the start value is 0, we can get to the 
  // intermediate step in one trip, so we can
  // just set this to 1, checking both start and
  // end because they can be reversed
  if (result.start == 0 || result.end == 0) {
    index++
    result.count++;
    result.trains.push(Math.pow(2, index));
  // We need to find the first '1' digit, then all
  // subsequent 0 digits, as these are the ones we
  // need to flip
  } else {
    for (index in start) {
      if (start[index] === expected){
        result.count++;
        result.trains.push(Math.pow(2, index));
        expected = '0';
      }
    }  
  }

  // add the second set to the first set, reversing
  // it to get them in the right order.
	result.trains = result.trains.concat(trains.reverse());

  // Reverse the stop list if the trip is reversed
	if (result.reverse) result.trains = result.trains.reverse();
  
  return result;
}

$(document).ready(function () {
	$("#submit").click(function () {
  	var trains = calculateStops(
      parseInt($("#start").val()),
      parseInt($("#end").val())
    );

  	$("#out").html(trains.count);
    
  	var current = trains.start;
    var stopDetails = 'Starting at station ' + current + '<br/>';
    for (index in trains.trains) {
      current = trains.reverse ? current - trains.trains[index] : current + trains.trains[index];
      stopDetails = stopDetails + 'Take train with interval ' + trains.trains[index] + ' to station ' + current + '<br/>';
    }

  	$("#stops").html(stopDetails);
  });
});

label {
  display: inline-block;
  width: 50px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<label>Start</label> <input id="start" type="number" /> <br>
<label>End</label> <input id="end" type="number" /> <br>
<button id="submit">Submit</button>

<p>Shortest route contains <span id="out">0</span> stops</p>
<p id="stops"></p>

Простое решение Java

public static int minimumNumberOfStops(int start, final int end) {
    // I would initialize it with 0 but the example given in the question states :
    // the minimum number of stops between start = 1 and end = 4 is 3 because we can get from 1 to 2 to 4
    int stops = 1;
    while (start < end) {
        start += findClosestPowerOfTwoLessOrEqualThan(end - start);
        stops++;
    }
    return stops;
}

private static int findClosestPowerOfTwoLessOrEqualThan(final int i) {
    if (i > 1) {
        return 2 << (30 - Integer.numberOfLeadingZeros(i));
    }
    return 1;
}

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

Этот алгоритм начинается с procedure main(Origin, Dest) и он моделирует наши движения к месту назначения с помощью updateOrigin(Origin, Dest)

procedure main(Origin, Dest){

         //at the end we have number of minimum steps in this variable
         counter = 0;

         while(Origin != Dest){

              //we simulate our movement toward destination with this
              Origin = updateOrigin(Origin, Dest);

              counter = counter + 1;

         }

}

procedure updateOrigin(Origin, Dest){

    if (Origin == 1) return 2;

    //we must find which train pass from our origin, what comes out from this IF clause is NOT exact choice and we still have to do some calculation in future
    if (Origin == 0){

       //all trains pass from stop 0, thus we can choose our train according to destination
       n = Log2(Dest);

    }else{

       //its a good starting point to check if it pass from our origin
       n = Log2(Origin);

    }

    //now lets choose exact train which pass from origin and doesn't overshoot destination
    counter = 0;
    do {
             temp = counter * 2 ^ (n - 1);

             //we have found suitable train
             if (temp == Origin){

                 //where we have moved to
                 return Origin + 2 ^ ( n - 1 );

             //we still don't know if this train pass from our origin
             } elseif (temp < Origin){

                 counter = counter + 1;

             //lets check another train
             } else {

                 n = n - 1;
                 counter  = 0;

             }

    }while(temp < origin)

}