Бридж ба бамбарын асуудал


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Accolite Ebay Quora Snapdeal Teradata Times Интернет
Array Динамик програмчлал

Асуудлын мэдэгдэл

“Гүүр ба бамбар” -ны асуудалд та гүүрээр гарах хүний ​​цуваа цагийг зааж өгдөг. Цаг нь болсон тул эерэг бүхэл тоонуудаас бүрдэнэ. Цаг хугацаатай зэрэгцэн бидэнд хүн гатлах хэрэгтэй гүүр өгдөг. Гүүр нь нэг удаад хоёр хүн л нэвтрэх боломжийг олгодог. Тэд гаталж байхдаа бамбар барьдаг. Ганц бамбар байдаг тул. Нөгөө талын хүмүүсийн нэг нь эргэж ирээд бамбарыг эхэнд нь аваачих ёстой. Хоёр хүн гүүрээр гарахдаа арай удаан хүний ​​хурдаар давж гардаг. Бүх хүмүүс гүүрээр гарах хамгийн бага хугацааг ол.

Жишээ нь

Бридж ба бамбарын асуудал

timeToCross = {1, 2, 3}
6

Тайлбар: Нэгдүгээрт, 1 ба 2-р хүмүүс гүүрээр гардаг. Тиймээс, одоо хүртэл 2 секунд өнгөрчээ. Одоо хүн 1 хөндлөн огтлолцох эсвэл буцаж эргэж буцаж ирнэ. Дараа нь 2 ба 3-р хүмүүс гүүрээр гарна. Тиймээс авсан нийт хугацаа = 2 + 1 + 3 = 6 болно.

Гүүр ба бамбартай холбоотой асуудал

Гэнэн хандлага

Бид рекурсийг ашиглан гүүр ба бамбартай холбоотой програм бичих, бүгдийг нь олох боломжтой Сонголт хийхмассивыг гатлах цаг. Дараа нь эхлээд бид хоёр хүнийг бамбараар нэг талаас нөгөө рүү шилжүүлнэ. Дараа нь өөр (очих газар) -ын хамгийн хурдан хүн эхний тал руугаа эргэж ирдэг. Ингэснээр бид бүх хүмүүсийг нэг талаас нөгөөд шилжүүлэхэд шаардагдах хамгийн бага хугацааг бүх нөхцлийг хангаж чадна.

Гэхдээ энэ алгоритм нь ажиллуулахын тулд экспоненциал цаг хугацаа шаарддаг. Тиймээс үр дүнтэй арга барил шаардагдана.

Үр ашигтай арга

Бид гүүр, бамбартай холбоотой програмыг үр дүнтэй аргыг ашиглан бичиж болно динамик програмчлал Учир нь бид эхний асуудлыг жижиг дэд асуудлуудад хувааж болох бөгөөд үүнийг жижиг дэд асуудлуудад хувааж болно. Тиймээс, жижиг дэд асуудлуудыг олон удаа тооцоолох эсвэл шийдвэрлэхийн оронд. Бид үр дүнг хадгалж, дараа нь эдгээр үр дүнг нэгтгэж хариултаа олох болно. 

Энэ асуудлыг шийдвэрлэх явцад анхаарах хэдэн зүйл байна. Хоёр хүн гүүрээр гарахад удаан хүний ​​хурд ашиглагддаг. Бамбарыг эхний тал руу буцааж өгөх шаардлагатай. Одоо бид зүүн, баруун талын хүмүүсийг төлөөлөх хэрэгтэй. Бид эхний болон очих тал дээр байгаа хүмүүсийг хэлж болно. 

Бид ашиглах болно битмаск талуудын аль нэгийг төлөөлөхийн тулд нөгөө талыг нь жаахан заль мэхийг ашиглан олж болно. Бид гурван хүнтэй гэж үзээд 3 хүнийг төлөөлөхдөө '3' хэмжээтэй битмаск ашигладаг. Хэрэв нэг хүн (2-рт) хүрэх газар байгаа бол. Эхний талыг илэрхийлсэн битмаск 101, очих тал = = (1 < XOR(эхний талыг илэрхийлсэн битмаск). Тиймээс (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

Одоо бид ашиглах болно 2 хэмжээст Динамик програмчлал dp [маск] [хөдөлгөөний чиглэл], маск маскыг төлөөлж буй хүнийг зүүнээс баруун тийш (хөдөлгөөний чиглэл = 0) эсвэл баруунаас зүүн тийш (хөдөлгөөний чиглэл = 1) шилжүүлэхэд шаардагдах хамгийн бага хугацааг илэрхийлдэг маск

код

Bridge and Torch Problem-т зориулсан C ++ код

#include <bits/stdc++.h>
using namespace std;

int solveBridgeAndTorchProblem(int mask, bool direction, vector<int> &timeToCross, vector<vector<int>> &dp)
{
    int n = timeToCross.size();
    // if nobody is left to transfer
  if (!mask)
    return 0;
    if(dp[mask][direction]!=-1)
        return dp[mask][direction];

  int transferredMask = ((1<<n)-1)^mask;
    int res = 0;
  // transfer people from left to right (from destination to start)
  if (direction == 1) {
    int minRow = INT_MAX, person;
    for (int i = 0; i < n; ++i) {
            // choose the person with smallest time to cross bridge
      if (transferredMask & (1 << i)) {
        if (minRow > timeToCross[i]) {
          person = i;
          minRow = timeToCross[i];
        }
      }
    }

    // now send this person to let and solve for smaller problem
    res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
  }
  else {

    // __builtin_popcount() counts the bits in mask
    if (__builtin_popcount(mask) == 1) {
      for (int i=0;i<n;++i) {
        // since there is only a single person on starting side, return him
        if (mask&(1<<i)) {
          res = timeToCross[i];
          break;
        }
      }
    }
    else {

      // find the minimum time by solving for each pair
      res = INT_MAX;
      for(int i=0;i<n;++i) {
                // if ith person is not on right side, then do nothing
        if(!(mask&(1<<i)))
          continue;
                // else find another person and try to cross the bridge
        for(int j=i+1;j<n;++j) {
          if(mask&(1<<j)){
            // time to cross the bridge for current pair
            int val = max(timeToCross[i], timeToCross[j]);
            // solve for smaller subproblems
            val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
            // update the answer
            res = min(res, val);
          }
        }
      }
    }
  }
  return dp[mask][direction] = res;
}

int main()
{
  int n;cin>>n;
  vector<int> timeToCross(n);
  for(int i=0;i<n;i++)cin>>timeToCross[i];
  vector<vector<int>> dp(1<<20, vector<int>(2,-1));
  int mask = (1<<n)-1;
  cout << solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
  return 0;
}
5
25 6 5 8 4
54

Bridge and Torch Problem-т зориулсан Java код

import java.util.*;

class Main{

    static int countBits(int n){
        int nn = n;
        int cnt = 0;
        while(n>0){
            if((n&1) == 1)
                cnt++;
            n = n/2;
        }
        n = nn;
        return cnt;
    }

    static int solveBridgeAndTorchProblem(int mask, int direction, int timeToCross[], int dp[][])
    {
        int n = timeToCross.length;
        // if nobody is left to transfer
        if (mask==0)
            return 0;
        if(dp[mask][direction]!=-1)
            return dp[mask][direction];

        int transferredMask = ((1<<n)-1)^mask;
        int res = 0;
        // transfer people from left to right (from destination to start)
        if(direction == 1) {
            int minRow = Integer.MAX_VALUE, person=0;
            for(int i = 0; i < n; ++i) {
                // choose the person with smallest time to cross bridge
                if((transferredMask & (1 << i)) > 0) {
                    if (minRow > timeToCross[i]) {
                        person = i;
                        minRow = timeToCross[i];
                    }
                }
            }

            // now send this person to let and solve for smaller problem
            res = timeToCross[person] + solveBridgeAndTorchProblem(mask|(1 << person),direction^1, timeToCross, dp);
        }
        else {

            // countBits() counts the bits in mask
            if (countBits(mask) == 1) {
                for (int i=0;i<n;++i) {
                    // since there is only a single person on starting side, return him
                    if((mask&(1<<i))!=0) {
                        res = timeToCross[i];
                        break;
                    }
                }
            }
            else {

                // find the minimum time by solving for each pair
                res = Integer.MAX_VALUE;
                for(int i=0;i<n;++i) {
                    // if ith person is not on right side, then do nothing
                    if((mask&(1<<i))== 0)
                        continue;
                    // else find another person and try to cross the bridge
                    for(int j=i+1;j<n;++j) {
                        if((mask&(1<<j))>0){
                            // time to cross the bridge for current pair
                            int val = Math.max(timeToCross[i], timeToCross[j]);
                            // solve for smaller subproblems
                            val += solveBridgeAndTorchProblem(mask^(1<<i)^(1<<j), direction^1,timeToCross,dp);
                            // update the answer
                            res = Math.min(res, val);
                        }
                    }
                }
            }
        }
        return dp[mask][direction] = res;
    }

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] timeToCross = new int[n];
        for(int i=0;i<n;i++)
            timeToCross[i] = sc.nextInt();
        int dp[][] = new int[1<<20][2];
        for(int i=0;i<(1<<20);i++){
            dp[i][0] = -1;
            dp[i][1] = -1;
        }
        int mask = (1<<n)-1;
        int answer = solveBridgeAndTorchProblem(mask, 0, timeToCross, dp);
        System.out.println(answer);
    }

}
5 
25 6 5 8 4
54

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал: O (2 ^ N * N ^ 2)

Бид 2 ^ n-д хувь нэмэр оруулах N тоог илэрхийлэхийн тулд битмаск ашиглаж байна. Дараа нь бид N ^ 2 коэффициентийг өгдөг хоёр үүрлэсэн гогцоог ашиглан хос бүрийг шалгана. Тиймээс цаг хугацааны нарийн төвөгтэй байдал нь O (2 ^ N * N ^ 2) болно.

Сансрын нарийн төвөгтэй байдал: O (2 ^ N)

Бид энд Dp bitmask дээр ашиглаж байна. Манай АН массив нь зөвхөн 2 чиглэлтэй чиглэл, битмаскаас хамааралтай тул. Бидэнд O (2 ^ N) -гийн орон зайн нарийн төвөгтэй байдал бий.