Bridge Crossing Puzzle

Question

Vier Männer müssen nachts eine Brücke überqueren. Jede Partei, die kreuzt, entweder ein oder zwei Männer, muss die Taschenlampe mit sich tragen. Die Taschenlampe muss hin und her gehen; es kann nicht geworfen werden, usw. Jeder Mann geht mit einer anderen Geschwindigkeit. Man braucht 1 Minute, um sich zu kreuzen, weitere 2 Minuten, weitere 5 und die letzten 10 Minuten. Wenn zwei Männer sich kreuzen, müssen sie im langsameren Tempo des Menschen gehen. Es gibt keine Tricks - die Männer beginnen alle auf der gleichen Seite, die Taschenlampe kann nicht weit strahlen, niemand kann getragen werden usw.

Und die Frage ist: Was ist der schnellste, den sie alle bewältigen können? Ich bin im Grunde auf der Suche nach einem verallgemeinerten Ansatz für diese Art von Problem. Mir wurde von meinem Freund gesagt, dass dies durch die Fibonacci-Serie gelöst werden kann, aber die Lösung funktioniert nicht für alle.

Bitte beachten Sie, dies ist keine Hausaufgaben.

Answer 1

Es gibt an entire PDF (alternate link), die den allgemeinen Fall dieses Problems (in einem formalen Beweis) löst.

Answer 2

17 Minuten - das ist eine klassische MS Frage.

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. 

Im Allgemeinen ist das größte Problem/langsamsten Menschen sollten immer zusammengesetzt werden und eine ausreichenden Fahrten des schnellsten machte das Licht der Lage sein, jedes Mal zurück zu bringen, ohne eine langsame Ressource zu verwenden.

Answer 3

17 - eine sehr häufige Frage

-> 1-2 = 2
<-2 = 2
-> 5,10 = 10 (keine von ihnen hat zurückzukehren)
< - 1 = 1
-> 1,2 = 2

alle auf der anderen Seite
total = 2 + 2 + 10 + 1 + 2 = 17

usuall y Leute erhalten es als 19 im ersten Versuch

Answer 4

Ich würde dieses Problem lösen, indem ich eine gefälschte Stellenanzeige auf Dice.com platziere und diese Frage dann in den Interviews stelle, bis jemand es richtig macht.

Answer 5

Eine erschöpfende Suche nach allen Möglichkeiten ist mit solch einem kleinen Problemraum einfach. Breite oder Tiefe würde zuerst funktionieren. Es ist ein einfaches CS-Problem.

ziehe ich den Missionar und Kannibalen Probleme selbst

Answer 6

Per Wikipedia

Das Puzzle bekannt ist bereits 1981 in dem Buch Super-Strategien für Puzzles und Spiele erschienen. In dieser Version des Puzzles, A, B, C und D dauern 5, 10, 20, und 25 Minuten jeweils zu überqueren, und das Zeitlimit ist 60 Minuten

Diese Frage wurde jedoch popularisiert nach seinem Auftreten in das Buch "Wie würdest du den Berg Fuji bewegen?"

Die Frage kann verallgemeinert werden für N Personen mit variierender individueller Zeit, um die Brücke zu überqueren.

Das folgende Programm funktioniert für eine generische N keine Menschen und ihre Zeiten.

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(); 
    } 
} 

OUTPUT:

Die Gesamtzeit, die Brücke zu überqueren genommen ist: 17

Denn

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

OUTPUT:

Die Gesamtzeit überqueren die Brücke ist: 25

Denn

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

OUTPUT Die die Brücke genommen Gesamtzeit zu überqueren ist: 60

Answer 7

ich die möglichen Lösungen algebraisch abgebildet und herauskam die mit der schnellsten Zeit. und Algebra mit der Liste von A, B, C, D zuzuteilen, wobei A die kleinste und D die größte Formel für die kürzeste Zeit ist B + A + D + B + B oder 3B + A + D oder in Wortliche Begriffe, die Summe der zweitschnellsten Zeiten 3 und fügen Sie mit den schnellsten und am langsamsten.

Blick auf das Programm gab es auch eine Frage der erhöhten Artikel. Obwohl ich es nicht durchgemacht habe, aber ich vermute, dass die Formel immer noch gilt, füge einfach hinzu, bis alle Items mit dem zweiten Item mal 3 sind und Summe von allem außer 2te langsamste Zeiten. z.B. seit 4 Positionen sind 3 x Sekunde + erste und vierte. dann 5 Elemente sind 3 x Sekunde + erste, dritte und fünfte. möchte dies mit dem Programm überprüfen.

auch ich schaute nur auf die pdf shared oben, so dass für mehr Artikel ist es die Summe 3 x Sekunde + schnellste + Summe der langsamsten von jedem nachfolgenden Paar.

bei den Schritten für die optimierte Lösung suchen, ist die Idee -right - für zwei Gegenstände nach rechts gehen die schnellste 1. und 2. schnellste, -left - dann plus die schnellste zurück für ein einzelnes Element gehen ist das schnellste Item -right - bringt die langsamsten 2 Items, die nur das langsamste Item ausmachen und das zweitlangsamste ignorieren. -links - der zweitschnellste Artikel. -finale rechts - das erste und zweitschnellste wieder

so wieder summing up = 2. schnellste geht 3 mal, schnellste geht einmal, und langsamste geht mit 2. langsamste.

Answer 8

Ein einfacher Algorithmus ist: Angenommen, ‚N‘ ist die Anzahl der Menschen, die zur gleichen Zeit durchqueren können und eine Person hat zurück zu überqueren die Fackel

1. Lager Wenn die Leute von der ersten Seite zu der zweiten Seite bevorzugt bewegt sollte die 'N' langsamsten Wanderer geben
2. Verwenden Sie immer am schnellsten Walker von der zweiten Seite zur ersten Seite zu nehmen
3. Wenn Menschen von der ersten Seite auf die zweite Seite zu bewegen, in Betracht ziehen, wer die Fackel in die bringen wird nächster Schritt.Wenn die Geschwindigkeit des Fackelträgers im nächsten Schritt gleich dem schnellsten Wanderer ist, wählen Sie unter den 'N' langsamsten Wanderern im aktuellen Schritt 'N' langsamster Wanderer, wie in '1' angegeben, und wählen Sie 'N' 'schnellste Wanderer

Hier ein Beispiel python-Skript, das tut dies: https://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py

Answer 9

Hier ist die Antwort in ruby:

@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

eine weitere Implementierung Rubin inspiriert von @ roc-Khalil' s Lösung

@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 

Ausgang:

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 
-------------------------