Bridge Crossing Puzzle's Optimal Strategy

• Download Bridge_Crossing_Puzzle-noexe.zip - 430.3 KB
• Download Bridge_Crossing_Puzzle.zip - 430.3 KB

Introduction

Generalized Puzzle:

A group of “n” people wish to cross a bridge at night. At most “m” people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross.

Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time.

For e.g.

n=4,m=2

Speed of 4 peoplle are 1,2,5,10.

Task  is to determine a strategy that gets all 4  people across the bridge in the minimum time.

Background

Why obvious solution is not optimal solution in many cases?

In obvious solution, we take highest & lowest to go to another side & returns with lowest person. Still, it’s not optimal in some cases. Reason is when highest goes with lowest on another side, time required is of highest. Then, Lowest returns . Now, when second highest goes with lowest, time required is of second highest. So, time is highest + second highest.

Suppose, highest goes with second highest, second highest time is covered by highest time & that’s why, time is only highest time. But if we return with  second highest, it will be very loss of time. That’s why, while doing such things, make sure that, you have low time persons on the another side so that, they can return with the boat.

This means,  we need to reserve the minimum time persons on the another side and this is the “reservation strategy”.

Reservation Strategy

As explained above, many times, optimal solution is obtained with the reservation strategy. But only obvious strategy or reservation strategy is not used for full solution. It’s used in batches and that batch size depends upon the capacity of the boat. Because, for the reservation strategy, we need to reserve low time persons for the return trip.

But how many people to reserve?

Optimal solution will only occur when in going trip, number of persons are maximum i.e. capacity of the boat. That’s why, in each batch, maximum “m” going trip & “m” return trips are done.

Let us solve the batch-1 by reservation strategy: 

Time taken by above is 3+1+10+2+7+3= 26 sec

Now, we have solved by reservation strategy. Same number of trips we need to evaluate by the obvious strategy.

Let us solve batch-1 by obvious strategy:

Time taken by above is 10+1+8+1+6+1=27 sec.

Taking minimum of obvious & reservation strategy

After each batch, maximum “m*(m-1)” high time persons goes on the another side. In above example, after first batch, 5,6,7,8,9,10 are on another side. Strategy which takes minimum time to travel batch on another side is used. In the above example, reservation strategy takes 26 seconds & obvious strategy takes 27 seconds. So, we will use batch-1 by reservation strategy.

Solving full problem

Full example is explained as follows:

Using the code

Variable “np” is the total number of people, “bp” is the capacity of the boat & arr[np] gives the timing of “np”th person to cross the bridge.

We need to first sort the array in which timing values are saved i.e. 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;
      }
   }

Now, following code will execute the batch by obvious strategy:

// 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];
}
}  

Then, after that, code evaluates time by reservation strategy:

// 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;
}

Then, we have taken the minimum of those:

time=min(ntime,rtime);

& do  the above procedure for all the batches.

Showing Output

Now, we have calculated the minimum time. But how to show the Path in which  we have travelled. Because, we’ve taken just minimum time. We‘ve not saved any path.

Solution is to create one array “idnfyarr[]”. If value of “idnfyarr[idnfy]”=1 then, do it by obvious strategy & if it is 2 then, do it by reservation strategy.

Output

O/p-1:

O/p-2:

O/p-3: