algorithm - problems - Número mínimo de paradas de la estación de tren
dynamic programming problems (8)
Como algunos han señalado, dado que las paradas son todos múltiplos de potencias de 2, los trenes que paran con más frecuencia también paran en las mismas paradas que los trenes más rápidos. Cualquier parada está en la ruta del primer tren, que se detiene en cada estación. Cualquier parada se encuentra a lo sumo a 1 unidad de la ruta del segundo tren, deteniéndose en cada segunda estación. Cualquier parada es a lo sumo 3 unidades del tercer tren que se detiene cada cuarta estación, y así sucesivamente.
Así que comience por el final y vuelva a trazar su ruta en el tiempo: súbase al tren más cercano de múltiplos de potencia de 2 y continúe cambiando al tren más alto de múltiplos de poder de 2 que pueda tan pronto como sea posible ( verifique la posición del bit de configuración menos significativo: ¿por qué? los múltiplos de potencias de 2 se pueden dividir en dos, es decir, con desplazamiento de bits a la derecha, sin dejar un resto, registrar 2 veces, o tantos ceros a la izquierda en la representación de bits) , siempre y cuando su intervalo no pierda el punto de partida después de una parada. Cuando este último sea el caso, realice el cambio de marcha atrás, suba al siguiente tren inferior de múltiples potencias de 2 y permanezca en él hasta que su intervalo no pierda el punto de inicio después de una parada, y así sucesivamente.
Recibí esta pregunta de la entrevista y me quedé atascado en ella:
Hay un número infinito de paradas de tren que comienzan en la estación número 0.
Hay un número infinito de trenes. El tren n se detiene en todos los k * 2 ^ (n - 1) paradas donde k está entre 0 e infinito.
Cuando n = 1, el primer tren se detiene en las paradas 0, 1, 2, 3, 4, 5, 6, etc.
Cuando n = 2, el segundo tren se detiene en las paradas 0, 2, 4, 6, 8, etc.
Cuando n = 3, el tercer tren se detiene en las paradas 0, 4, 8, 12, etc.
Dado un número de estación de inicio y un número de estación final, devuelva el número mínimo de paradas entre ellos. Puede utilizar cualquiera de los trenes para ir de una parada a otra.
Por ejemplo, el número mínimo de paradas entre inicio = 1 y final = 4 es 3 porque podemos obtener de 1 a 2 a 4.
Estoy pensando en una solución de programación dinámica que almacene en dp[start][end] el número mínimo de pasos entre el start y el end . Construimos la matriz usando start...mid1, mid1...mid2, mid2...mid3, ..., midn...end . Pero no pude hacerlo funcionar. ¿Cómo resuelves esto?
Aclaraciones:
- Los trenes solo pueden avanzar desde una parada numérica inferior a una parada numérica superior.
- Un tren puede comenzar en cualquier estación donde haga una parada en.
- Los trenes se pueden abordar en cualquier orden. El tren n = 1 puede abordarse antes o después de abordar el tren n = 3.
- Los trenes pueden ser abordados varias veces. Por ejemplo, está permitido abordar el tren n = 1, luego abordar el tren n = 2 y finalmente abordar el tren n = 1 nuevamente.
Este problema no requiere programación dinámica.
Aquí hay una implementación simple de una solución usando 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;
}
El esquema del tren es un mapa de potencias de dos. Si visualiza las líneas del tren como una representación de bits, puede ver que el conjunto de bits más bajo representa la línea de trenes con la distancia más larga entre paradas que puede tomar. También puedes tomar las líneas con distancias más cortas.
Para minimizar la distancia, desea tomar la línea con la mayor distancia posible, hasta que eso haga que la estación final sea inalcanzable. Eso es lo que hace la adición por el bit de conjunto más bajo en el código. Una vez que haga esto, algún número de los bits superiores coincidirá con los bits superiores de la estación final, mientras que los bits inferiores serán cero.
En ese punto, es simplemente una cuestión de tomar un tren para el bit más alto en la estación final que no está configurado en la estación actual. Esto se optimiza como __builtin_popcount en el código.
Un ejemplo que va del 5 al 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
Intentaré probar que mi algoritmo es óptimo.
El algoritmo es "tomar el tren más rápido que no sobrepasa su destino".
Cuántas paradas es un poco complicada.
Codifica ambas paradas como números binarios. Afirmo que un prefijo idéntico puede ser descuidado; El problema de ir de a a b es el mismo que el de ir de a+2^n a b+2^n si 2^n > b , como las paradas entre 2^n y 2^(n+1) son solo las paradas entre 0 y 2^n desplazadas.
A partir de esto, podemos reducir un viaje de a a b para garantizar que se establece el bit alto de b , y no se establece el mismo bit "high" de a .
Para resolver el paso de 5 ( 101 ) a 7 ( 111 ), simplemente tenemos que resolver el paso de 1 ( 01 ) a 3 ( 11 ), luego cambiar nuestros números de parada 4 ( 100 ).
Para pasar de x a 2^n + y , donde y < 2^n (y, por tanto, x es), primero queremos ir a 2^n , porque no hay trenes que salten más de 2^n que tampoco salten más de 2^n+y < 2^{n+1} .
Por lo tanto, cualquier conjunto de paradas entre x e y debe detenerse en 2^n .
Por lo tanto, el número óptimo de paradas de x a 2^n + y es el número de paradas de x a 2^n , seguido del número de paradas de 2^n a 2^n+y , inclusive (o de 0 a y , que es lo mismo).
El algoritmo que propongo obtener de 0 a y es comenzar con el conjunto de bits de orden superior, y tomar el tren que lo lleva allí, luego continuar por la lista.
Reclamo: para generar un número con k 1 s, debes tomar al menos k trenes. Como prueba, si toma un tren y no causa un acarreo en su número de parada, establece 1 bit. Si toma un tren y causa un acarreo, el número resultante tiene a lo sumo 1 bit más establecido que con el que comenzó.
Obtener de x a 2^n es un poco más complicado, pero se puede simplificar rastreando los trenes que toma hacia atrás .
Al asignar s_i a s_{2^ni} e invertir los pasos del tren, cualquier solución para obtener de x a 2^n describe una solución para obtener de 0 a 2^nx . Y cualquier solución que sea óptima para la delantera es óptima para la anterior, y viceversa.
Usando el resultado para pasar de 0 a y , obtenemos que la ruta óptima de a a b donde b conjunto de bits más alto es 2^n y a no tiene ese bit establecido como # b-2^n + # 2^na , donde # significa "el número de bits establecido en la representación binaria". Y, en general, si a y b tienen un prefijo común, simplemente elimine ese prefijo común.
Una regla local que genera el número de pasos anterior es "tomar el tren más rápido en su ubicación actual que no supere su destino".
Para la parte que va de 2^n a 2^n+y lo hicimos explícitamente en nuestra prueba anterior. Para la parte que va de x a 2^n esto es más difícil de ver.
Primero, si se establece el bit de orden inferior de x , obviamente tenemos que tomar el primer y único tren que podamos tomar.
En segundo lugar, imagine x tiene una colección de bits de orden inferior no configurados, digamos m de ellos. Si jugamos el juego del tren yendo de x/2^m a 2^(nm) , luego escalamos los números de parada multiplicando por 2^m obtendríamos una solución para pasar de x a 2^n .
Y # (2^nx)/2^m = # 2^n - x . Así que esta solución "escalada" es óptima.
A partir de esto, siempre estamos tomando el tren correspondiente a nuestro bit de ajuste de bajo orden en esta solución óptima. Este es el tren de mayor alcance disponible, y no sobrepasa 2^n .
QED
No creo que necesites programación dinámica para este problema. Básicamente se puede expresar mediante cálculos binarios.
Si convierte el número de una estación a binario, le indica de inmediato cómo llegar desde la estación 0, por ejemplo,
estación 6 = 110
le dice que necesita tomar el tren n = 3 y el tren n = 2 para cada estación. Por lo tanto, la suma cruzada de la representación binaria le indica cuántos pasos necesita.
El siguiente paso es averiguar cómo ir de una estación a otra. Voy a mostrar esto de nuevo por ejemplo. Digamos que quieres ir de la estación 7 a la estación 23.
estación 7 = 00111
estación 23 = 10111
Lo primero que quieres hacer es llegar a una parada intermedia. Esta parada está especificada por
(los bits más altos que son iguales en la estación de inicio y final) + (primer bit diferente) + (rellenado con ceros)
En nuestro ejemplo, la parada intermedia es 16 (10000). Los pasos que debe realizar se pueden calcular por la diferencia de ese número y la estación de inicio (7 = 00111). En nuestro ejemplo este cede.
10000 - 00111 = 1001
Ahora sabes que necesitas 2 paradas (n = 1 tren y n = 4) para llegar de 7 a 16. La tarea restante es obtener de 16 a 23, una vez más, esto se puede resolver con la diferencia correspondiente
10111 - 10000 = 00111
Entonces, necesitas otras 3 paradas para ir de 16 a 23 (n = 3, n = 2, n = 1). Esto le da 5 paradas en total, solo usando dos diferencias binarias y el operador de suma cruzada. La ruta resultante se puede extraer de las representaciones de bits 7 -> 8 -> 16 -> 20 -> 22 -> 23
Editar:
Para una mayor aclaración de la parada intermedia, supongamos que queremos ir desde
estación 5 = 101 a
estación 7 = 111
la parada intermedia en este caso será 110, porque
bits más altos que son iguales en la estación de inicio y final = 1
primer bit diferente = 1
rellenado con ceros = 0
necesitamos un paso para ir allí (110 - 101 = 001) y uno más para ir desde allí hasta la estación final (111 - 110 = 001).
Sobre la parada intermedia.
El concepto de la parada intermedia es un poco torpe pero no pude encontrar una forma más elegante para que las operaciones de bits funcionen. La parada intermedia es la parada entre el inicio y el final donde el bit de nivel más alto cambia (por eso se construye de la manera que es). En este sentido, es la parada en la que opera el tren más rápido (entre el inicio y el final) (en realidad, todos los trenes que puede tomar se detienen allí).
Al restar la parada intermedia (representación de bits) de la estación final (representación de bits), reduce el problema al caso simple a partir de la estación 0 (consulte el primer ejemplo de mi respuesta).
Al restar la estación de inicio de la parada intermedia, también reduce el problema al caso simple, pero suponga que va desde la parada intermedia a la estación de inicio que es equivalente a la inversa.
Podemos resolver esto haciendo nada más que un poco de conteo y manipulación de matrices. Al igual que todas las respuestas anteriores, debemos comenzar por convertir ambos números a binarios y rellenarlos a la misma longitud. Así que 12 y 38 se convierten en 01100 y 10110.
Mirando la estación 12, mirando el bit de configuración menos significativo (en este caso, el único bit, 2 ^ 2), todos los trenes con intervalos mayores que 2 ^ 2 no se detendrán en la estación 4, y todos con intervalos menores o iguales a 2 ^ 2 se detendrá en la estación 4, pero requerirá varias paradas para llegar al mismo destino que el tren del intervalo 4. En todas las situaciones, hasta que alcancemos el bit de conjunto más grande en el valor final, debemos tomar el tren con el intervalo del bit menos significativo de la estación actual.
Si estamos en la estación 0010110100, nuestra secuencia será:
0010110100 2^2
0010111000 2^3
0011000000 2^6
0100000000 2^7
1000000000
Aquí podemos eliminar todos los bits más pequeños que el mínimo establecido y obtener el mismo conteo.
00101101 2^0
00101110 2^1
00110000 2^4
01000000 2^6
10000000
Recortando los extremos en cada etapa, obtenemos esto:
00101101 2^0
0010111 2^0
0011 2^0
01 2^0
1
Esto también podría ser descrito como el proceso de voltear todos los 0 bits. Lo que nos lleva a la primera mitad del algoritmo: Cuente los bits no configurados en el número de inicio con relleno cero mayor que el bit de configuración menos significativo, o 1 si la estación de inicio es 0.
Esto nos llevará a la única estación intermedia a la que puede llegar el tren con el mayor intervalo más pequeño que la estación final, por lo que todos los trenes después de esto deben ser más pequeños que el tren anterior.
Ahora debemos ir de la estación al 100101, es más fácil y obvio, tomar el tren con un intervalo igual al bit significativo más grande establecido en el destino y no en el número de estación actual.
1000000000 2^7
1010000000 2^5
1010100000 2^4
1010110000 2^2
1010110100
Al igual que en el primer método, podemos recortar el bit más significativo que siempre se establecerá y luego contar los 1 restantes en la respuesta. Así que la segunda parte del algoritmo es Contar todos los bits significativos establecidos más pequeños que el bit más significativo
Luego agrega el resultado de las partes 1 y 2
Ajustando el algoritmo ligeramente para obtener todos los intervalos del tren, aquí hay un ejemplo escrito en javascript para que pueda ejecutarse aquí.
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>
Primero, pregunta si puedes ir hacia atrás. Parece que no puede, pero como se presenta aquí (que puede no reflejar la pregunta tal como la recibió), el problema nunca da una dirección explícita para ninguno de estos trenes. (Veo que ahora ha editado su pregunta para decir que no puede retroceder).
Suponiendo que no pueda retroceder, la estrategia es simple: siempre tome el tren disponible con el número más alto que no exceda su destino.
Supongamos que se encuentra en la parada s , y el tren con el número más alto que se detiene en su ubicación actual y no sobrepasa el tren k . Viajar una vez en el tren k te llevará a detener s + 2^(k-1) . No hay una manera más rápida de llegar a esa parada, y no hay manera de saltear esa parada, no hay trenes con números más bajos que se salten ninguna de las paradas del tren k , y no hay trenes con números más altos que se detengan entre las paradas del tren k , por lo que puede No te subas a un tren de mayor número antes de llegar allí. Por lo tanto, el tren k es tu mejor movimiento inmediato.
Con esta estrategia en mente, la mayor parte de la optimización restante es una cuestión de trucos eficientes para calcular el número de paradas sin descubrir explícitamente cada parada en la ruta.
Solución Java simple
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;
}
AVISO : El motivo de los comentarios actuales en mi respuesta es que primero escribí este algoritmo completamente incorrecto y el usuario2357112 me libró de mis errores. Así que eliminé completamente ese algoritmo y escribí uno nuevo según lo que el usuario2357112 respondió a esta pregunta. También agregué algunos comentarios a este algoritmo para aclarar qué sucede en cada línea.
Este algoritmo comienza en el procedure main(Origin, Dest) y simula nuestros movimientos hacia el destino con 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)
}