gpt4 book ai didi

php - 在 student_ids 到 class_times 的映射中找到常见负空间的最佳方法

转载 作者:可可西里 更新时间:2023-11-01 12:59:08 25 4
gpt4 key购买 nike

我正在用 PHP 编写一个调度应用程序的概念证明。我有一个学生时间表的二维数组,格式为 (str) class_time => (array) student_ids,打印输出:http://d.pr/i/UKAy .

在处理的这一点上,我需要确定哪个 class_time 最适合举办一门新类(class),比如有 10 名学生提出要求。为此,我想确定有多少学生有 n class_times 可用,理想情况下存储为 class_time => student_ids => n_available_class_times

那么,构建/搜索这些数据的理想方式是什么?最终结果是所有 class_times 的列表,以及学生在安排每门新类(class)时可以使用给定类(class)的想法。这使我可以按 available_class_times 排序,以找到日程安排最受限制的学生,以及考虑到 future 安排他们的难度,他们需要优先安排给定类(class),给定一些现有/潜在的限制条件。

最佳答案

以下内容会有所帮助。每个数组 student_ids 都需要排序。您可以使用快速排序在 nlog(n) 时间内完成此操作。然后你就得开始计划了。我认为像 AB 剪枝这样的东西在这里会起作用,因为你在最后有一些最佳状态,并且一路上的决定会影响你的最佳状态。 (开头的排序位只是为了让它更快)

这里有一些关于 AB 修剪的东西:

首先,有一个称为 min-max 的决策算法,它指出“游戏”中的所有决策都会导致最终状态,该状态要么无限好,要么无限坏,即赢或输。因此,您构建这棵树,每个节点代表一个“游戏状态”,在您的情况下是学生被安排的状态。然后你搜索树。横穿它以获得最佳移动状态。在您的情况下,最佳调度。在每个节点,您决定它是否是结束状态并将其称为无限或负无限,或者您分支到其他节点。请注意,这不是二叉树。决策树节点有 n 个分支,其中 n 是您可以在那里做出的决策数。这对于您所做的事情来说并不太好,但需要解释才能理解 AB 剪枝。

现在假设您可以衡量一个游戏状态的好坏,而不是仅仅询问一个节点是赢还是输。在您的情况下,基于可以最佳安排的学生人数。当你遍历巨大的决策树时,你可以切掉很大的部分,因为你知道它们会导致糟糕的“游戏状态”,即你想要轻松放置和不容易放置的学生的状态。您执行此操作的方法是考虑导致游戏状态 B 的节点,您知道这些节点比 A(您之前评估的节点)更差。这很好,因为搜索这棵树是一项严肃的计算任务。这允许您通过忽略大量部分(这真的是巨大的计算增益)来进行更深入的评估。这将为您提供最佳类(class)表状态的答案。祝你好运。

// HERE IS SOME CODE FROM THE INTERNET
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return the heuristic value of node
if Player = MaxPlayer
for each child of node
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Beta cut-off *)
return α
else
for each child of node
β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break (* Alpha cut-off *)
return β
(* Initial call *)
alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

这是关于这个主题的链接: http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning

关于php - 在 student_ids 到 class_times 的映射中找到常见负空间的最佳方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15987480/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com