过桥谜题的最优策略

• 下载 Bridge_Crossing_Puzzle-noexe.zip - 430.3 KB
• 下载 Bridge_Crossing_Puzzle.zip - 430.3 KB

引言

广义问题

一群 “n” 个人希望在夜间过桥。 每次最多可以过 “m” 个人，并且每个人都必须有一支手电筒。 只有一支手电筒可供 n 个人使用，因此必须安排某种穿梭安排才能返回手电筒，以便更多的人可以过桥。

每个人都有不同的过桥速度；一个组的速度由较慢成员的速度决定。 您的工作是确定一种策略，以最少的时间让所有 n 个人过桥。

例如：

n=4,m=2

4 个人的速度分别为 1,2,5,10。

任务是确定一种策略，以最少的时间让所有 4 个人过桥。

背景

为什么显而易见的解决方案在许多情况下不是最优解？

在显而易见的解决方案中，我们选择最高和最低的到另一边，然后由最低的人返回。 尽管如此，在某些情况下它仍然不是最优的。 原因是，当最高的人和最低的人到另一边时，所需的时间是最高的。 然后，最低的人返回。 现在，当第二高的人和最低的人一起走时，所需的时间是第二高的人。 因此，时间是最高的 + 第二高的人。

假设，最高的人和第二高的人一起走，第二高的时间被最高的时间所覆盖，这就是为什么时间只是最高的时间。 但是，如果我们由第二高的人返回，那将是非常大的时间损失。 这就是为什么在做这些事情时，要确保另一边有低时间的人，这样他们才能带着船返回。

这意味着，我们需要在另一边预留最少时间的人，这就是“预留策略”。

预留策略

如上所述，很多时候，最优解是通过预留策略获得的。 但仅使用显而易见的策略或预留策略并不能获得完整的解决方案。 它是分批使用的，批次大小取决于船的容量。 因为，对于预留策略，我们需要预留低时间的人进行返回旅行。

但是要预留多少人？

最优解只有在出行时，人数最多时才会发生，即船的容量。 这就是为什么在每个批次中，最多 “m” 次出行和 “m” 次返回旅行都会完成。

让我们用预留策略解决批次 1：

上述所需时间为 3+1+10+2+7+3= 26 秒

现在，我们已经通过预留策略解决了这个问题。 我们需要通过显而易见的策略评估相同数量的行程。

让我们用显而易见的策略解决批次 1

上述所需时间为 10+1+8+1+6+1=27 秒。

取显而易见策略和预留策略的最小值

在每个批次之后，最多 “m*(m-1)” 个高时间的人会到另一边。 在上面的示例中，在第一个批次之后，5、6、7、8、9、10 在另一边。 使用在另一边行驶批次所需时间最少的策略。 在上面的例子中，预留策略需要 26 秒，而显而易见的策略需要 27 秒。 所以，我们将使用预留策略进行批次 1。

解决完整问题

完整示例解释如下

使用代码

变量 “np” 是总人数，“bp” 是船的容量，arr[np] 给出了第 “np” 个人过桥的时间。

我们需要首先对保存时间值的数组进行排序，即 arr[]

// Sorting array:

for (i= 0;i<np-1;i++)
   {
      position =i;
 
      for (j= i+1;j<np;j++)
      {
         if(arr[position]>arr[j])
            position=j;
      }
      if ( position != i )
      {
         swap =arr[i];
         arr[i] = arr[position];
         arr[position] = swap;
      }
   }

现在，以下代码将通过显而易见的策略执行批次

// Obvious strategy: 

for(i=0;i<bp;i++)    
{
chkn[0]=1;finish1++;count=1;
for(j=np-1;count<bp && j>=0;j--)
{
    if(chkn[j]==0)
    {
        chkn[j]=1;finish1++;   // Finish gives the number of people present on another side
        if(count==1)  max=j;
        count++;    
    }  
}
ntime+=arr[max];
if(finish1==np) break;
else
{
chkn[0]=0;finish1--;
ntime+=arr[0];
}
}  

然后，在那之后，代码通过预留策略评估时间

// Reservation strategy: 

for(i=0;i<bp;i++)    
{
for(k=0;k<bp;k++)
{    
    if(chkr[k]==1) {chkr[k]=0;;rtime+=arr[k];finish2--;break;}
}
if(i==bp-1) break;
count=0;
for(j=np-1;count<bp && j>=0;j--)
{
    if(chkr[j]==0)
    {
        chkr[j]=1;finish2++;
        if(count==0)  max=j;
        count++;    
    }  
}
rtime+=arr[max];
if(finish2==np) break;
}

然后，我们取了这些的最小值

time=min(ntime,rtime);

并且对所有批次执行上述过程。

显示输出

现在，我们已经计算出最少的时间。 但是如何显示我们旅行的路径呢。 因为，我们只取了最少的时间。 我们没有保存任何路径。

解决方案是创建一个数组 “idnfyarr[]”。 如果 “idnfyarr[idnfy]” 的值为 1，则通过显而易见的策略执行，如果值为 2，则通过预留策略执行。

输出

输出-1

输出-2

输出-3