Rompecabezas de cruce de puente

Question

Cuatro hombres tienen que cruzar un puente por la noche. Cualquier persona que cruza, ya sea uno o dos hombres, debe llevar la linterna con ellos. La linterna debe caminar hacia adelante y hacia atrás; no puede ser arrojado, etc. Cada hombre camina a una velocidad diferente. Uno tarda 1 minuto en cruzar, otros 2 minutos, otros 5 y los últimos 10 minutos. Si dos hombres se cruzan juntos, deben caminar al paso del hombre más lento. No hay trucos: todos los hombres comienzan en el mismo lado, la linterna no puede iluminar una gran distancia, nadie puede cargarse, etc.

Y la pregunta es: ¿Cuál es el tiempo más rápido que pueden cruzar? Básicamente estoy buscando un enfoque generalizado para este tipo de problema. Mi amigo me dijo que esto puede resolverse con la serie de Fibonacci, pero la solución no funciona para todos.

Tenga en cuenta que esto no es un trabajo a domicilio.

Answer 1

Hay an entire PDF (alternate link) que resuelve el caso general de este problema (en una prueba formal).

Answer 2

17 minutos: esta es una pregunta clásica de MS.

1,2 => 2 minutes passed. 
1 retuns => 3 minutes passed. 
5,10 => 13 minutes passed. 
2 returns => 15 minutes passed. 
1,2 => 17 minute passed. 

En general, el problema más grande/más lentos gente siempre debe poner juntos, y los viajes de los más rápidos suficientes hechos para ser capaz de devolver la luz cada vez sin necesidad de utilizar un recurso lento.

Answer 3

17 - una pregunta muy común

-> 1-2 = 2
< - 2 = 2
-> 5,10 = 10 (ninguno de ellos tiene que volver)
< - 1 = 1
-> 1,2 = 2

todo en el otro lado
Total = 2 + 2 + 10 + 1 + 2 = 17

usuall y la gente lo obtiene como 19 en el primer intento

Answer 4

Resolvería este problema colocando un anuncio de trabajo falso en Dice.com, y luego haciendo esta pregunta en las entrevistas hasta que alguien lo haga bien.

Answer 5

Una búsqueda exhaustiva de todas las posibilidades es simple con un espacio de problema tan pequeño. La amplitud o profundidad primero funcionaría. Es un problema simple de CS.

Yo prefiero el misionero y problemas caníbal yo mismo

Answer 6

Según Wikipedia

El puzzle es conocido por haber aparecido ya en 1981, en el libro de Super Estrategias para los rompecabezas y juegos. En esta versión del rompecabezas, A, B, C y D tardan 5, 10, 20 y 25 minutos, respectivamente, en cruzarse, y el límite de tiempo es 60 minutos

Esta pregunta se popularizó después de su aparición en el libro "¿Cómo te mudarías al monte Fuji?"

la pregunta puede ser generalizada para N personas con diferentes tiempos individuales para cruzar el puente.

El siguiente programa funciona para un n genérico de personas y sus tiempos.

class Program 
{ 
    public static int TotalTime(List<int> band, int n) 
    { 
     if (n < 3) 
     { 
      return band[n - 1]; 
     } 
     else if (n == 3) 
     { 
      return band[0] + band[1] + band[2]; 
     } 
     else 
     { 
      int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0]; 
      int temp2 = band[1] + band[0] + band[n - 1] + band[1]; 

      if (temp1 < temp2) 
      { 
       return temp1 + TotalTime(band, n - 2); 
      } 
      else if (temp2 < temp1) 
      { 
       return temp2 + TotalTime(band, n - 2); 
      } 
      else 
      { 
       return temp2 + TotalTime(band, n - 2); 
      } 
     } 
    } 

    static void Main(string[] args) 
    { 
     // change the no of people crossing the bridge 
     // add or remove corresponding time to the list 
     int n = 4; 

     List<int> band = new List<int>() { 1, 2, 5, 10 }; 

     band.Sort(); 

     Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n)); 
     Console.ReadLine(); 
    } 
} 

SALIDA:

El tiempo total necesario para cruzar el puente es: 17

Para,

int n = 5; 
List<int> band = new List<int>() { 1, 2, 5, 10, 12 }; 

SALIDA:

El tiempo total necesario para cruzar la el puente es: 25

Para,

int n = 4; 
List<int> band = new List<int>() { 5, 10, 20, 25 }; 

SALIDA El tiempo total necesario para cruzar el puente es: 60

Answer 7

Me asignan las posibles soluciones algebraicamente y salió con el mejor tiempo. y asignando álgebra con la lista de A, B, C, D donde A es el más pequeño y D es el más grande la fórmula para el tiempo más corto es B + A + D + B + B o 3B + A + D o en términos verbosos, la suma de los segundos mejores tiempos 3 y agrega los más rápidos y los más lentos.

mirando el programa también hubo una cuestión de aumento de los artículos. Aunque no he pasado por eso, pero supongo que la fórmula aún se aplica, simplemente agregue todos los elementos con el segundo elemento multiplicado por 3 y la suma de todo, excepto los segundos tiempos más lentos. p. ya que 4 elementos son 3 x segundo + primero y cuarto. luego 5 artículos son 3 x segundo + primero, tercero y quinto. quisiera verificar esto usando el programa.

también acabo de ver el pdf compartido anteriormente, por lo que para más elementos es la suma de 3 x segundo + más rápido + suma de la más lenta de cada par posterior.

mirando los pasos para la solución optimizada, la idea es -right - por dos elementos va a la derecha, el más rápido es 1º y 2º más rápido, -izquierda - a continuación, además de la más rápida de volver para un solo elemento es el artículo más rápido -derecho- trae los 2 elementos más lentos, que representarán solo el artículo más lento y descartarán el segundo más lento. -izquierda - el segundo elemento más rápido. -final derecha- el 1º y 2º más rápido nuevamente

así que de nuevo resumiendo = 2º más rápido va 3 veces, el más rápido va una vez, y el más lento va con 2º más lento.

Answer 8

Un simple algoritmo es: asuma 'N' es el número de personas que pueden cruzar en mismo tiempo y una persona tiene que cruzar de nuevo teniendo la antorcha

1. Al mover personas desde el primer lado al segundo preferencia lado se debe dar a los caminantes más lentos de la 'N'
2. siempre uso más rápido andador para tomar la antorcha del segundo lado de la primera parte
3. Cuando personas que se desplazan desde el primer lado al segundo lado, tener en cuenta que va a traer de vuelta a la antorcha en el próximo paso.Si la velocidad del portador de la antorcha en el siguiente paso será igual al andador más rápido, entre los caminantes más lentos 'N', en el paso actual, en lugar de elegir 'N' el andador más lento, como se indica en '1', elija 'N' 'caminantes más rápidos

Aquí es un script de ejemplo pitón que hace esto: https://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py

Answer 9

Aquí está la respuesta en rubí:

@values = [1, 2, 5, 10] 
# @values = [1, 2, 5, 10, 20, 25, 30, 35, 40] 
@values.sort! 
@position = @values.map { |v| :first } 
@total = 0 

def send_people(first, second) 
    first_time = @values[first] 
    second_time = @values[second] 

    @position[first] = :second 
    @position[second] = :second 

    p "crossing #{first_time} and #{second_time}" 

    first_time > second_time ? first_time : second_time 
end 

def send_lowest 
    value = nil 
    @values.each_with_index do |v, i| 
    if @position[i] == :second 
     value = v 
     @position[i] = :first 
     break 
    end 
    end 

    p "return #{value}" 
    return value 
end 


def highest_two 
    first = nil 
    second = nil 

    first_arr = @position - [:second] 

    if (first_arr.length % 2) == 0 
    @values.each_with_index do |v, i| 
     if @position[i] == :first 
     first = i unless first 
     second = i if !second && i != first 
     end 

     break if first && second 
    end 
    else 
    @values.reverse.each_with_index do |v, i| 
     real_index = @values.length - i - 1 
     if @position[real_index] == :first 
     first = real_index unless first 
     second = real_index if !second && real_index != first 
     end 

     break if first && second 
    end 
    end 

    return first, second 
end 

#we first send the first two 
@total += send_people(0, 1) 
#then we get the lowest one from there 
@total += send_lowest 
#we loop through the rest with highest 2 always being sent 
while @position.include?(:first) 
    first, second = highest_two 
    @total += send_people(first, second) 
    @total += send_lowest if @position.include?(:first) 
end 

p "Total time: #{@total}" 

Answer 10

Otra implementación de ruby ​​inspirado por @ roc-Khalil' solución s

@values = [1,2,5,10] 
# @values = [1,2,5,10,20,25] 
@left = @values.sort 
@right = [] 
@total_time = 0 

def trace(moving) 
    puts moving 
    puts "State: #{@left} #{@right}" 
    puts "Time: #{@total_time}" 
    puts "-------------------------" 
end 

# move right the fastest two 
def move_fastest_right! 
    fastest_two = @left.shift(2) 
    @right = @right + fastest_two 
    @right = @right.sort 
    @total_time += fastest_two.max 
    trace "Moving right: #{fastest_two}" 
end 

# move left the fastest runner 
def move_fastest_left! 
    fastest_one = @right.shift 
    @left << fastest_one 
    @left.sort! 
    @total_time += fastest_one 
    trace "Moving left: #{fastest_one}" 
end 

# move right the slowest two 
def move_slowest_right! 
    slowest_two = @left.pop(2) 
    @right = @right + slowest_two 
    @right = @right.sort 
    @total_time += slowest_two.max 
    trace "Moving right: #{slowest_two}" 
end 

def iterate! 
    move_fastest_right! 
    return if @left.length == 0 

    move_fastest_left! 
    move_slowest_right! 
    return if @left.length == 0 

    move_fastest_left! 
end 

puts "State: #{@left} #{@right}" 
puts "-------------------------" 
while @left.length > 0 
    iterate! 
end 

Salida:

State: [1, 2, 5, 10] [] 
------------------------- 
Moving right: [1, 2] 
State: [5, 10] [1, 2] 
Time: 2 
------------------------- 
Moving left: 1 
State: [1, 5, 10] [2] 
Time: 3 
------------------------- 
Moving right: [5, 10] 
State: [1] [2, 5, 10] 
Time: 13 
------------------------- 
Moving left: 2 
State: [1, 2] [5, 10] 
Time: 15 
------------------------- 
Moving right: [1, 2] 
State: [] [1, 2, 5, 10] 
Time: 17 
-------------------------