班级调度算法显示与标准的最佳匹配?

发布于 2024-12-08 19:35:17 字数 178 浏览 0 评论 0原文

我希望创建一个系统,您可以输入您想在大学学习的课程(3-7门课程),然后选择偏好(早上、白天、晚上、晚上/M、T、W、TR、F) 。

我需要一种方法,以便当程序查询数据库(MySQL)时,它会返回根据这些参数制定的最佳计划。我是用php写的。

有谁知道做到这一点的最佳方法?或者我可以理解的一些示例代码的链接?

I am looking to create a system where you can input the courses (3-7 courses) that you want to take at a college and then select preferences (Morning, Day, Evening, Night / M, T, W, TR, F).

I need a way so that when the program queries the database (MySQL) it returns the best possible schedule that was made according to those parameters. I am writing it in php.

Does any one know the best way to do this? Or a link to some sample code I could understand it from?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(3

七七 2024-12-15 19:35:17

它是 NP 完全的。

如果您想要简单快速的东西,请编写一个构造启发式,例如首次拟合递减。简而言之,它根据难度(学生人数等)对课程进行排序,并在最佳的剩余时间段和空间中一次分配一门课程。您可以在 PHP 中轻松完成此操作。

如果你想做得正确,就像 @malejpavouk 所说,请使用 CP 库。它将首先使用构造启发式,然后使用元启发式,例如禁忌搜索、模拟退火……这是一个用 Java 实现的开源课程安排。寻找一个好的 PHP CP 库。

It's NP-complete.

If you want something simple and fast, write a construction heuristic like First Fit Decreasing. Simply put, it orders the courses according to difficulty (student size, ...) and assign them one at a time at the best remaining timeslot and room. You could easily do this in PHP.

If you want to do it right, like @malejpavouk said, use a CP library. It will first use a construction heuristic and then does metaheuristics like tabu search, simulated annealing, ... Here's a open source course scheduling implementation in Java. Look for a good PHP CP library.

婴鹅 2024-12-15 19:35:17

你可能想尝试一些约束编程(CSP)库......在CSP中,你陈述问题(通常是NP Hard),库使用一些启发式方法(模拟退火、禁忌搜索)或带有一些技巧的详尽的DFS来解决它(弧一致性,搜索空间剃须)...它可以解决具有数千个变量的 NPC 问题...但是设置黑盒系统的“精细”参数有点棘手...

You might want to try some constraint programming (CSP) library.... In CSP you state the problem (usually NP Hard) and the library solves it using some heuristics (simulated annealing, taboo search) or an exhaustive DFS with some tricks (arc consistency ,search space shaving)... It can solve NPC problems with thousands of variables...but its somehow tricky to set the "fine" parameters of the black-box system...

看透却不说透 2024-12-15 19:35:17

这是一个很难的优化问题。
这是一个建议的启发式(随机跳跃)。

  1. 获取一组约束(偏好)。
  2. 还有一套课程。
  3. 使用 MySQL 查询获取所选课程的可能时间。
  4. 选择一组可行的课程。
  5. 根据约束条件对集合进行评分。
  6. 如果分数足够好,就停止。
  7. 否则,更改随机选择的一门课程的时间。
  8. 返回步骤 4。

This is a hard optimization problem.
Here's a proposed heuristic (with random jumps).

  1. Get a set of constraints (preferences).
  2. And a set of courses.
  3. Get possible times of the chosen courses using a MySQL query.
  4. Choose a feasible set of courses.
  5. Score the set according to the constraints.
  6. If the score is good enough, stop.
  7. Otherwise, change the hours of one course, chosen at random.
  8. return to step 4.
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文