建议使用以下浏览器,以获得最佳体验。 IE 9.0+以上版本 Chrome 31+ 谷歌浏览器 Firefox 30+ 火狐浏览器
请选择 进入手机版 | 继续访问电脑版
设置昵称

在此一键设置昵称,即可参与社区互动!

确定
我再想想
选择版块

小原No.1

发帖: 5粉丝: 37

级别 : 版主

Rank: 7Rank: 7Rank: 7

发消息 + 关注

发表于2019-3-9 23:47:01 23383 94 楼主 显示全部楼层
[干货分享] 【答疑解惑】系统调度详细说明 【更新于2019-3-13 16:30】

1、系统调度时间从开始调度进行计算,时间计为0时刻,从0时刻开始计算。每个调度计为一个时间片,一个调度驱动所有车辆行驶一个时间单位。系统调度结束所处的时间片数即为系统调度时间。


2、系统调度最小单位为1个单位,也就是一个时间片,不考虑小数。不会出现1/2见时间单位,1/3时间单位,1/4时间单位等小于一个时间单位的情况。也就是说车辆要么走一个时间单位,要么不走,不会出现车辆先走1/2时间单位,再走1/2时间单位。比如一车辆的可以行驶的速度为3,则一次调度一个时间单位行驶距离3,不能以1/3时间单位、1/3时间单位、1/3时间单位调度且相应行驶距离1、距离1、距离1的情况。


3、车辆最小行驶距离为1,不考虑小数。也就是车辆最小行驶1个单位,不可以先行驶1/2单位,再行驶1/2单位。


4、系统调度先调度在路上行驶的车辆进行行驶,当道路上所有车辆全部不可再行驶后再调度等待上路行驶的车辆。


5、调度等待上路行驶的车辆,按等待车辆ID升序进行调度,进入道路车道依然按车道小优先进行进入。


6、说明一下判题系统的调度处理逻辑:

    第一步:

    该步骤处理所有道路的车辆不影响其他道路上车辆的顺序,因此先调度哪条道路无关紧要。

  •     先处理每条道路上的车辆,将这些车辆进行遍历扫描,如果车在经过行驶速度(前方没有车辆阻挡)可以出路口,将这些车辆标记为等待行驶车辆。

  •     车辆如果行驶过程中,前方没有阻挡并且也不会出路口(v=min(最大车速,道路限速)),则该车辆行驶可行驶的最大车速(v=min(最大车速,道路限速)),此时该车辆在本次调度确定了该时刻的终止位置。该车辆标记为终止状态。

  •     车辆如果行驶过程中,发现前方有车辆阻挡,且阻挡的车辆为等待车辆,则该辆车也被标记为等待行驶车辆。(与阻挡车辆的距离s < v*t)) 其中:v=min(最大车速,道路限速),t=1

  •     车辆如果行驶过程中,发现前方有车辆阻挡,且阻挡的车辆为终止车辆,则该辆车也被标记为终止车辆。(与前方阻挡的车辆的距离记为s)则该车辆最大行驶速度为v = min(最高车速,道路限速,s/t) 其中t=1,该车辆最大可行驶距离为s。

  •     遍历道路上车辆由第一排向最后一排进行遍历,确定每辆车的行驶状态。(出道路处为道路第一排,入道路处为是后一排)


    第二步:

    处理所有路口、道路中处于等待状态的车辆,等待车辆的调度顺序按7、8、9进行调度。


7、整个系统调度按路口ID升序进行调度各个路口,路口内各道路按道路ID升序进行调度。

     

        while(not all car are end state){

            for (all crosses){

                for (roads in cross){

                    runCar();

                    ...

                } 

            }

        }


     每个路口遍历道路时,只调度该道路出路口的方向。

     如图所示则调度路口5时,只调度道路500从路口6到路口5的方向;调度路口6时,只调度道路500从路口5到路口6的方向。

     如:路口5 <-----500------  路口6 

            路口5 ------500----->  路口6

            道路500的起始点为路口5,终止点为路口6      


8、道路内部车辆调度按任务书给定的优先顺序进行调度。

     在每次调度中,调度到的车辆要么行驶其可行驶的最大车速,要么就会因等待其他车辆行驶而处于等待行驶状态,待所等待行驶的车辆行驶后,再使该车辆行驶其可行驶的最大车速。

    是否发生冲突,只与相关道路的第一优先级车辆的行驶方向进行比较,看是否发生冲突   

    每条道路如果当前道路第一优先级车辆不能行驶,则当前道路后面的的车辆都不能行驶,只有第一优先级的车辆行驶了,后面第二优先级才可以确定是否可以行驶。 

2019-3-13:

    每个道路(道路R)一旦有一辆等待车辆(记为车A,所在车道记为C)通过路口而成为终止状态,则会该道路R的车道C上所有车辆进行一次调度,如第一步所示,仅仅处理该道路该车道上能在该车道内行驶后成为终止状态的车辆(对于调度后依然是等待状态的车辆不进行调度,且依然标记为等待状态)

    ----尽可能多、尽可能快地将车辆确定为终止状态

   (本车道内将可以达到终止状态主要目的是尽快让出空位让其他道路的车辆可以进入该道路,同时会重新识别真正等待出路口的车辆,因为有些车辆是因为前车是等待状态而导致自己也是等待状态,有可能他自己这次根本不会出路口,也就是不参与出路口的优先级排序---只有出路口的车辆才参与优先级排序

    假定道路有如下车辆,车AB车速为3,CD均为车速为1

    A空空B空空CD   (路口)

    按步骤一后ABCD均为等待状态。

    在处理待状态车辆D后,假定D前进到其他道路后,此刻道路状态变化为A空空B空空C空   (路口)

    接下来因D车辆的前进后,需要对该条道路该车道的所有车辆进行一次调度,只调度经过一次调度会依然在该车道内车辆且状态为终止状态(不出路口)

    因此:

    C的车速为1,则C车前进1个距离,且为终止状态。A空空B空空空C   (路口)

    B的车速为3,则B车前进3个距离,且为终止状态。A空空空空空BC   (路口)

    A的车速为3,则A车前进3个距离,且为终止状态。空空空A空空BC   (路口)


   调度后道路车辆分布为:空空A空空BC   (路口),且ABC均为终止状态


9、一个时间单位内,一次调度时7与8的调度会出现多次重复调度因每次调度有可能因为等待其他道路车辆的行驶而导致当前车辆无法行驶,因此会循环调度使所有车辆行驶一个时间单位

     每次调度到一条道路,直到该道路无车辆可调度,或该条道路上车辆处于冲突状态。也就是说尽可能多地让该道路上的车辆行驶,直到没有车辆或者车辆与其他车辆发生冲突不可行驶。

     如果本次循环因冲突失去调度权限,则需要等下一次循环,此道路才会获得调度权限。当一个条道路获得调度权限时,尽可能多地让此道路的车辆进行行驶。

     依次按道路ID升序调度该路口所连接的所有道路,再次循环该路口下所有道路,直到所有道路车辆全部处于终态


10、每次车辆调度,该车辆要么不走,要么行驶其可行驶的最大车速。不存在该车辆先走0.5时间单位,再走0.5时间单位的情况。


11、基于10,参赛选手需要注意一次调度能使所有车辆均到达各车辆的行驶速度行驶,就得保证不能出现各车辆循环等待的情况,否则该次调度就会锁死。循环等待是指比如车辆A等待车辆B,车辆B等待车辆C,车辆C等待车辆D,车辆D等待车辆E,车辆E等待车辆F,车辆F等待车辆A的情况。


a)         假定下图各车辆100200300400500600700800车速均为6,图中各道路限速均为8,车辆100300500700均为右转。

b)        图中各条道路长度均为10

c)         因车辆100右转,需要等待车辆800的前行而导致车辆100处于等待状态

d)        因车辆100处于等待状态,而导致车辆200也必须处于等待状态

e)         相同的原因车辆700处于等待状态,车辆800也处于等待状态

f)         同理,车辆300400500600均处于等待状态

g)        如下图中车辆100200300400500600700800均处于等待状态,形成循环等待

如此,下图中各车辆处于相互锁定状态

                                              死锁.png


12、为简化实现,整个系统不存在小数。也就是不存在车辆实际出发时间为小数、调度为小数、行驶距离为小数、车辆速度为小数等。


13、给出如下图例说明一下路口调度顺序:

       假定各道路均为双向道路,且每条道路长度为20(因便于图中仅标示出来长度5)

       图中双黄线为道路中间线,假定双黄线左侧道路全部是空车道,没有车辆阻挡,能够容纳所有进入的车辆(图中仅标示出来长度为5,假定长度为20)。

       假定下图各道路车辆全部处于等待状态

多道路排序.png

1、道路编号如图所示5000、5001、5010、5018

2、车辆编号前方各字母表示方向,不体现在车辆编号中。D:直行;L:左转;R:右转

3、车辆编号为字母后纯数字

4、在本路口调度道路的顺序为5000、5001、5010、5018、5000、5001、5010、5018、5000、5001、5010、5018...5000、5001、5010、5018

5、假设4条道路上所有车辆均可以通过路口,则车辆调度顺序如下:

D100、D200、D201、D202、L203、L204、R205、R206、D207、R208、D400、D401、L402、L403、L404、R405、R406、D407、D408、L101、L300、L301、R302、R303、D304、R305、R306、L307、D308、R102、L103、D104、D105、D106、R107、R108

     首先调度5000道路,只有D100可以走,因为L101左转与5010道路的D200冲突,所以必须等待5010车道上没有直行冲突。

     其次再调度5001道路,因5001道路的L300与道路5018的D400冲突,所以L300必须等待道路5018的D400先行后再调度行驶。

     再次调度道路5010,D200、D201、D202不与其他道路的车辆冲突,可以直接行驶。L203左转,且道路5001无左转车辆与其冲突,因此L203可以左转。L204也可以左转。L205为右转,与左侧道路5000的车辆L101不冲突(只与道路5000的直行会发生冲突),且与道路5018的D400不发生冲突(只与道路5018的左转车辆发生冲突),因此车辆L205可以右转,依次道路5010上的剩余车辆全部可以通过。

    说明:这里假定每调度一辆等待车辆达到终态,都会确定该车道后续车辆有没有因为该等待车辆的前进,而可以在本车道内前进且达到终止状态的车辆(本车道内将可以达到终止状态主要目的是尽快让出空位让其他道路的车辆可以进入该道路,同时会重新识别真正等待出路口的车辆,因为有些车辆是因为前车是等待状态而导致自己也是等待状态,有可能他自己这次根本不会出路口,也就是不参与出路口的优先级排序。同时假定每一次这样的调度该车道的车辆均没有任何一辆可以到达终止状态,全部依然处于等待状态(也就是后续车辆的位置和状态没有发生任何变化)。

     接着调度5018道路上的车辆.....

     再调度道路5000....

     再调度道路5001...

     再调度道路5000....

    (这里每一辆等待车辆调度行驶达到终态,都会进行“说明”部分的操作)

     是否发生冲突,只与相关道路的第一优先级车辆的行驶方向进行比较,看是否发生冲突

    每次调度到一条道路,直到该道路无车辆可调度,或该条道路上车辆处于冲突状态。也就是说尽可能多地让该道路行驶,直到没有车辆或者车辆与其他车辆发生冲突不可行驶。


附伪码(判题器):(输入为car.txt,cross.txt,road.txt answer.txt, 输出为调度时间,总调度时间)

        for(/* 按时间片处理 */) {
            while(/* all car in road run into end state */){
                foreach(roads) {
                    /* 调整所有道路上在道路上的车辆,让道路上车辆前进,只要不出路口且可以到达终止状态的车辆
                     * 分别标记出来等待的车辆(要出路口的车辆,或者因为要出路口的车辆阻挡而不能前进的车辆)
                     * 和终止状态的车辆(在该车道内可以经过这一次调度可以行驶其最大可行驶距离的车辆)*/
                    driveAllCarJustOnRoadToEndState(allChannle);/* 对所有车道进行调整 */

                    /* driveAllCarJustOnRoadToEndState该处理内的算法与性能自行考虑 */
                }
			}
            
            while(/* all car in road run into end state */){
                /* driveAllWaitCar() */
                foreach(crosses){
                    foreach(roads){
			while(/* wait car on the road */){
			    Direction dir = getDirection();
			    Car car = getCarFromRoad(road, dir);
			    if (conflict){
			    	break;
			    }

			    channle = car.getChannel();
			    car.moveToNextRoad();

			    /* driveAllCarJustOnRoadToEndState该处理内的算法与性能自行考虑 */
			    driveAllCarJustOnRoadToEndState(channel);
			}
		    }
                }
            }

            /* 车库中的车辆上路行驶 */
            driveCarInGarage();
        }

   

回复 举报
分享

分享文章到朋友圈

分享文章到微博

齐天码圣

发帖: 18粉丝: 1

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 09:31:16 沙发 显示全部楼层

Untitled.png

在道路500的车1左拐,在道路501的车2直行,按道路ID升序调度应该车1先走,但按直行优于拐弯应该车2先走,请问到底谁先走?

如果车2直行先走,那按道路ID升序调度又有啥意义呢?如果车1先走,那先直行再拐弯又有啥意义呢?

点赞6 回复 举报

阿甘

发帖: 2粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 09:41:20 板凳 显示全部楼层

   

齐天码圣 发表于 2019-3-10 09:31在道路500的车1左拐,在道路501的车2直行,按道路ID升序调度应该车1先走,但按直行优于拐弯应该车2先走,请 ...

按照题意的理解:

1.同道路牌车道号小(车道的编号)车辆优先于车道号大的车辆——单单指同一条道路

2.在不同道路上,直行车辆有优先通行权,直行车辆优先于转车辆

结论:车2先走,车1再走,不存在比较ID序号的问题


ID号的问题应该要发生冲突的时候,才会按ID升序调度把!平常应该就按任务书的规则就行了


点评

顶你: 5.0
顶你: 5
  发表于 2019-3-10 09:48
你还是没理解人家的意思就在这瞎回答,人家主要想问任务书和目前给的调度貌似冲突,如何处理?你这把两个揉在一起自己安排。。。。  发表于 2019-3-10 09:55
我觉得答主的意思很明确了,就是同向行驶车道才会存在ID升序调度,否则都是按照交规进行调度的啊。hello_c点主还是揣摩好出题人意图再点评吧  发表于 2019-3-11 10:26
点赞1 回复 举报

RenZH

发帖: 0粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 10:09:06 地板 显示全部楼层

在“车道固定进入“一节,什么情况下会出现”车道号小的车道没有空位可以进入?“


image.png


也就是201号车为什么需要调度到右边的2号车道,是因为101号车堵在右边1车道末尾了吗?

点赞 回复 举报

RenZH

发帖: 0粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 10:20:04 5# 显示全部楼层
RenZH 发表于 2019-3-10 10:09 在“车道固定进入“一节,什么情况下会出现”车道号小的车道没有空位可以进入?“也就是201号车为什么需要 ...

明白了,是因为201号车无法在右边1号车道上行驶1个时间单位,但是在右边2号车道上可以

点赞 回复 举报

bihuasky

发帖: 0粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 10:31:10 6# 显示全部楼层

一条车道最大容纳车辆数是多少?4?

点赞 回复 举报

RenZH

发帖: 0粉丝: 0

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 10:34:50 7# 显示全部楼层
齐天码圣 发表于 2019-3-10 09:31 在道路500的车1左拐,在道路501的车2直行,按道路ID升序调度应该车1先走,但按直行优于拐弯应该车2先走,请 ...

我认为是如果两辆车都要直行,那么按道路ID升序调度。直行/转弯的优先级大于同一路口道路调度的优先级。

点赞 回复 举报

齐天码圣

发帖: 18粉丝: 1

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 10:46:56 8# 显示全部楼层
RenZH 发表于 2019-3-10 10:34 我认为是如果两辆车都要直行,那么按道路ID升序调度。直行/转弯的优先级大于同一路口道路调度的优先级。

可是如果2辆车都直行,本就去往不同的路,顺序不影响最终结果呀,只有去往同一条路,谁先进谁后进才会影响最终去往同一条路的排布……

点赞 回复 举报

小原No.1

发帖: 5粉丝: 37

级别 : 版主

Rank: 7Rank: 7Rank: 7

发消息 + 关注

发表于2019-3-10 11:32:12 9# 显示全部楼层
齐天码圣 发表于 2019-3-10 09:31 在道路500的车1左拐,在道路501的车2直行,按道路ID升序调度应该车1先走,但按直行优于拐弯应该车2先走,请 ...

先调度500道路上1号车进行行驶,但是发现1号车因与2号车冲突而导致1号车不能行驶,处于等待2号车行驶状态

然后再调度下一条道路501,将2号车直行调度完成后,依次完成502,503的调度,再次调度到501时,就会让1号车行驶


点赞2 回复 举报

yd_7813768...

发帖: 1粉丝: 1

级别 : 新手上路

Rank: 1

发消息 + 关注

发表于2019-3-10 12:20:04 10# 显示全部楼层
小原No.1 发表于 2019-3-10 11:32 先调度500道路上1号车进行行驶,但是发现1号车因与2号车冲突而导致1号车不能行驶,处于等待2号车行驶状态 ...

这样调度岂不是1号车就少走一轮?

点赞 回复 举报

游客

您需要登录后才可以回帖 登录 | 立即注册