תוכנית לבעיית גשר ולפיד


רמת קושי קשה
נשאל לעתים קרובות נאמן eBay Quora Snapdeal Teradata פעמים באינטרנט
מערך תכנות דינמי

הצהרת בעיה

בעיית "הגשר והלפיד" קובעת שמקבלים לך זמן של זמן שאדם צריך לחצות את הגשר. מכיוון שהגיע הזמן, הוא כולל מספרים שלמים חיוביים. יחד עם הזמן נותנים לנו גשר, אותו אדם צריך לעבור. הגשר מאפשר לחצות רק שני אנשים בכל פעם. הם נושאים לפיד בזמן המעבר. ומכיוון שיש לפיד יחיד. אחד האנשים מהצד השני צריך לחזור ולקחת את הלפיד חזרה לצד ההתחלתי. כששני אנשים חוצים את הגשר, הם יכולים לעבור במהירות של אדם איטי יותר. מצא את הזמן המינימלי הכולל שבו כל האנשים יכולים לעבור את הגשר.

דוגמה

תוכנית לבעיית גשר ולפיד

timeToCross = {1, 2, 3}
6

הסבר: ראשית, אדם 1 ו -2 חוצים את הגשר. אז, עד עכשיו 2s עברו. כעת אדם 1 חוצה או חוזר חזרה לצד ההתחלתי. ואז אדם 2 ו -3 חוצים את הגשר. כך שהזמן הכולל שנלקח הוא = 2 + 1 + 3 = 6.

גישה לבעיית גשר ולפיד

גישה נאיבית

אנו יכולים להשתמש ברקורסיה כדי לכתוב תוכנית לבעיות בגשר ולפיד, כדי למצוא את כל ה תמורהשל הזמן לחצות מערך. ואז ראשית אנו מעבירים שני אנשים מצד אחד לצד השני עם הלפיד. ואז האדם המהיר ביותר מצד אחר (יעד) חוזר לצד הראשוני. על ידי כך אנו יכולים למצוא את הזמן המינימלי הנדרש לשליחת כל האנשים מצד אחד למשנהו העומדים בכל התנאים.

אך אלגוריתם זה דורש זמן אקספוננציאלי להפעלה. לפיכך נדרשת גישה יעילה.

גישה יעילה

אנו יכולים לכתוב תוכנית לבעיות גשר ולפיד באמצעות גישה יעילה תשתמש תכנות דינמי מכיוון שאנו יכולים לחלק את הבעיה הראשונית לבעיות משנה קטנות יותר אשר ניתן לחלק עוד יותר לבעיות משנה קטנות יותר. לכן, במקום לחשב או לפתור את בעיות המשנה הקטנות יותר פעמים רבות. אנו נאחסן את התוצאה ולאחר מכן נשלב תוצאות אלו כדי למצוא את תשובתנו. 

יש לציין כמה דברים בעת פתרון בעיה זו. כששני אנשים חוצים את הגשר, משתמשים במהירות של האדם האיטי יותר. יש להחזיר את הלפיד חזרה לצד הראשוני. כעת עלינו לייצג את האנשים בצד שמאל ובצד ימין. אנחנו יכולים גם לומר את האנשים בצד הראשוני ובצד היעד. 

אנחנו נשתמש bitmask לייצג את אחד הצדדים ואת הצד השני ניתן למצוא בקלות באמצעות כמה מניפולציות קצת. בהתחשב בכך שיש לנו שלושה אנשים, אנו משתמשים במסכת סיביות בגודל '3' כדי לייצג 3 אנשים. אם אדם אחד (שני) נמצא בצד היעד. מסיכת הסיביות המייצגת את הצד ההתחלתי תהיה 2, מסיכת הסיביות לצד היעד = (101 < XOR(מסיכת סיביות המייצגת צד ראשוני). לפיכך (2 ^ n-1) XOR (5) = 7 XOR 5 = 2.

עכשיו, נשתמש דו ממדי תכנות דינמי dp [מסכה] [כיוון תנועה], כאשר המסכה מייצגת את הזמן המינימלי הנדרש להעברת האדם שמייצג את המסכה משמאל לימין (כיוון תנועה = 0) או מימין לשמאל (כיוון תנועה = 1),

קופונים

קוד C ++ לבעיית Bridge and Torch

#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

קוד Java לבעיית Bridge and Torch

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)

אנו משתמשים במסכת סיביות כדי לייצג מספרים N, התורם ל- 2 ^ n. ואז אנו בודקים כל זוג באמצעות שני לולאות מקוננות שנותנות לנו גורם של N ^ 2. לפיכך מורכבות הזמן היא O (2 ^ N * N ^ 2).

מורכבות בחלל: O (2 ^ N)

אנו משתמשים ב- Dp מעל מסיכת סיביות כאן. ומכיוון שמערך ה- DP שלנו תלוי בכיוון ובמסכת סיביות, שם יש רק 2 כיוונים. יש לנו מורכבות שטח אקספוננציאלית של O (2 ^ N).