事件条目调度算法PHP

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了事件条目调度算法PHP，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7502字，纯文字阅读大概需要11分钟。

内容图文

我们有一个入口门户系统,我们接受事件的条目.

例如,2017年冠军赛将于11月30日举行.

活动在不同的课程中获得约150个参赛作品初级班,高级班,专业班等

现在活动场地只有一定数量的基础可以举行比赛.例如地面1,地面2和地面3.它是一个独奏表演活动.

现在我们的系统需要生成一个计划,以便多次进入多个班级或同一班级的竞争者应该在他们的表现之间获得最大的中断.

我们输入的数据是在每个类下注册的.
每个地面的开始时间.例如,地面A将在上午8:00开始,地面2在8:00开始,地面3在9:00开始.
我们也知道哪个级别将在哪个级别举行.例如,Junior和Senior Class将在Ground 1举行,Pro Class将在Ground 2举行.

我们也知道演出时间.高级1级表演是5分钟.初级表演为7分钟,专业表演为9分钟.

现在我已经编写了以下代码来获得时间表,以便竞争对手在一个级别或多个级别中多次竞争可以在他们的表现之间获得最大的突破,但它仍然会使竞争对手的表现一个接一个.

让我知道我的错误是什么.

foreach ($totalPerformanceTimeSlot as $time => $performance) {
    # $totalPerformanceTimeSlot is array of timeslots starting from 8:00 am

    foreach ($performance as $classId) {
        #there could be 2 performance at the same time in different arena for different class.
        $totalPerformanceLeftThisClass = count($this->lassRegistrationLinks[$classId]); //Get the total performance for this class from array;

        # $accountRidesLeftArray has value of how many times each account is performing in this class
        arsort($accountRidesLeftArray);
        # for each person,  estimate what their start time threshold should be based on how many times they're performing
        $accountPerformanceTimeThreshold = array();

        foreach ($accountPerformanceLeftArray as $accountId => $accountPerformancesLeft) {

            $tempPerformanceThreshold = 20 * 60;
            # reduce this person's performance threshold by a performance at a time until the minimum performance threshold has been met
            while ((($totalPerformanceLeftThisClass * $this->classes[$classId]['performanceTime']) / $accountPerformanceLeft < $tempPerformanceThreshold) && ($tempPerformanceThreshold > $this->minRideThreshold))
                $tempPerformanceThreshold -= $this->classes[$classId]['performanceTime'];

            $accountPerformanceTimeThreshold[$accountId] = $tempPerformanceThreshold;
        }

        $performanceLeft = $totalPerformanceLeftThisClass - $count;

        # given the number of performance left in the class,
        # calculate how important it is per account that they get placed in the next slot
        $accountToPerformNextImportanceArray = array();
        $timeLeft = $performanceLeft * $this->classes[$classId]['performanceTime'];

        foreach ($accountPerformanceLeftArray as $accountId => $accountPerformancesLeft) {

            # work out the maximum number that can be used as entropy
            $entropyMax = (20 * 60 / ($timeLeft / 1)) * 0.5;
            $entropy = ((mt_rand (0, $entropyMax * 1000)) / 1000);

            # the absolute minimum amount of time required for this user to perform
            $minTimeRequiredForComfortableSpacing = ($accountRidesLeft - 1) * 20* 60;
            # add a bit of time around the absolute minimum amount of time required for this person to perform so that it doesn't instantly snap in when this person suddenly has the minimum amount of time left to perform
            $generalTimeRequiredForComfortableSpacing = $minTimeRequiredForComfortableSpacing * 1.7;

            $nearestPerformancePrior = $this->nearest_performance_prior($classDetails['date'], $currentTime, $accountId);
            $nearestRideAfter = $this->nearest_performance_after($classDetails['date'], $currentTime, $accountId);

           # work out how important it is for this rider to ride next based on how many rides they have left
           $importanceRating = 20 * 60 / ($timeLeft / $accountPerformanceLeft);

           # if there's more than enough time left then don't worry about giving this person any importance rating,  ie. it's not really important that they perform straight away
           if ($timeLeft > $generalTimeRequiredForComfortableSpacing)
                $importanceRating = 0;

           # add a little bit of random entropy to their importance rating
           $importanceRating += $entropy;

           # if this account has performed too recently to place them here in this slot,  then make them very undesirable for this slot
           if ((!is_null($nearestPerformancePrior)) && ($nearestPerformancePrior > $currentTime - $accountPerformanceTimeThreshold[$accountId]))
               $importanceRating = -1;

          # work out if this account will perform too soon afterwards to place them here in this slot,  then make them very undesirable for this slot
          if ((!is_null($nearestRideAfter)) && ($nearestRideAfter < $currentTime + $accountRideTimeThreshold[$accountId]))
               $importanceRating = -1;

           $accountToPerformNextImportanceArray[$accountId] = $importanceRating;

       }

       arsort($accountToPerformNextImportanceArray);
       //Then I take the first one from this array and allocate the time for that user.
       $this->set_performance_time($classDetails['date'], $accountId, $currentTime);
       $currentTime += $this->classes[$classId]['performanceTime'];
    }
}

以下是对变量的一些解释

$accountPerformancessLeft is total number of performance for each user.
For e.g. if user has entered into 2 classes that means $accountPerformancessLeft is 6 for that user.
threshold is something like break.
Rider and account is conceptually the same.

我知道很难在没有实际数据的情况下考虑输出,但任何帮助都会受到赞赏.

谢谢

解决方法:

好吧,首先让我们看看我们有什么并简化问题：

>有不同的比赛(赛事),但由于他们彼此独立,我们只能考虑一个
>我们有不同的C级(高级,初级,……)
>我们有不同的理由,每个理由都可能包含一些C类.
>有些人(竞争对手)让P说谁登记到C级.
>人员需要有最大可能的休息时间.

所以把它们放在一起的问题是：
有些理由G = {g1,g2,…,gm},它们每个都包含一些人P = {p1,p2,…,pn}.我们希望在所有比赛中最大化每个人的休息时间.

琐碎的案例：

首先,让我们假设只有一个地面g1,以及一群人P = {p1,p2,…,pn}想要在这个基础上竞争.让我们定义一个布尔方法isItPossible(breaktime),显示是否可以安排每个人至少休息休息时间的比赛.我们可以简单地证明这种方法是单调的,即如果存在可能的休息时间(休息时间)变为真,那么：

isItPossible(t) = true       for every t <= breaktime

因此,我们可以使用二进制搜索来查找breaktime的最大值.这是伪代码(C语法)：

double low = 0 , high = INF;
while(low < high){
    mid = (low + high) / 2;
    if(isItPossible(mid))
        low = mid;
    else
        high = mid;
}
breakTime = low;

现在唯一剩下的就是实现isItPossible(breaktime)方法.有很多方法可以实现它,但我使用贪心算法和堆优先级队列来解决它.我们需要一个优先级队列来维护一些元组.每个元组包含一个人,该人应该竞争的时间以及我们可以为该人安排比赛的最早时间.我们从时间t0开始(地面的开放时间,例如可能是早上8点),每次我们从最短时间的优先级队列中挑选一个人.这是C like伪代码：

bool isItPossible(double breaktime){
    //Tuple(personId, numberOfCompete, earliestTime)
    priority_queue<Tuple> pq;
    for p in Person_list
        pq.push(Tuple(p,countCompetition(p),t0));

    for(time = t0;time<end_of_ground_time;){
        person = pq.pop();
        add_person_to_scedule_list(person.personId, max(time, person.earliestTime));
        time = max(time, person.earliestTime) + competition_time;
        if(person.numberOfCompete > 1)
            pq.push(Tuple(person.Id,person.numberOfCompete - 1,time + breaktime)));
    }
    return pq.isEmpty();
}

主要问题：

在解决了琐碎的案例后,我们准备解决原来的问题.在这种情况下,存在G = {g1,g2,…,gm}的理由,我们想要安排P = {p1,p2,…,pn}竞争者.就像琐碎的情况一样,我们定义了一个isItPossible(breaktime)函数.我们再次证明这个函数是单调的,所以我们使用二进制搜索来找到最大值(如上面的代码).之后我们只需要实现isItPossible(breaktime)方法.在这种情况下,实现此方法有点棘手.

对于这种方法,您可以执行一些启发式算法或一些创造性的贪婪算法(例如,根据所有理由分配每个人的开始时间基于breakTime,并检查是否可以为所有人执行此操作).但我再次建议您使用Greedy算法和优先级队列,就像琐碎的情况一样.你的元组也应该包含每个人在每个地方竞争的次数,当你想要增加时间并扫除它时,你应该遍历所有理由并同时安排它们.

希望它可以帮到你.当然有一些进化算法,如遗传算法或PSO来解决它(如果你愿意,我也可以解释它们)但是使用上面的方法实现和调试要简单得多.

内容总结

以上是互联网集市为您收集整理的事件条目调度算法PHP全部内容，希望文章能够帮你解决事件条目调度算法PHP所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---