我正在尝试实现一个非常基本,非常简单的版本,它可以根据预定的类次列表和预定的人员列表生成学校时间表。

约束和基本设置

为了举例,让我们假设以下问题数据:

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

我知道代码很乱,但是其本质很简单:

我基本上是蛮力的,每次通过时,我都会“累积” 3个可能的类次,然后将它们与下一组可能的类次进行比较,直到我只选择了可能的类次到达终点为止。

我试图用一个简单的DP公式甚至是图形来思考,但是,我完全陷入了困境……也许以个人的变化而不是“变化的块”来思考更好,但是,现在,我米茫然。
我已经做了两天了,这让我很紧张

最佳答案

假设有n个人,有m个类次,并且您想为每个人分配s个(必须是s maximum matching的问题。匹配是一组边,因此在一个以上的边中不使用顶点。最大匹配是最大可能大小的匹配。构造图形:

  • 在A部分中,为每个人i创建s个顶点v_ {i,1},...,v_ {i,s}。
  • 在B部分中,为每个类次创建一个顶点。
  • 只要我可以使用类次j的人,都插入s边(v_ {i,1},j),(v_ {i,2},j),...,(v_ {i,s},j)。

  • 由于A中的2个顶点之间或B中的2个顶点之间没有边,因此生成的图是二分图。您可以使用Hopcroft-Karp算法在O(sqrt(| V |)| E |)时间中找到最大匹配项在第一个链接中;如果存在的话,这将为您提供最佳的解决方案(为每个人分配类次)。 | V | = sn + m,并且| E | = O(snm),因为在最坏的情况下,每个人都有可能列出每个类次,因此总时间复杂度将为O(sqrt(sn + m)snm)。

    Ari解决方案的反例

    Ari Hietanen's solution是一种很好的启发式方法,但是即使存在解决方案,它也可能无法找到解决方案,如以下示例问题实例所示。

    假设我们有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的算法将首先选择类次(第5列),因为只有2个人(A和F),此类次可以比所有其他类次(至少可以由3个人使用)更少的人使用。由于此时A和F均未分配任何类次,因此尚不确定是选择A还是F将5分配给类次,因此很可能会选择F-当然,如果它通过选择拥有最少的可用类次,它将这样做(因为F有4个可能的类次,而A有5个)。但是,一旦做出选择,就无法解决问题,因为这意味着需要以某种方式将4个类次1、2、3和4分配给A,B,C,D和E这5个人,这是不可能的。要查看确实存在解决方案,假设我们将类次5分配给A:现在,我们只需要将4个类次1、2、3和4分配给4个人B,C,D和E,以及3个类次6 ,7和8跨越三个人F,G和H,这很容易做到。

    07-24 09:51
    查看更多