1

我目前正在为一所大学的考试时间表安排解决方案。我正在考虑使用遗传算法。

现在我从一个简单的例子开始，以便我了解正在发生的事情，因为我对这一切都不熟悉。在这个例子中，我有 10 个考试、6 个学生和 6 个可用的时间段。我代表一个染色体，这样我在一个位串中有 10 个位置，其值从 1-6 不等，代表时隙，例如：[3 1 4 1 3 5 5 6 4 2]暗示考试 1 发生在第三个时隙，考试 2 发生在第 1 次-插槽等...

现在，如果我有以下数组表示每个学生参加的考试：

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 回答