我正在为PHP中的调度应用程序编写概念证明.我有一个学生时间表的2D数组,格式为(str) class_time => (array) student_ids:printd:http://d.pr/i/UKAy.
在处理的这一点上,我需要确定哪个class_time最适合主持一个新课程,并说有10个学生要求它.为此,我想确定有多少学生可以n class_times使用,理想情况下存储为class_time => student_ids => n_available_class_times.
那么,构建/搜索这些数据的理想方法是什么？最终结果是所有的列表class_times以及学生在安排每门新课程时可以利用给定班级的想法.这让我可以排序,available_class_times找出那些在他们的日程安排上受到最大限制的学生,并且考虑到一些现有的/潜在的约束条件,考虑到将来安排这些课程的难度,他们需要优先考虑某个班级的日程安排. .
以下内容会有所帮助。每个数组都student_ids需要排序。您可以使用快速排序在 nlog(n) 时间内完成此操作。然后你就必须开始计划。我认为像 AB 剪枝这样的东西在这里会起作用，因为你最终会得到一些最佳状态，并且一路上的决策会影响你的最佳状态。（一开始的排序只是为了加快速度）
以下是AB修剪的一些内容：
\n\n首先，有一种称为“最小-最大”的决策算法，它指出“游戏”中的所有决策都会导致最终状态，该状态要么无限好，要么无限坏，即获胜或失败。因此，您构建这棵树，每个节点代表一个“游戏状态”，在您的情况下是学生被安排的状态。然后你搜索树。遍历它以获得最佳移动状态。根据您的情况优化调度。在每个节点，您决定它是否是最终状态，并在无限或负无限处调用它，或者分支到其他节点。请注意，这不是二叉树。决策树节点有 n 个分支，其中 n 是您可以在其中做出的决策数。这对于你所做的事情来说并不算太好，但需要解释才能理解 AB 剪枝。
\n\n现在假设您不仅可以询问节点是赢还是输，还可以衡量它的游戏状态有多好。根据您的情况，根据可以最佳安排的学生人数。当你遍历巨大的决策树时，你可以剪掉巨大的部分，因为你知道它们会导致蹩脚的“游戏状态”，即你想要的学生容易放置和不容易放置的状态。这样做的方法是考虑导致游戏状态 B 的节点，您知道该状态比 A（您之前评估的节点）更差。这很好，因为搜索这棵树是一项严肃的计算任务。这允许您通过忽略巨大的部分来进行更深入的评估（这确实是巨大的计算增益）。这将为您提供最佳课程安排状态的答案。祝你好运，伙计。
\n\n// HERE IS SOME CODE FROM THE INTERNET\nfunction alphabeta(node, depth, \xce\xb1, \xce\xb2, Player) \nif depth = 0 or node is a terminal node\n return the heuristic value of node\nif Player = MaxPlayer\n for each child of node\n \xce\xb1 := max(\xce\xb1, alphabeta(child, depth-1, \xce\xb1, \xce\xb2, not(Player) )) \n if \xce\xb2 \xe2\x89\xa4 \xce\xb1\n break (* Beta cut-off *)\n return \xce\xb1\nelse\n for each child of node\n \xce\xb2 := min(\xce\xb2, alphabeta(child, depth-1, \xce\xb1, \xce\xb2, not(Player) )) \n if \xce\xb2 \xe2\x89\xa4 \xce\xb1\n break (* Alpha cut-off *)\n return \xce\xb2\n(* Initial call *)\nalphabeta(origin, depth, -infinity, +infinity, MaxPlayer)\n以下是有关该主题的链接：\n http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning
\n| 归档时间： |
|
| 查看次数： |
115 次 |
| 最近记录： |