1

私は現在、大学の試験時間割スケジューリングのソリューションに取り組んでいます。遺伝的アルゴリズムの使用を考えていました。

今、私は簡単な例から始めました。これは、私がこれらすべてに慣れていないため、何が起こっているのかを把握するためです。この例では、10 件の試験、6 人の学生、および 6 つの利用可能な時間枠があります。[3 1 4 1 3 5 5 6 4 2]タイムスロットを表す 1 ～ 6 の値を持つビット文字列に 10 の位置があるような染色体を表しています。例: -スロットなど...

ここで、各学生が受けている試験を表す次の配列があるとします。

int[][] students_exams = 
{
    {3, 1, 2, 5, 8},   // student 1
    {10, 4, 5, 7},     // student 2
    {1, 2, 3, 6},      // student 3
    {2, 7, 4, 5},      // student 4
    {1, 6, 2, 10},     // student 5
    {8, 9, 1, 3}       // student 6
};

この情報を [nxn] 行列として効率的に表現するにはどうすればよいでしょうか。ここで、n は試験の数 (この場合は 10) で、M[i][j]は試験 i と試験 j を受ける学生の数に等しくなります。

使用できるデータ構造はありますか、それとも各試験を他の試験と比較してインクリメント カウンターを使用する必要がありますか? 考えてみれば、現実の学生数や試験の数に対して効率的ではないと思うからです。

論文や参考文献を紹介していただければ、大変助かります。

ありがとう

4

1 に答える 1

1

おそらく回避しようとしているブルートフォースアプローチは次のとおりです。

class testMatrixSO{
    public static void main(String[] args){

        int[][] students_exams = 
        {
        {3, 1, 2, 5, 8},   // student 1
        {10, 4, 5, 7},     // student 2
        {1, 2, 3, 6},      // student 3
        {2, 7, 4, 5},      // student 4
        {1, 6, 2, 10},     // student 5
        {8, 9, 1, 3}       // student 6
        };

        int[][] finalMatrix = new int[10][10];
        //here is the part that creates your matrix
        for(int i=0; i<students_exams.length; i++)
            for(int j=0; j<students_exams[i].length; j++)
                for(int k=0; k<students_exams[i].length; k++)
                    if(j != k) finalMatrix[students_exams[i][j]-1][students_exams[i][k]-1]++;



        //print results
        for(int i=0; i < finalMatrix.length; i++){
            for(int j=0; j < finalMatrix[i].length; j++)
                System.out.print(finalMatrix[i][j] + " ");
            System.out.println();
        }

    }
}

良い点として、各生徒が 6 回以下の試験を受けると仮定すると、行列を更新するループの実行回数は (生徒数)*(6*6) 未満であると自信を持って言えます。つまり、アルゴリズムは線形次数 O(n) です。

于 2013-10-30T19:06:36.050 に答える