订购组合以获得最大效率

Question

所以最近我遇到了一个问题,我一直在考虑,但仍然无法解决; 我想知道这里是否有人可以通过向我提供这个问题的伪代码(或者至少是伪代码的粗略轮廓)来指出我正确的方向.PS如果有所作为,我将用PHP构建......

眼镜

有大约50个人(对于这个例子我只称他们为a,b,c ......)并且用户将他们分成三个一组(组中的人可能重叠),最后那里将是50-100组(即{a,b,c}; {d,e,f}; {a,d,f}; {b,c,l} ......).*

到目前为止它很容易,它是一个构建html表单并将其处理成多维数组的问题

---

白天有大约15个时段(例如上午9点,上午9点20分,上午9点40分......).这些团体中的每一个都需要在白天见面一次.并且在一个时间段内,该人不能被双重预订(即'a'在上午9:40不能在两个不同的组中).

它在这里变得棘手,但并非不可能,我最好的猜测是如何做到这一点就是强行它(挑选出没有重叠的组(例如{a,b,c}; {l,f,g}} ; {q,n,d} ...)然后将每个放入一个时隙

---

最后,我输出的时间表需要"优化",我的意思是'a'应该在会议之间的时间最短(所以如果他的第一次会议是在上午9:20,他的第二次会议不应该是2: 00PM).

这是我迷失的地方,我唯一的猜测是建立许多很多时间表,然后根据一个人从一次会议到下次会议的平均等待时间对他们进行排名

---

然而,我的"解决方案"(我对此称之为犹豫不决)需要太多的蛮力,并且需要很长时间来创建.是否有更简单,更优雅的解决方案？

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 多人、约 10 次会议的 EXCEL。我不明白为什么这在 SQL + PHP 中不起作用。只是计算实际上可能需要花费相当长的时间。