注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mister.Hu(巷里人家)

Go abroad!

 
 
 

日志

 
 
关于我

A campus photograph palyer,an enthusiastic reader,a solitary writer,a future traffic engineer.

网易考拉推荐

第一篇论文代码优化笔记  

2016-02-16 14:09:50|  分类: Senior |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

冲突算法优化

第一篇论文代码优化笔记 - Mister.Hu - Mister.Hu(巷里人家)

改进算法的目的,在于解决之前算法的问题,即,要保证前方行人的冲突优先权,使其充分利用可用空间资源离开场内。这也更符合实际生活中前方行人的运行规律,即,前方行人不会关注后方是否与其产生冲突,不会因为其可能与后方行人产生冲突而选择静止,其关心的是如何尽快到达出口。因此,新的冲突算法改进为:

1)    A的最终路线确定为A1A4中首个不为空的路线,若都为空,则A静止。此处,假设A最终确定的路线为A1

2)    B1A1A的最终路线)比较,如果有冲突,则将B2替换为B1,并以此类推至B4,如果都有冲突,则B静止。此处假设B最终确定的路线为B2

3)    C1A1A的最终路线)和B2B的最终路线)比较,类比步骤2,确定C的最终路线。

4)    类比BC,直至所有的行人路线确定完毕。

而实际上,这个算法对有种情况是无效的,比如,假如A确定的路线为A1,而A1路线与B1的起点有交点,则行人B在与A1比较时,所有路线都会与A1产生冲突(因为行人B的每一条路线的起点都是相同的),而由于A的冲突优先级别比B高,因此,B将只能选择静止,这样,就出现了A选择的路线穿过B的现象。

这个问题在老算法中,是不存在的,因为老算法中,A确定路线时需要与B1 C1 D1进行冲突比较。因此,需要添加新的筛选算法对此类情况进行排除。

最开始的想法是在冲突算法中加上一些判别条件进行排除,结果运行时间马上由120s上升至2000s。经过思考,决定采用冲突解决提前的方法,将此类问题在前期阶段进行解决。从而有了下一部分的优化。

路线筛选代码优化

在老的算法中,先确定行人的A’目标元胞集合,然后针对每一个可能的目标元胞建立初始路线CELL矩阵,然后再建立路线筛选规则,将不合理的路线置空。最终,利用筛选后的路线矩阵进行冲突判别,确定每个行人最终确定的唯一路线。

路线筛选规则中,不合理的路线主要有:

1)路线经过的元胞中,存在障碍物的(如闸机栏杆、墙壁);

2)路线的终点元胞的综合场强大于起点元胞的综合场强;

3)斜线行走时,斜线两侧元胞被行人或障碍物占据;

之前在进行代码性能分析时,耗时最多的块,除了冲突算法就是这个路线筛选代码。而为了解决更新后的冲突代码出现的问题,必须在此处添加新的筛选规则,即:

4)将每一个行人对于的所有路线与其后的所有行人的当前位置进行交集,如果交集不为空,则将行人的该路线置空。

这样,行人在冲突判别之前就保证了不会与其后行人的起点相交,也就避免了上诉的问题。

而在加上这个规则之后,代码的运行时间还是保持在1200s附近,还是不够理想。分析表明,主要是因为路线矩阵太过庞大,而且还是CELL型的,每一次运行都需要将这个矩阵拆开为正常矩阵再进行筛选规则运算。因此,亟需减少运行次数。最终经过思考,在保持所有筛选规则不变的前提下,增加了一些新的条件:

1)不对整个路线矩阵进行判断,首先搜索路线矩阵中不为空的行人,并截取出其路线区间,仅对不为空的路线进行运算。

2)将“路线的终点元胞的综合场强大于起点元胞的综合场强”这个规则再次迁移,放在A’集合确定的算法中完成,即,在确定目标元胞时就将终点元胞的综合场强大于起点的目标元胞删除。

如此,运行时间已经可以缩小到70s,而且运行结果是符合的。

 

:以上运行时间,指的是方案:两个闸机,通行能力为2120,宽度为2m,行人为500,时间为600s(相当于行人流量为3000pedes/h.相同参数在之前的代码中跑需要26000s,即7个多小时。

 

 

 

  评论这张
 
阅读(11)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016