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

P对NP的世界

Polynomial时间和指数时间的比赛

 
 
 

日志

 
 

2009研究生数学建模竞赛D题的图论模型  

2009-09-21 13:36:03|  分类: 图论中NP问题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
        前天收到王MM短信,要我帮找找去年一个暑期班的图论材料,并且说是今年数学建模D题目比赛用。结果,文件太大,网速太慢,居然传递不过去。 好奇心让我去比赛网站下载D题看了下,果然是图论方面内容。
       该题目大致可以归结为: 一个有湖泊的城市中,有三个重点区域,警车在街道上巡弋,巡逻速度为20km/h,接警后速度为40km/h,当任何道路上发生事故时候,要求为 警车在接警后三分钟内赶到现场的比例不低于90%;而赶到重点部位的时间必须在两分钟之内;,问该区最少需要配置多少辆警车巡逻?
       初初看这个题目,大概可以归结为点控制一类。它和这类题目类似,例如若干条街道构成居民小区,现计划在某些路口安装消防设施,只有与路口直接相连的街道才能使用它们.为了使所有街道在必要时都能使用消防设施,在那些路口安装设施最节省?
     往往教科书图论研究东西都是抽象出来,比较理想化,所以不会涉及移动巡逻问题,即点控制只是是静态的解决方法,不是D题的动态模型。不过这点王MM发短信前就察觉了,难怪能年年能出风头。
    离比赛结束还有大半天,祝愿王MM成功!

   

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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