2007--B题--顶级解决方案

dianslmm

2007--B题--顶级解决方案
问题一,构造不用换车的站点直达式关系矩阵 R，此关系矩阵为0-1矩阵且为稀疏矩阵,应用离散数学传递性运算概念，可知矩阵 R*R 表示中转一次可到达的关系矩阵, R*R*R 为中转两次可到达的关系矩阵，依次类推,巧妙的解决了中转后站点与站点是否可达的判断问题，同时易得到R对应的最小时间耗费矩阵T、最少费用耗费矩阵F和乘车矩阵W。利用这一信息，反向侦测最佳路线，使计算量大为降低，从而避免了通常图论方法的复杂计算。本问题是以顾客出行时间g、行使费用f 和路线查询时间 为目标的三目标规划模型，其中，第三个目标尤为重要，应保证路线查询时间 CT 较小，通常应小于10秒钟,为保证 CT较小，可在实验室把R、R*R、R*R*R、T、F、W等常量矩阵先算好备用，如此CT可达1秒钟内，图论的通常算法无法达此要求。
问题二，将地铁1、2线路视为虚拟公汽线路，将地铁站和相邻的公交车站均虚拟成两两有对开的“公交车”车站,这种“公交车”实为步行，如此,可用问题一的方法解决问题二,不过要用到 R*R*R*R。
问题三，在知道所有站点步行时间的前提下，建立任意两站点间步行时间矩阵Tw，任意两站点间的步行，可虚拟成两两有对开的“公交车”行驶,根据乘客出行心理问卷调查统计分析，易知绝大多数人不愿步行10分钟以上,按此可将直达式关系矩阵 转化为0-1稀疏矩阵，同样可按问题一的方法求解,要用到 R*R*R*R。

优化原则：路线查询时间CT 绝对优先，其后为时间优先，最后为费用优选，即逐次优化。

一种方案实际应用中，若无法使路线查询时间CT 在3秒内，就不是一个好方案，好的方案对硬件要求不会很高。

qingquan1

强！！！！！！！！

tangbaby

行了，我看不下去了，

第一，当使用T和T*T的时候的确可以确定转乘点，TTT就不是非常好办了
第二，图论这好似抄来的，是不会得到国家认可的
第三，给出一种方案是不合理的
第四，路线查询时间不是关键，实际中把查询好的都放在数据库，无需计算直接返回
哎。。。。。不要骂我啊。。

dianslmm

TTT就不是非常好办了----------这当然不会“非常”好办，但和别的方法比算很好办了。
第二，图论这好似抄来的，是不会得到国家认可的-----------ok
第三，给出一种方案是不合理的---------？？？
第四，路线查询时间不是关键，实际中把查询好的都放在数据库------------数据库真能放下全部有关数据么？ 其实主要数据可放，但为给数据库减肥，查询时应有适当计算，即实验室解决大的常量矩阵计算，查询时解决普通计算。

哎。。。。。不要骂我啊----------讨论问题，没什么该骂的。

lwh

这也算顶级解决方案?太复杂!计算量太大!标准答案是穷举搜索法.

dianslmm

实际中把查询好的都放在数据库---------这种数据库，简单计算可知是1000M的一个数据库，查这样大的数据库不知 CT 会怎样。

实验室计算R、R*R、R*R*R、T、F、W........用奔4双核须时为：
R-----5分钟    R*R-----10分钟    R*R*R------12分钟   R*R*R*R------13分钟

R 的 T------5分钟   F------5分钟    W........5分钟
R*R 的 T------30分钟   F------60分钟  
R*R*R 的 T------30分钟   F------60分钟
R*R*R*R 的 T------30分钟   F------60分钟
这样一个城市的交通特证常量数据就完成了，在此基础上，实用中 CT 可在1秒内。


穷举搜索法，遇转车多的CT 会较大，客人会下跑。

lwh

我的穷举搜索法只要几秒钟就搞掂换乘两次的问题.

lwh

反正比赛时间已过,告诉你也不算违规.与一个站点相关联的搜索计算平均500次,换乘两次的搜索量也就只有500*500*500次.所有可能的路径全部扫尽,不漏1条!

深蓝世界

你最大的遗憾是没有模型，这是建模的最大禁忌，虽然图论中矩阵运算行得通．
还有就是建模时不少人用到了数据库，他们都忽视了一个根本问题，自已是在建模比赛而不是数据库开发或界面设计创作

dianslmm

利用所算出的城市交通常量矩阵数据，在反向侦测最佳路线技术中有最优化模型，而且漂亮、简明、易理解。

建模中最大的遗憾是没有模型，这是建模的最大禁忌--------完全赞通你的观点。