过桥难题

有 an entire PDF ( alternate link )这解决了这个问题的一般情况(在形式证明中)。

17分钟-这是一个典型的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.

一般来说,最大的问题/最慢的人应该总是放在一起,并进行足够的最快的旅行,以便每次都能够在不使用慢速资源的情况下将光线带回。

我会在Dice.com上放一个虚假的招聘广告,然后在面试中问这个问题,直到有人答对为止,以此来解决这个问题。

根据维基百科

这个谜题早在1981年就出现在《谜题和游戏的超级策略》一书中。在这个版本的拼图中,A、B、C和D分别需要5、10、20和25分钟才能完成,时间限制为60分钟

然而,这一问题在《你将如何移动富士山》一书中出现后便广为流行

这个问题可以推广到N个人,他们需要不同的时间过桥。

下面的程序适用于一般N个人员及其时间。

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

输出:

过桥总时间为:17

对于

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

输出:

过桥的总时间是:25分钟

对于

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

输出

以下是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}"

@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

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

对于这样一个小的问题空间,对所有可能性的彻底搜索是很简单的。广度或深度优先。这是一个简单的CS问题。

我更喜欢传教士和食人族的问题

17--一个非常常见的问题

-&燃气轮机;1-2 = 2

-&燃气轮机;5,10=10(他们都不必返回)
<-1 = 1

都在另一边
总数=2+2+10+1+2=17

考虑到将有两条边,一条边和二条边,N人应从一条边穿过二条边。过桥人数限制在L人以内的逻辑是-

步骤1:将L个最快的成员从1侧移动到2侧

第四步:在第二组中,把最快的人带回来

这里有一个C#代码,用于n个用户,一次只有2个用户。这将占用N个用户,可以在运行时指定。然后,它将接受N个人的姓名和时间。输出还指定了可能的最短时间的迭代。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace RiverCrossing_Problem
{
    class Program
    {
        static void Main(string[] args)
        {
            Dictionary<string, int> Side1 = new Dictionary<string, int>();
            Dictionary<string, int> Side2 = new Dictionary<string, int>();

            Console.WriteLine("Enter number of persons");
            int n = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Enter the name and time taken by each");

            for(int a =0; a<n; a++)
            {
                string tempname = Console.ReadLine();
                int temptime = Convert.ToInt32(Console.ReadLine());
                Side1.Add(tempname, temptime);
            }

            Console.WriteLine("Shortest time and logic:");
            int totaltime = 0;
            int i = 1;
            do
            {
                KeyValuePair<string, int> low1, low2, high1, high2;
                if (i % 2 == 1)
                {
                    LowestTwo(Side1, out low1, out low2);
                    Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", low1.Key, low2.Key, low2.Value);
                    Side1.Remove(low2.Key);
                    Side1.Remove(low1.Key);
                    Side2.Add(low2.Key, low2.Value);
                    Side2.Add(low1.Key, low1.Value);
                    totaltime += low2.Value;

                    low1 = LowestOne(Side2);
                    Console.WriteLine("{0} comes back to side 1, time taken = {1}", low1.Key, low1.Value);
                    totaltime += low1.Value;
                    Side1.Add(low1.Key, low1.Value);
                    Side2.Remove(low1.Key);
                    i++;
                }
                else
                {
                    HighestTwo(Side1, out high1, out high2);
                    Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", high1.Key, high2.Key, high1.Value);
                    Side1.Remove(high1.Key);
                    Side1.Remove(high2.Key);
                    Side2.Add(high1.Key, high1.Value);
                    Side2.Add(high2.Key, high2.Value);
                    totaltime += high1.Value;

                    low1 = LowestOne(Side2);
                    Console.WriteLine("{0} comes back to side 1, time taken = {1}", low1.Key, low1.Value);
                    Side2.Remove(low1.Key);
                    Side1.Add(low1.Key, low1.Value);
                    totaltime += low1.Value;
                    i++;
                }
            } while (Side1.Count > 2);

            KeyValuePair<string, int> low3, low4;
            LowestTwo(Side1, out low3, out low4);
            Console.WriteLine("{0} and {1} goes from side 1 to side 2, time taken = {2}", low3.Key, low4.Key, low4.Value);
            Side2.Add(low4.Key, low4.Value);
            Side2.Add(low3.Key, low3.Value);
            totaltime += low4.Value;

            Console.WriteLine("\n");
            Console.WriteLine("Total Time taken = {0}", totaltime);

        }

        public static void LowestTwo(Dictionary<string, int> a, out KeyValuePair<string, int> low1, out KeyValuePair<string, int> low2)
        {
            Dictionary<string, int> b = a;
            low1 = b.OrderBy(kvp => kvp.Value).First();
            b.Remove(low1.Key);
            low2 = b.OrderBy(kvp => kvp.Value).First();
        }

        public static void HighestTwo(Dictionary<string,int> a, out KeyValuePair<string,int> high1, out KeyValuePair<string,int> high2)
        {
            Dictionary<string, int> b = a;
            high1 = b.OrderByDescending(k => k.Value).First();
            b.Remove(high1.Key);
            high2 = b.OrderByDescending(k => k.Value).First();
        }

        public static KeyValuePair<string, int> LowestOne(Dictionary<string,int> a)
        {
            Dictionary<string, int> b = a;
            return b.OrderBy(k => k.Value).First();
        }
    }
}

随机输入的样本输出为7,在本例中为7,每次2人交叉:

Enter number of persons
7
Enter the name and time taken by each
A
2
B
5
C
3
D
7
E
9
F
4
G
6
Shortest time and logic:
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
E and D goes from side 1 to side 2, time taken = 9
C comes back to side 1, time taken = 3
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
G and B goes from side 1 to side 2, time taken = 6
C comes back to side 1, time taken = 3
A and C goes from side 1 to side 2, time taken = 3
A comes back to side 1, time taken = 2
A and F goes from side 1 to side 2, time taken = 4


Total Time taken = 40

最短时间的公式是B+A+D+B+B或3B+A+D

看看这个项目,还有一个项目增加的问题。虽然我还没有经历过,但我猜公式仍然适用,只需将第二项乘以3的所有项相加,再加上除第二慢外的所有项的总和。 然后5个项目是3x秒+第一、第三和第五。 我想用这个程序检查一下。

3 x第二个+最快+每个后续对中最慢的总和。

查看优化解决方案的步骤,想法是 -右-对于右边的两个项目,最快的是第一和第二快, -左-然后加上最快返回的单个项目是最快的项目 -右-带上最慢的2个项目,这将只考虑最慢的项目,而忽略第二个最慢的项目。 -最后右转-又是第一和第二快

所以再次总结=第二快的跑3次,最快的跑一次,最慢的跑第二慢。

一个简单的算法是:假设‘N’是可以同时穿越的人数,一个人必须背着火炬穿越

1. 当将人从第一面移动到第二面时,应优先考虑“N”个最慢的步行者
2. 始终使用最快的步行者从第二面到第一面传递火炬
3. 当把人从第一面移到第二面时,要考虑下一步谁会把火炬带回来。如果下一步中火炬手的速度等于当前步骤中“N”个最慢步行者中的最快步行者,则选择“N”个最慢步行者,而不是“1”中给出的“N”个最慢步行者

https://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py