制定基本的学校时间表

Question

我正在尝试实现一个非常基本的，非常简单的版本，根据预先确定的班次列表和预先确定的人员列表生成一份学校时间表。

约束与基本设置

为了举例，让我们假设以下问题数据：

5-大家，我们叫他们A，B，C，D，E，希望他们各自的时间表被分配。

每个人都有一个轮班列表，先前选择过。

每周有5天，让我们假设每天有3班，所以，我们有一个矩阵，3行，5列。表示移动的单元格从上到下从左到右编号，从1开始。

名单：

A= {1,2,3,5,10,11}

B= {6,7,1,3,8,15}

C= {2,6,8,9,12,13}

D= {3,4,5,6,7,8}

E= {6,8,10,11,13,14}

在确定所有的轮班之后，时间表将是：

A-5，10 11

B- 1,7,15

C- 2,6,12

D- 3,4,9

E-8-13 14

我怎样才能把这个概念推广到现实世界，比如说20人，40班，每个人从8班名单中选出2人。

我的代码如下：

 #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <cmath>
    using namespace std;

    #define OPT_DEGREE 300

    #define DEBUG 0
    #define vpbvi vector<pair<bool,vector<ULL> > >
    #define ULL unsigned long long

    static string dict[20];

    void showV(vector<ULL> & v)
    {
        for(int i = 0; i < v.size(); i++)
        {
            cout << v[i] << " ";
        }
        cout << endl;
    }

    inline bool do_vectors_intersect(vector<ULL> v1, vector<ULL> v2)
    {
        unsigned long long int target_sz = v1.size()+v2.size();
        set<ULL> s;
        for(int i = 0; i < v1.size(); i++)
            s.insert(v1[i]);
        for(int j = 0; j < v2.size(); j++)
            s.insert(v2[j]);

        return !(static_cast<ULL>(s.size()) == target_sz); //True se ha intersecçao False c.c.
    }

    void generateAllPossibleShifts(vector<vector<ULL> > & auxiliar, vector<ULL> & _shifts, int N, int K)
    {
        string bitmask(K, 1); // K leading 1's
        bitmask.resize(N, 0); // N-K trailing 0's

         // print integers and permute bitmask
         do {
                vector<ULL> aux;
                for (int i = 0; i < N; ++i) // [0..N-1] integers
                {
                    if (bitmask[i])
                    {
                        aux.push_back(_shifts[i]);
                        if(DEBUG){
                            cout << " " << _shifts[i];}
                    }
                }
                if(DEBUG){
                    cout << endl << aux.size() << " Done. Create Pair and add to scheudle." << endl;}
                    pair<bool,vector<ULL> > pbvi = make_pair(true,aux);

                    for(int i = 0; i < aux.size();i++)
                        if(DEBUG){
                        cout << "aux[" <<i<<"] = " << pbvi.second[i] << endl;}
                    auxiliar.push_back(aux);
                   // fullVec.push_back(pbvi);
                    aux.resize(0); //vector is cleared here
                    if(DEBUG){
                    cout << "Clear vec" << endl;
                    cout << pbvi.second.size() << " Done" << endl;
                    cout <<  endl;}
            } while ( prev_permutation(bitmask.begin(), bitmask.end()));
    }

    vector<ULL> SumVecs(vector<ULL> & a, vector<ULL> & b)
    {
        vector<ULL> newVec;
        for(int i = 0; i < a.size(); i++)
            newVec.push_back(a[i]);
        for(int i = 0; i < b.size(); i++)
            newVec.push_back(b[i]);
        return newVec;
    }

    void AppendToFirst(vector<ULL> & fst, vector<ULL> & snd, int ind)
    {
        for(int k = 0; k < snd.size(); k++)
        fst.push_back(snd[k]);
    }

    void OptimizeBeforeNextPassLeft(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
    {
        int opt = 0;
        for(int i = 0; i < bsc.size(); i++)
        {
            for(int j = 0; j < arg2.size(); j++)
            {
                if(do_vectors_intersect(bsc[i],arg2[j])==true){
                    arg2.erase(remove(arg2.begin(), arg2.end(), arg2[j]), arg2.end());
                    }
            }
        }
    }

    void OptimizeBeforeNextPassRight(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
    {
        int opt = 0;
        for(int i = bsc.size()-1; i >= 0 ; i--)
        {
            for(int j = 0; j < arg2.size(); j++)
            {
                if(do_vectors_intersect(bsc[i],arg2[j])==true){
                    bsc.erase(bsc.begin()+i);
                    }
            }
        }
    }

    void HardOptimize(vector<vector<ULL> > & bsc, vector<vector<ULL> > & arg2)
    {
        int opt = 0;
        for(int i = bsc.size()-1; i >= 0 ; i--)
        {
            for(int j = 1; j < arg2.size(); j+=2)
            {
                if(do_vectors_intersect(bsc[i],arg2[j])==true){
                    bsc.erase(bsc.begin()+i);
                    }
            }
        }
    }

    //Recursive Function that filters bad attempts and uses "basic" look-ahead technique to narrow search space
    //while building an iterative solution. Can still be optimized.
     void ExpandSearchSpace(vector<vector<vector<ULL> > > & v, vector<vector<ULL> > & buildSol, int guesslvl, vector<vector<ULL> > & placeholder)
    {
       if(guesslvl==4) //Num de pessoas-1
       {
           // cout << "inside ret " << endl << buildSol.size();
            placeholder = buildSol;
           return;
       }
       else
       {
            vector<vector<ULL> > BuildSolCp;
            const int ssz = buildSol.size();
            for(int i = 0; i < ssz;i++)
            {
                vector<ULL> arg1 = buildSol[i];
                const int ssz2 = v[guesslvl+1].size();
               //cout << "arg1.sz() = " << arg1.size() << endl;
                for(int j = 0; j < ssz2;j++)
                {
                    if(do_vectors_intersect(buildSol[i], v[guesslvl+1][j])==false){
                 //   cout << "Iter " << guesslvl << "   " << buildSol[i].size() << " ";
                   vector<ULL> arg2 = v[guesslvl+1][j];
                 // cout << "arg2 " << arg1.size() << " --- ";
                  vector<ULL> auxi = SumVecs(arg1,arg2);
                 // cout << "OLFOFKODSJFDSIHFDSFDS" << endl;
                     BuildSolCp.push_back(auxi);
                   //  cout << "PUSHDED SDUSHFUDSHF"<<endl;

                    }
                }
            }

            guesslvl++;
            if(BuildSolCp.size()> 1000){
            cout << "WE neeed optimize Jon" << endl;
            for(int i = 0; i < BuildSolCp.size();i++)
            showV(BuildSolCp[i]);
            vector<vector<ULL> > s= v[guesslvl+1];
            //vector<vector<ULL> > s3= v[guesslvl+4];
          //  vector<vector<ULL> > s4= v[guesslvl+5];
         //  OptimizeBeforeNextPassLeft(BuildSolCp, s);
         OptimizeBeforeNextPassLeft(buildSol,v[guesslvl+2]);

          //  OptimizeBeforeNextPassRight(BuildSolCp, s);}
           // OptimizeFromBothSidesAtOnce(BuildSolCp, v[guesslvl+1][j]);
           }

            cout << BuildSolCp.size() << " " << guesslvl << endl;

           ExpandSearchSpace(v,BuildSolCp, guesslvl, placeholder);
       }
      // cout << "end" << endl;
    }

    void ShowPrettyScheudle(vector<vector<ULL> > sol)
    {
        vector<int> scheudle(15);
        for(int j = 0; j <= 10; j+=5){
            for(int i = j; i < j+5; i++)
            {
                cout << sol[0][i] << "\t | ";
            }
            cout << endl;}

    }

    int main()
    {
        static vector<vector<ULL> > WorkerVec1,WorkerVec2,WorkerVec3,WorkerVec4, WorkerVec5;
        static vector<vector<ULL> > WorkerVec6,WorkerVec7,WorkerVec8,WorkerVec9, WorkerVec10;
        static vector<vector<ULL> > WorkerVec11,WorkerVec12,WorkerVec13,WorkerVec14, WorkerVec15;
        static vector<vector<ULL> > WorkerVec16,WorkerVec17,WorkerVec18,WorkerVec19, WorkerVec20;
        vector<vector<ULL> > sol;
        static vector<vector<vector<ULL>>> v;

        vector<ULL> v1{5,10,11,3,1,2}, v2{1,7,3,15,6,8} ,v3{2,6,12,8,13,9}, v4{3,4,5,6,7,8},v5{6,8,10,11,13,14};
        generateAllPossibleShifts(WorkerVec1, v1,6,3);
        generateAllPossibleShifts(WorkerVec2, v2,6,3);
        generateAllPossibleShifts(WorkerVec3, v3,6,3);
        generateAllPossibleShifts(WorkerVec4, v4,6,3);
        generateAllPossibleShifts(WorkerVec5, v5,6,3);
        v.insert(v.end(), {WorkerVec1,WorkerVec2, WorkerVec3,WorkerVec4, WorkerVec5} );
        cout << "SIZE OF v[0] in main is " << v[0].size() << endl; //20
        for(int i = 0; i < v[0].size(); i++)
        {
            sol.push_back(v[0][i]);
        }
        cout << sol.size() << endl; //20
        vector<vector<ULL> > plcholder;
        cout << "OMG " << plcholder.size()<<endl;
        ExpandSearchSpace(v,sol,0,plcholder);

        cout << sol.size() << endl;
        for(int i = plcholder.size()-1; i >= 0; i--){
            cout << plcholder[i].size() << endl;
            if(plcholder[i].size()==15){
                 cout << "FUCK YEA ";showV(plcholder[i]);
                 cout << endl << endl;
                vector<vector<ULL> > vect{plcholder[i]};
                ShowPrettyScheudle(vect);
                break;}
                }
        cout << endl;
       // cout << endl << Ans[0].size() << " " << Ans[1].size() << " " << Ans[2].size() << " " << Ans[3].size();
        return 0;
    }

我知道代码很混乱，但是，它的本质很简单：

我基本上做了一个蛮力，在每次通过时，我“积累”了三个可能的移动块，并将它们与下一组可能的移位进行比较，直到我到达最后，只选择可能的移位。

我试着用简单的DP公式，甚至是图表来思考，但是，我完全被困在.也许用个人轮班而不是“轮班”来思考更好，但现在，我不知所措。这件事我已经讨论了两天了，这让我很紧张

Answer 1

假设有n个人，m个轮班可用，并且您希望将s(必然是s <= m/n)转移分配给每个人。这个问题可以建模为在二分图中寻找最大匹配的问题。匹配是一组边缘，在多个边缘中不使用顶点；最大匹配是最大可能大小的匹配。要构造图形：

• 在第A部分中，为每个人i创建s顶点v_{i,1}，…，v_{i，s}。
• 在B部分中，为每个移位创建一个顶点。
• 每当我可以使用shift j时，插入s边(v_{i,1}，j)，(v_{i,2}，j)，.，(v_{i，s}，j)。

生成的图是二部图，因为A中的两个顶点之间没有边，B中的两个顶点之间没有边，所以可以使用第一个链接中的Hopcroft-Karp算法，在O(sqrt(sqrt(sqrt(x=v)的时间内找到一个最大匹配；这将给出一个最优解(每个人都被分配了s移位)。在这里，由于在最坏的情况下，每个人都会列出每一个移位的可能性，所以总的时间复杂度将是O(sqrt( sn+m )snm)。

Ari解的反例

阿里·希塔宁(氏)液是一种很好的启发式方法，但即使存在，它也可能找不到解决方案，如下面的示例问题实例所示。

假设我们有8个人A，B，.，H和8班1，2，.，8，我们想给每个人分配一个班次，可能的轮班矩阵如下所示：

  12345678
A XXXXX...
B XXXX....
C XXXX....
D XXXX....
E XXXX....
F ....XXXX
G .....XXX
H .....XXX

其中X表示该行中的人员可以在该列中执行移位操作。

Ari的算法将首先选择shift (列) 5，因为只有2个人(A和F)可以使用这个移位比所有其他轮班(至少3个人都可以使用)更少。因为在这一点上，A和F都没有任何移位，所以还没有决定它是选择A还是F来将移位5分配给它，所以它有可能选择F --当然，如果它通过选择有最少可用移位的人来打破联系，它就会这样做(因为F有4种可能的移位，而A有5种可能的移位)。但是一旦它作出这个选择，它就没有办法解决这个问题，因为这就意味着，四班一，二，三和四需要在A，B，C，D和E五个人之间分配，这是不可能的。要知道一个解决方案确实存在，假设我们将移位5分配给A，现在我们只需要将4班1，2，3和4分散到B，C，D和E上，3班6，7和8在F，G和H三人之间，这很容易做到。

Answer 2

作为你的例子--它很简单，你可以尝试下面的算法，

1. 首先，把轮班和人联系起来
2. 循环遍历所有移位的
   1. 选择与它联系最少的人的转变
   2. 用最少的班次分配给其中的一个人。

​

该算法在O(N*M)中工作，其中N是移位，M是人。它也总是找到一个解决方案，但不一定是正确的解决方案。请看j_random_hacker的答案。

下面是一个不检查输入数据是否有效的实现。我将移位15改为0，用向量索引映射。

#include <list>
#include <vector>
#include <iostream>
#include <algorithm>

class VectorComp{
public:
  bool operator()(const std::vector<int>& v1,const std::vector<int>& v2){
    if (v1.size()==0) return false;
    if (v2.size()==0) return true;
    return v1.size()<v2.size();
  }
};

int main(){
  std::vector<std::vector<int>> personToShift{{1,2,3,5,10,11},
                                              {6,7,1,3,8,0},
                                              {2,6,8,9,12,13},
                                              {3,4,5,6,7,8},
                                              {6,8,10,11,13,14}};

  //Map shifts to persons
  std::vector<std::vector<int>> shiftToPerson(15);
  for (size_t i=0;i<personToShift.size();++i){
    for (auto s:personToShift[i]){
      shiftToPerson[s].push_back(i);
    }
  }

  //Result vector
  std::vector<std::vector<int>> res(personToShift.size());

  for (size_t i=0;i<shiftToPerson.size();++i){
    auto minPersonsForShift = std::min_element(shiftToPerson.begin(),
                                              shiftToPerson.end(),
                                              VectorComp());//Find shift with minimum persons
    size_t shift=minPersonsForShift-shiftToPerson.begin();
    size_t minShifts=shiftToPerson.size();
    size_t minPerson=0;
    for (auto person:*minPersonsForShift){//Find person in shift with   minimum shifts so far
      if (res[person].size()<minShifts){
        minPerson=person;
        minShifts=res[person].size();
      }
    }
    res[minPerson].push_back(shift);//Update the result
    shiftToPerson[shift].clear();//Mark the shift assigned by clearing the vector
  }

  for (size_t i=0;i<res.size();++i){//Print the result
    std::cout << char(('A'+i)) << " - ";
    for (auto t:res[i]){
      std::cout << t << " ";
    }
    std::cout << std::endl;
  }    
}       

输出：

A - 1 2 11 
B - 0 7 3 
C - 9 12 13 
D - 4 5 6 
E - 14 10 8