php - SQL高效的计划生成算法

Question

这个主意

想象一下，教育中心有分公司。 该教育中心的类(class)对所有分支机构都是通用的。

分支

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;

由管理员生成的每个类(class)的每个分支的房间。例如，管理员输入数学类(class)的房间数。系统生成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;

管理员首次注册学生时，他会选择该学生要参加的所有类(class)。例如，如果选择的5门类(class) StudentCourseAssoc将为该学生填充5行。在测试了学生的每门类(class)的基本知识水平之后，管理员将学生评估为特定类(class)的“聪明”(+1)或“愚蠢”(-1)。因此， knowledge_level是学生与类(class)之间的连接的值。

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名学生。

类(class)间有限。因此，每天odt_rli中每个房间只能容纳5个小组

每个学生都必须在1天之内参加每门(由他自己选择)的类(class)

搜索满足以上条件的 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;

And here is fiddle to play with.

我做了什么

我正在尝试在知识评估过程中将学生放置在 group(现有的或创建新的)上。就像，如果学生选择数学作为类(class)之一，那么当管理员评估他的数学知识并给予肯定评价时，程序就会开始为该学生选择合适的组:

功能标记学生的知识水平

检查学生的可用时间(例如，已经花了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的答案，我创建了“虚拟”小时表和以下 View ，以获取每个学生的所有可能的时空类(class)组合列表。
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`)
            )
        )
    )

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

将学生分组

将组放置在房间中

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

有什么建议？

Answer 1

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

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

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

因此，student/math-1问题:

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

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

本质上(至少我)不关心某个房间是否可用，只要有1个可用房间即可:
因此，在这种情况下，每个索引的AND可能是可用性的答案(请记住:0可用):

session 室1:[1 0 0]
session 室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中:数据模型(部分:类(class)匹配缺失):
桌房:

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％的解决方案，因此在使用它之前需要先做一些工作......