我正在尝试用 JavaScript 为一所高中开发一个学校时间表生成器，其中包含各种科目、教师和课程。目标是创建一个平衡的时间表，最大限度地减少冲突，同时考虑教师的偏好和可用性。
具体挑战：
我正在努力研究主题分布的算法。理想情况下，我想要一个可以处理这些约束的有效算法：
整个星期各班级的科目分布均衡。
尊重老师的喜好和无法上课的日子。
以有组织且公平的方式向所有人分发教师的讲座。
附加信息：
我熟悉 JavaScript 中基本的面向对象编程概念，并查看了一些有关调度算法的在线资源。然而，它们对于我的需求来说似乎太复杂了。
有没有适合这种场景的有效算法，或者您能否建议一种在考虑上述约束的同时有效分配主题的方法？
示例数据：
const teachers = [
{
name: "Math-Teacher",
id: "T1",
workDays: 6,
subjects: ["M1", "M2", "M3"],
},
{
name: "Quilting-Teacher",
id: "T2",
workDays: 2,
subjects: ["Q1", "Q2", "Q3"],
},
{
name: "Italian-Teacher",
id: "T3",
workDays: 6,
subjects: ["I1", "I2", "I3"],
},
{
name: "Biology-Teacher",
id: "T4",
workDays: 4,
subjects: ["B1", "B2", "B3"],
},
{
name: "history-Teacher",
id: "T5",
workDays: 2,
subjects: ["H1"],
},
{
name: "Phasics-Teacher",
id: "T6",
workDays: 5,
subjects: ["P1", "P2", "P3"],
},
{
name: "Italian-Teacher",
id: "T7",
workDays: 3,
subjects: ["I1", "I2", "I3"],
},
{
name: "Chemistry-Teacher",
id: "T8",
workDays: 3,
subjects: ["C1", "C2", "C3"],
},
{
name: "English-Teacher",
id: "T9",
workDays: 4,
subjects: ["M1"],
},
{
name: "Arabic-Teacher",
id: "T10",
workDays: 6,
subjects: ["A1", "A2"],
},
];
const subjects = [
//1-sec subjects
{
name: "Math",
class: "1-sec",
id: "M1",
weeklyLectures: 7,
},
{
name: "Biology",
class: "1-sec",
id: "B1",
weeklyLectures: 4,
},
{
name: " Quilting",
class: "1-sec",
id: "Q1",
weeklyLectures: 3,
},
{
name: "Isramic Culture",
class: "1-sec",
id: "I1",
weeklyLectures: 3,
},
{
name: "Phasics",
class: "1-sec",
id: "P1",
weeklyLectures: 5,
},
{
name: "History",
class: "1-sec",
id: "H1",
weeklyLectures: 3,
},
{
name: "English",
class: "1-sec",
id: "E1",
weeklyLectures: 5,
},
{
name: "Arabic",
class: "1-sec",
id: "A1",
weeklyLectures: 6,
},
{
name: "Chemistry",
class: "1-sec",
id: "C1",
weeklyLectures: 3,
},
//2-sec subjects
{
name: "Math",
class: "2-sec",
id: "M2",
weeklyLectures: 7,
},
{
name: "Biology",
class: "2-sec",
id: "B2",
weeklyLectures: 4,
},
{
name: " Quilting",
class: "2-sec",
id: "Q2",
weeklyLectures: 3,
},
{
name: "Isramic Culture",
class: "2-sec",
id: "I2",
weeklyLectures: 3,
},
{
name: "Phasics",
class: "2-sec",
id: "P2",
weeklyLectures: 5,
},
{
name: "English",
class: "2-sec",
id: "E2",
weeklyLectures: 5,
},
{
name: "Arabic",
class: "2-sec",
id: "A2",
weeklyLectures: 6,
},
{
name: "Chemistry",
class: "2-sec",
id: "C2",
weeklyLectures: 3,
},
//3-sec subjects
{
name: "Math",
class: "3-sec",
id: "M3",
weeklyLectures: 7,
},
{
name: "Biology",
class: "3-sec",
id: "B3",
weeklyLectures: 4,
},
{
name: " Quilting",
class: "3-sec",
id: "Q3",
weeklyLectures: 3,
},
{
name: "Isramic Culture",
class: "3-sec",
id: "I3",
weeklyLectures: 3,
},
{
name: "Phasics",
class: "3-sec",
id: "P3",
weeklyLectures: 5,
},
{
name: "English",
class: "3-sec",
id: "E3",
weeklyLectures: 5,
},
{
name: "Arabic",
class: "3-sec",
id: "A3",
weeklyLectures: 6,
},
{
name: "Chemistry",
class: "3-sec",
id: "C3",
weeklyLectures: 3,
},
];
const classes = [
{
name: "1-secondary",
id: "1-sec",
DailyLectures: 7,
subjects: ["M1", "Q1", "I1", "A1", "E1", "H1", "C1", "B1", "P1"],
},
{
name: "2-secondary",
id: "2-sec",
DailyLectures: 7,
subjects: ["M2", "Q2", "I2", "A2", "E2", "C2", "B2", "P2"],
},
{
name: "3-secondary",
id: "3-sec",
DailyLectures: 7,
subjects: ["M3", "Q3", "I3", "A3", "E3", "C3", "B3", "P3"],
},
];
const daysOfWeek = ["Sat", "Sun", "Mon", "Tue", "Wed", "Thr"];
预期输出:
我希望输出的是每堂课每周的时间表，老师的讲座均匀分布在工作日。
例如（像这样但以有效的方式）：
1-sec: {
Sat: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: ' Quilting', class: '1-sec', id: 'Q1', weeklyLectures: 3 },
{ name: ' Quilting', class: '1-sec', id: 'Q1', weeklyLectures: 3 },
{
name: 'Isramic Culture',
class: '1-sec',
id: 'I1',
weeklyLectures: 3
},
{ name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
{ name: 'History', class: '1-sec', id: 'H1', weeklyLectures: 3 },
{ name: 'History', class: '1-sec', id: 'H1', weeklyLectures: 3 }
],
Sun: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: ' Quilting', class: '1-sec', id: 'Q1', weeklyLectures: 3 },
{
name: 'Isramic Culture',
class: '1-sec',
id: 'I1',
weeklyLectures: 3
},
{ name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
{ name: 'History', class: '1-sec', id: 'H1', weeklyLectures: 3 },
{ name: 'Phasics', class: '1-sec', id: 'P1', weeklyLectures: 5 },
{ name: 'Chemistry', class: '1-sec', id: 'C1', weeklyLectures: 3 }
],
Mon: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{
name: 'Isramic Culture',
class: '1-sec',
id: 'I1',
weeklyLectures: 3
},
{ name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
{ name: 'Phasics', class: '1-sec', id: 'P1', weeklyLectures: 5 },
{ name: 'Chemistry', class: '1-sec', id: 'C1', weeklyLectures: 3 },
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 }
],
Tue: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Biology', class: '1-sec', id: 'B1', weeklyLectures: 4 },
{ name: 'Phasics', class: '1-sec', id: 'P1', weeklyLectures: 5 },
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Arabic', class: '1-sec', id: 'A1', weeklyLectures: 6 }
],
Wed: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Phasics', class: '1-sec', id: 'P1', weeklyLectures: 5 },
{ name: 'Arabic', class: '1-sec', id: 'A1', weeklyLectures: 6 }
],
Thr: [
{ name: 'Math', class: '1-sec', id: 'M1', weeklyLectures: 7 },
{ name: 'Arabic', class: '1-sec', id: 'A1', weeklyLectures: 6 }
]
}
这个问题通常被称为“为任务分配代理”。有几种算法可以解决这个问题。我使用 Ford-Fulkerson 最大流算法（theory.stanford.edu/~tim/w16/l/l1.pdf）
一如既往，技巧是使算法适应您的特定约束，以便最大流算法在不违反任何约束的情况下运行。
我不明白你的一些限制（特别是“工作日”，请参阅我对你的问题的评论以获取所需的澄清）。所以我不能应用你所有的限制。但是，我认为您可能会发现查看一些代码（C++，抱歉）很有用，这些代码实现了应用于问题的简化版本的最大流量分配。此代码使用 PathFinder 图论库提供的 Ford-Fulkerson 实现。 （https://github.com/JamesBremner/PathFinder）
#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include "GraphTheory.h"
class cAgent
{
public:
std::string myID;
std::vector<std::string> myTasks;
bool cando( const std::string& task )
{
return std::find(
myTasks.begin(),myTasks.end(),
task )
!= myTasks.end();
}
};
std::set<std::string> theTasks;
std::vector<cAgent> theAgents;
void readfile()
{
std::ifstream ifs("../dat/data1.txt");
if (!ifs.is_open())
throw std::runtime_error(
"Cannot read input");
std::string line;
while (getline(ifs, line))
{
// std::cout << line << "\n";
if (line.find("id:") != -1)
{
int p = line.find("\"");
int q = line.find("\"", p + 1);
line = line.substr(p + 1, q - p - 1);
if (line[0] == 'T')
{
cAgent A;
A.myID = line;
theAgents.push_back(A);
}
}
else if (line.find("subjects:") != -1)
{
int p = line.find("\"", p + 1);
while (p != -1)
{
int q = line.find("\"", p + 1);
auto task = line.substr(p + 1, q - p - 1);
theTasks.insert(task);
theAgents.back().myTasks.push_back(task);
p = line.find("\"", q + 1);
}
}
else if (line.find("const subjects") != -1)
break;
}
std::cout << "Teachers:\n ";
for (auto &a : theAgents)
{
std::cout << a.myID << " can teach ";
for (auto &t : a.myTasks)
std::cout << t << " ";
std::cout << "\n";
}
}
void allocateMaxFlow()
{
raven::graph::cGraph g;
g.directed();
// loop over the tasks in timeslot
for (auto & task : theTasks)
{
// loop over agents that can do task
for (cAgent &a : theAgents)
{
if( ! a.cando( task ))
continue;
// add link from agent to task agent is able to do
g.add(
a.myID,
task );
}
}
// apply pathfinder maximum flow allocation algorithm
raven::graph::sGraphData gd;
gd.g = g;
auto sg = alloc(gd);
std::cout << "\nAssignments:\n";
for (std::pair<int, int> p : sg.edgeList())
{
std::cout << "teacher " << sg.userName(p.first )
<< " assigned to " << sg.userName (p.second)
<< "\n";
}
}
main()
{
readfile();
allocateMaxFlow();
return 0;
}
其输出是
Teachers:
T1 can teach M1 M2 M3
T2 can teach Q1 Q2 Q3
T3 can teach I1 I2 I3
T4 can teach B1 B2 B3
T5 can teach H1
T6 can teach P1 P2 P3
T7 can teach I1 I2 I3
T8 can teach C1 C2 C3
T9 can teach M1
T10 can teach A1 A2
Assignments:
teacher T10 assigned to A1
teacher T4 assigned to B1
teacher T8 assigned to C1
teacher T5 assigned to H1
teacher T3 assigned to I1
teacher T7 assigned to I2
teacher T9 assigned to M1
teacher T1 assigned to M2
teacher T6 assigned to P1
teacher T2 assigned to Q1