SQL高效的计划生成算法

支彭亮

2023-03-14

问题内容：

想象一下设有 分支机构的 教育中心。该教育中心的课程对所有分支机构都是通用的。

分行

CREATE TABLE `Branch` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8;


CREATE TABLE `Course` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `active` tinyint(1) DEFAULT '1',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

*管理员生成的每个课程的每个分支中的 *房间。例如，管理员输入数学课程的房间数。系统生成3个房间。换句话说，它们受到计数的限制。

CREATE TABLE `Room` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `branch_id` int(10) unsigned DEFAULT NULL,
  `course_id` int(10) unsigned DEFAULT NULL,
  `occupied_hours` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

每个房间每天有5个可用的教学时间。换句话说，Math-1每个教学小时（共5个）将有1个不同的学生组。

学生 -也按分支分组。每个学生都喜欢按周计划（week_day_mode）上中学。

一周的1、3、5天
一周的2、4、6天

class 该字段是学校（主要学校）的年级，

CREATE TABLE `Student` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `fullname` varchar(255) NOT NULL,
  `class` tinyint(2) DEFAULT NULL,
  `branchID` int(10) unsigned DEFAULT NULL,
  `week_day_mode` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `branchID` (`branchID`)
) ENGINE=InnoDB AUTO_INCREMENT=246 DEFAULT CHARSET=utf8;

管理员首次注册学生时，他会选择该学生要参加的所有课程。例如，如果选择的5门课程StudentCourseAssoc将为该学生填充5行。在测试了学生的每门课程的基本知识水平之后，管理员将学生评估为特定课程的“聪明”（+1）或“愚蠢”（-1）。所以knowledge_level对于学生课程连接的价值。

CREATE TABLE `StudentCourseAssoc` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `studentID` int(10) unsigned DEFAULT NULL,
  `courseID` int(10) unsigned DEFAULT NULL,
  `knowledge_level` tinyint(1) DEFAULT NULL,
  `group_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1144 DEFAULT CHARSET=utf8;

该应用程序必须：

在以下条件下自动分组（可以创建新分组或将学生添加到现有分组）每个分支的学生

聪明而又愚蠢的学生必须分在不同的小组中
小组可能由一些年级组合组成。因此，可以将9年级和10年级混合使用。和11级一起毕业（12级意味着sql毕业）。但不是10日至11日。（将有2种模式：9-10、11-12）
小组最多可容纳8名学生。
教室有限。因此，每个房间在一天中只能容纳5个团体
每个学生必须在1天之内上完每门（由他本人选择）的课程

搜索group满足以上条件的内容后，如果找不到，则应用必须创建，然后将学生分配给group。然后：

CREATE TABLE `StudentGroupAssoc` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) unsigned DEFAULT NULL,
  `student_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

CREATE TABLE `Schedule` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `group_id` int(10) unsigned DEFAULT NULL,
  `week_day_mode` tinyint(1) DEFAULT NULL,
  `hour` tinyint(1) DEFAULT NULL,
  `room_id` int(4) unsigned DEFAULT NULL,
  `teacher_id` int(10) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `Unique Room for exact time` (`week_day_mode`,`hour`,`room_id`) USING BTREE,
  UNIQUE KEY `Unique Group for exact time` (`group_id`,`week_day_mode`) USING BTREE,
  KEY `Unique Teacher for exact time` (`week_day_mode`,`hour`,`teacher_id`),
  KEY `room_id` (`room_id`),
  KEY `teacher_id` (`teacher_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

和这里玩弄小提琴。

我做了什么

我正在尝试group在知识评估期间让学生参加（现有的或创建新的）学生。就像，如果学生选择数学作为课程之一，那么当管理员评估他的数学知识并给予肯定评价时，程序就会开始为该学生选择合适的组：

功能标记学生的知识水平
检查学生的可用时间（例如，已经采取了第1个小时，那么他有4个小时可用）
在搜索中添加全班学习条件（例如9-10年级或11-12年级）
检查时间表表中学生的每周计划中是否有可用时间的班组

如果没有人，则尝试创建。

所以PHP表示看起来像这样

        //sets knowledge level of student
        $studentCourse->knowledge_level = intval($_POST["mark"]);

        //check hours of student, and keep only available hours
        $availableHours = array_combine(range(1, 5), range(1, 5));

        //Unsets students unavailable hours from possible hours
        if ($student->GroupRels)
            foreach ($student->GroupRels as $groupRel)
                unset($availableHours[$groupRel->hour]);

        //Checks available groups based on class coverage
        if (in_array($student->class, ['11', 'G']))
            $classCoverage = "11-m";
        else if (in_array($student->class, ['9', '10']))
            $classCoverage = "9-10";

        $availableGroups = Group::find()
            ->with("schedule")
            ->where([
                    "Group.class_coverage" => $classCoverage,
                    "Group.knowledge_level" => $studentCourse->knowledge_level,
                    "Group.participiant_count<8",
                    "Schedule.hour" => $availableHours,
                    'Schedule.week_day_mode' => $student->week_day_mode
                ]
            )->all();


        if (count($availableGroups) > 0) {
             //Selecting one of groups
             //adding row to StudentGroupAssoc
            //adding row to Schedule
        } else {
            $group = new Group();
            $group->branch_id = $student->branchID;
            $group->class_coverage = $classCoverage;
            $group->course_id=$studentCourse->courseID;
            $group->knowledge_level=$studentCourse->knowledge_level;
            $group->save();
            ...
            //adding row to StudentGroupAssoc
            //adding row to Schedule


        }

问题是

从理论上讲，我的工作方式就像购买飞机票。是无错的，并且必须有效，但是效率不高且不是最佳的。必须以最有效的方式满足所有分组条件：最少的组数和满足有限的房间数策略。这种方法很快将组成大量的组，这些组将不适合可用的房间时间。

当我在评估过程中一小时一小时地学习学生时，越来越难获得真正有效的结果。由于房间有限，找不到学生的团体和无法创建新团体的机会越来越多地花费了数小时的学生。

您建议在每个房间中利用什么小时？

更新

基于@norbert_van_nobelen的答案，我创建了“虚拟”小时表和以下视图，以获取每个学生的所有可能的时空课程组合列表。

hours计划的实际小时数 hours_available是二进制开关。因此，在实际代码中，我们添加了一个where子句：WHERE
hours_available = 0以仅获取我们要针对其进行计划的小时数：

SELECT
    `s`.`id` AS `student_id`,

IF ((ifnull(`sch`.`hour`, 0) > 0), 1, 0) AS `hour_available`,
 `d`.`hours` AS `hours`,
 `sca`.`courseID` AS `courseID`,
 `sch`.`room_id` AS `room_id`,
 `sca`.`knowledge_level` AS `knowledge_level`,
 (
    CASE
    WHEN (
        (`s`.`class` = 9)
        OR (`s`.`class` = 10)
    ) THEN
        '9-10'
    WHEN (
        (`s`.`class` = 11)
        OR (`s`.`class` = 12)
    ) THEN
        '11-12'
    ELSE
        '??'
    END
) AS `class_variant`
FROM
    (
        (
            (
                (
                    `dummy_hours` `d`
                    JOIN `Student` `s`
                )
                LEFT JOIN `StudentCourseAssoc` `sca` ON ((`s`.`id` = `sca`.`studentID`))
            )
            LEFT JOIN `StudentGroupAssoc` `b` ON ((`s`.`id` = `b`.`student_id`))
        )
        LEFT JOIN `Schedule` `sch` ON (
            (
                (
                    `sch`.`group_id` = `b`.`group_id`
                )
                AND (`d`.`hours` = `sch`.`hour`)
            )
        )
    )

使用此视图可以全面了解当前情况。但是我仍然不知道算法

将学生分组
在房间里放置团体

以最有效，最优化的方式创建最少的组数。

有什么建议？

问题答案：

此答案仅是作为计划部分的解决方案方向，而不是100％好的解决方案：

您创建的内容需要循环才能满足所有条件。

为了更快地解决这种情况，实际上可以使用向量代替，其中向量中的所有位置都由0（可用）和1（采用）表示。

因此，student / math-1问题：

假设有2个房间和3个小时：那么每个房间的math-1向量为：

Room 1: [0 0 0]
Room 2: [0 0 0]

本质上（至少我不关心）只要有1个房间就可以使用某个房间：因此，在这种情况下，每个索引的AND可能是可用性的答案（请记住：0可用）：

会议室1：[1 0 0]会议室2：[0 0 0]房间结果：[1 0 0]和[0 0 0] = [0 0 0]

因此，AND可以判断第一个小时是否仍然可用。

如果现在将其与有可用时间的学生相结合（在此示例中也仅为3）：

学生A：[0 0 1]房间结果：[0 0 0]学生使用此操作的OR匹配房间：[0 0 1]或[0 0 0] = [0 0 1]

因此，学生A将与房间结果相匹配。

在SQL中：数据模型（部分：缺少匹配项）：表室：

CREATE TABLE room(
room_id INT,
space TINYINT DEFAULT 0,
hour INT DEFAULT 1
);

CREATE TABLE student(
student_id INT,
space TINYINT DEFAULT 0,
hour INT DEFAULT 1
)

所有数据已全部插入到表中：在这种情况下，有1个房间，3小时，3个位置可用。

INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,1);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,2);
INSERT INTO room VALUES (1,0,3);
INSERT INTO room VALUES (1,0,3);
INSERT INTO room VALUES (1,0,3);

学生有：

INSERT INTO student VALUES(1,0,1);   
INSERT INTO student VALUES(1,0,2);   
INSERT INTO student VALUES(1,1,3);

因此，该学生仅在前两个小时有空。

现在要从查询中获取结果：

SELECT room_id
FROM room a
INNER JOIN student b ON a.space=b.space AND a.hour=b.hour;

该结果仅需分成最多8个组，在该组中，这是SQL部分的结尾，并且是另一种编程语言的时间。

该模型可以添加日期，但是在仅使用小时和工作日（工作日可用性再次为0或1）时，其效果最佳。

正如我所说：这是一个概念/想法，而不是100％的解决方案，因此在使用它之前需要先做一些工作......

SQL高效的计划生成算法

和这里玩弄小提琴。

我做了什么

问题是

更新

相关阅读

相关文章

相关问答

相关工具

相关文档