7

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

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

那么，构建/搜索这些数据的理想方法是什么？最终结果是所有的列表，class_times以及在安排每门新课程时学生可以利用给定课程的想法。这使我能够通过排序available_class_times找到他们的日程安排最受限制的学生，以及考虑到未来安排他们的难度，考虑到一些当前/潜在的限制，他们需要优先安排到给定的班级.

4

1 回答 1

2

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

以下是关于 AB 修剪的一些内容：

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

现在假设不只是询问一个节点是赢还是输，您可以衡量它的游戏状态有多好。在您的情况下，基于可以优化安排的学生人数。当您遍历巨大的决策树时，您可以剪掉很大的部分，因为您知道它们会导致蹩脚的“游戏状态”，即您想要轻松放置学生而不容易放置的状态。您这样做的方法是考虑导致游戏状态 B 的节点，您知道该节点比 A 最差（您之前评估的节点）。这很好，因为搜索这棵树是一项严肃的计算任务。这使您可以通过忽略巨大的部分来进行更深入的评估（这是非常棒的巨大计算增益）。这可以让您获得最佳课程表状态的答案。祝你好运，伙计。

// 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

于 2013-04-20T17:48:08.590 回答