订购组合以获得最大功效

Question

所以最近给我出了一个问题，我一直在思考，但还是无法解决；我想知道这里是否有人可以通过为我提供这个问题的伪代码（或至少是伪代码的粗略轮廓）来为我指出正确的方向。 PS 如果这有影响的话，我将用 PHP 构建...

规格

有大约 50 个人（在这个例子中，我将他们称为 a、b、c...），用户将把他们分组为三人一组（组内人员可能重叠），最终会有 50-100 组（即 {a,b,c}; {d,e,f}; {a,d,f}; { b,c,l}...）。 *

到目前为止，这很容易，只需构建一个 html 表单并将其处理为多维数组即可

---

一天中大约有 15 个时间段（例如 9:00AM、9:20AM、9 :40AM...)。每个小组都需要在白天开会一次。并且在一个时间段内，该人不能被重复预订（即“a”不能在上午 9:40 分在 2 个不同的组中）。

这里很棘手，但并非不可能，我对如何做到这一点的最佳猜测是暴力破解（挑选出没有重叠的组集（例如 {a,b,c}; {l,f ,g}; {q,n,d}...) 然后将每个放入一个时间段

---

最后，我输出的时间表需要“优化”，我的意思是“a”会议之间的时间应该最短（所以如果他的第一次会议是上午 9:20，他的第二次会议不应该在下午 2:00

这是我迷失的地方，我唯一的猜测是制定很多很多时间表，然后根据它们进行排名 ）。一个人从一次会议到下一次会议的平均等待时间

---

但是，我的“解决方案”（我犹豫如何称呼它们）需要太多的蛮力，并且需要很长时间才能创建。解决方案？

Answer 1

这些是根据您的场景进行修改的表格。

+----User_Details------+  //You may or may not need this
| UID | Particulars... |
+----------------------+

+----User_Timeslots---------+  //Time slots per collumn
| UID | SlotNumber(bool)... |  //true/false if the user is avaliable
+---------------------------+  //SlotNumber is replaced by s1, s2, etc

+----User_Arrangements--------+  //Time slots per collumn
| UID | SlotNumber(string)... |  //Group session string
+-----------------------------+

注意：排列表中的字符串采用以下格式：JSON

'[12,15,32]' //从最小到最大！

那么安排表中发生的情况是，脚本 [或 EXCEL 列公式] 将遍历每个会话的每个槽，并随机创建一个可能的会话。检查所有先前的会话是否存在冲突。

/**
* Randomise a session, in which data is not yet set
**/
function randomizeSession( sesionID ) {
    for( var id = [lowest UID], id < [highest UID], id++ ) {
        if( id exists ) {
            randomizeSingleSession( id, sessionID );
        } //else skips
    }
}

/**
* Randomizes a single user in a session, without conflicts in previous sessions
**/
function randomizeSingleSession( id, sessionID ) {

    convert sessionID to its collumns name =)
    get the collumns name of all ther previous session

    if( there is data, false, or JSON ) {
        Does nothing (Already has data)
    }

    if( ID is avaliable in time slot table (for this session) ) {
        Get all IDs who are avaliable, and contains no data this session
        Get all the UID previous session
        while( first time || not yet resolved ) {
            Randomly chose 2
            if( there was conflict in UID previous session ) {
                try again (while) : not yet resolved
            } else {
                resolved
            }
        }

        Registers all 3 users as a group in the session

    } else {
        Set session result to false (no attendance)
    }
}

您将意识到分组分配的主要部分是通过随机化。然而，随着会话量的增加。将会有越来越多的数据来检查冲突。导致性能大大降低。无论存在多么大，大得离谱，以至于几乎完美的排列/组合公式。

编辑：

此设置还有助于确保只要用户有空，他们就会在一个组中。尽管您可能有少量用户，但没有用户组（数量很少）。这些通常可以通过重新计算来解决（对于较小的会话数）。或者只是手动将它们分组在一起，即使是重复的。 （到处都有一些并没有什么坏处）。或者，在您的情况下，与其余部分一起，加入几个 3 人组，形成 4 人组。 =)

如果这可以用于大约 100 多人的 EXCEL 和大约 10 个会话。我不明白为什么这在 SQL + PHP 中不起作用。只是计算实际上可能需要花费相当长的时间。

Answer 2

好吧，对于那些刚刚加入这篇文章的人来说，请在考虑这个答案的内容之前先阅读对该问题的所有评论，因为这很可能会超出你的头脑。

这是一些 PHP 风格的伪代码：

/* Array with profs (this is one dimensional here for the show, but I assume
it will be multi-dimensional, filled with availability and what not;
For the sake of this example, let me say that the multi-dimensional array
contains the following keys: [id]{[avail_from],[avail_to],[last_ses],[name]}*/
$profs = array_fill(0, $prof_num, "assoc_ids");

// Array with time slots, let's say UNIX stamps of begin time
$times = array_fill(0, $slot_num, "time");

// First, we need to loop through all the time slots
foreach ($times as $slot) {

    // See when session ends
    $slot_end = $slot + $session_time;

    // Now, run through the profs to see who's available
    $avail_profs = array(); // Empty
    foreach ($profs as $prof_id => $data) {

        if (($data['avail_from'] >= $slot) && ($data['avail_to'] >= $slot_end)) {

            $avail_prof[$prof_id] = $data['last_ses'];

        }

    }

    /* Reverse sort the array so that the highest numbers (profs who have been
    waiting the longest) will be up top */
    arsort($avail_profs);
    $profs_session = array_slice($avail_profs, 0, 3);
    $profs_session_names = array(); // Empty

    // Reset the last_ses counters on those profs
    foreach ($profs_session as $prof_id => $last_ses) {


        $profs[$prof_id]['last_ses'] = 0;
        $profs_session_names[0] = $profs[$prof_id]['name'];

    }

    // Now, loop through all profs to add one to their waiting time
    foreach ($profs as $prof_id = > $data) {

       $profs[$prof_id]['last_ses']++;

    }

    print(sprintf('The %s session will be held by: %s, $s, and %s<br />', $slot,
                   $profs_session_names[0], $profs_session_names[1],
                   $profs_session_names[2]);

    unset ($profs_session, $profs_session_names, $avail_prof);

}

应该打印如下内容：

The 9:40am session will be held by: C. Hicks, A. Hole, and B.E.N. Dover

Answer 3

我看到一个对象模型，其中包含：

• 小组成员：小组成员（汤姆、迪克、哈利等）的固定存储库
• 小组：由 X 个小组成员组成（在您的情况下 X=3）
• 时隙：您的时隙的固定存储库。假设固定持续时间并且仅发生在一天，那么您所需要的只是跟踪开始时间。
• 会议：由小组组成 时间段
• 安排：由许多会议组成

现在，正如您所观察到的，优化是关键。对我来说，问题是：“根据什么标准进行优化？”。对汤姆来说最理想的可能意味着他所属的小组的布局没有很大的差距。但哈利的面板可能是全面的。因此，也许对于给定的 Schedule，我们计算类似 totalMemberDeadTime （= Schedule 中所有死区时间成员间隙的总和）。最优调度是相对于该总和而言最小的调度。

如果我们有兴趣在所有调度的范围中计算技术上最优的调度，我真的没有看到除了暴力之外的替代方案。

也许时间表的范围并不需要像最初看起来那么大。听起来好像首先组成了小组，然后问题是将它们分配给由它们构成时间表的会议。因此，我们消除了面板组成的可变性；全部的可变性都在会议和日程安排中。尽管如此，确实似乎存在很多变化。

但也许对于所有可能的时间表而言，最佳的情况超出了我们真正需要的范围。

如果没有小组成员的总停滞时间超过 X，我们是否可以将时间表定义为可接受的？或者如果失败了，如果不超过X个小组成员的停滞时间超过X个（不能满足所有人，但将麻烦减少到最低限度）？然后，用户可以首先为包含更“重要”的小组成员的小组分配会议，而不太重要的人只需接受他们所得到的。那么我们所要做的就是制定一个可接受的时间表，

比较任何两个时间表是否足以满足您的目的？与一个界面（我看到的是一个拖放界面，但这显然超出了重点）相结合，该界面允许用户制定一个时间表，将其克隆到第二个时间表中，并调整第二个时间表，以减少总计直到我们找到一个可以接受的死区时间。

无论如何，这不是一个完整的答案。只是大声思考。希望有帮助。