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

Ответ 1

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

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

станция 6 = 110

говорит вам, что вам нужно сесть на поезд n = 3 и поезд n = 2 каждый для одной станции. Таким образом, поп -код двоичного представления говорит вам, сколько шагов вам нужно.

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

станция 7 = 00111

станция 23 = 10111

Первое, что вы хотите сделать, это добраться до промежуточной остановки. Эта остановка определяется

(старшие биты, которые равны в начальной и конечной станциях) + (первый разный бит) + (заполнены нулями)

В нашем примере промежуточный останов 16 (10000). Шаги, которые вам нужно сделать, могут быть рассчитаны по разности этого числа и начальной станции (7 = 00111). В нашем примере это дает

10000 - 00111 = 1001

Теперь вы знаете, что вам нужно 2 остановки (n = 1 поезд и n = 4), чтобы добраться с 7 до 16. Остальная задача - с 16 до 23, опять же, это можно решить с помощью соответствующей разницы.

10111 - 10000 = 00111

Итак, вам нужно еще 3 остановки, чтобы перейти с 16 на 23 (n = 3, n = 2, n = 1). Это дает вам всего 5 остановок, просто используя две двоичные разницы и поп-счет. Результирующий путь может быть извлечен из битовых представлений 7 → 8 → 16 → 20 → 22 → 23

Редактировать:

Для дальнейшего уточнения промежуточной остановки предположим, что мы хотим перейти от

станция 5 = 101 до

станция 7 = 111

промежуточный останов в этом случае будет 110, потому что

старшие биты, которые равны в начальной и конечной станциях = 1

первый отличающийся бит = 1

заполнено нулями = 0

нам нужно сделать один шаг туда (110 - 101 = 001) и еще один - оттуда до конечной станции (111 - 110 = 001).

О промежуточной остановке

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

Вычитая промежуточную остановку (представление битов) из конечной станции (представление битов), вы сводите задачу к простому случаю, начиная со станции 0 (см. Первый пример моего ответа).

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Кодировать обе остановки как двоичные числа. Я утверждаю, что одним и тем же префиксом можно пренебречь; проблема перехода от 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 is), мы сначала хотим перейти к 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 1 с, вы должны взять не менее k поезда. В качестве доказательства, если вы едете на поезде, и он не вызывает перенос вашего номера остановки, он устанавливает 1 бит. Если вы берете поезд, и это вызывает перенос, итоговое число имеет не более 1 бит, чем было начато.

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

Сопоставляя s_i с s_{2^ni} и изменяя шаги поезда, любое решение для получения от x до 2^n описывает решение для получения от 0 до 2^nx. И любое решение, оптимальное для прямого, оптимально для обратного, и наоборот.

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

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

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

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

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

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

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

QED

Ответ 4

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

Вот простая реализация решения с использованием 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

Ответ 5

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

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

Ответ 6

Мы можем понять это, ничего не делая, кроме небольшого подсчета и манипуляции с массивами. Как и все предыдущие ответы, нам нужно начать с преобразования двух чисел в двоичные и их заполнения до одной и той же длины. Таким образом, 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>

Ответ 7

Простое решение 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;
}

Ответ 8

УВЕДОМЛЕНИЕ. Основанием для текущих комментариев под моим ответом является то, что сначала я написал этот алгоритм полностью неправильно, и 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)

}