Board logo

标题: [挑战]查询北京地铁线路 [打印本页]

作者: 随风    时间: 2011-6-4 16:39     标题: 批处理实现地铁线路查询

a.txt
内容一行为一条地铁线路站名,每站以空格隔开,第一个为线路名,第二个为起点站
  1. 1号线 苹果园 古城 八角游乐园 八宝山 玉泉路 五棵松 万寿路 公主坟 军事博物馆 木樨地 南礼士路 复兴门 西单 天安门西 天安门东 王府井 东单 建国门 永安里 国贸 大望路 四惠
  2. 八通线 四惠 四惠东 高碑店 传媒大学 双桥
  3. 2号线 安定门 雍和宫 东直门 东四十条 朝阳门 建国门 北京站 崇文门 前门 和平门 宣武门 复兴门 阜成门 车公庄 西直门 积水潭 鼓楼大街
  4. 大兴线 天宫门 生物医药基地 义和庄 黄村火车站 黄村西大街 清源路 枣园 高米店南 高米店北 西红门 新宫 公益西桥
  5. 4号线 公益西桥 角门西 马家堡 北京南站 陶然亭 菜市口 宣武门 西单 灵境胡同 西四 平安里 新街口 西直门 动物园 国家图书馆 魏公村 人民大学 海淀黄庄 中关村 北京大学东门 圆明园 西苑 北宫门 安河桥北
  6. 房山线 苏庄 良乡南关 良乡大学城西 良乡大学城 良乡大学城北 广阳城 篱笆房 长阳 稻田 大葆台
  7. 亦庄线 次渠 次渠南 经海路 同济南路 荣昌东街 荣京东街 万源街 亦庄文化园 亦庄桥 旧宫 小红门 肖村 宋家庄
  8. 5号线 宋家庄 刘家窖 蒲黄榆 天坛东门 磁器口 崇文门 东单 灯市口 东四 张自忠路 北新桥 雍和宫 和平里北街 惠新西街南口 惠新西街北口 大屯路东 北苑路北 立水桥南 立水桥 天通苑南 天通苑 天通苑北
  9. 8号线 森林公园南门 奥林匹克公园 奥体中心 北土城
  10. 10号线 劲松 双井 国贸 金台夕照 呼家楼 团结湖 农业展览馆 亮马桥 三元桥 太阳宫 芍药居 惠新西街南口 安贞门 北土城 健德门 牡丹园 西土城 知春路 知春里 海淀黄庄 巴沟
  11. 13号线 西直门 大钟寺 知春路 五道口 上地 西二旗 龙泽 回龙观 霍营 立水桥 北苑 望京西 芍药居 光熙门 柳芳 东直门
  12. 昌平线 南邵 沙河高教园 沙河 巩华城 朱辛庄 生命科学园 西二旗
  13. 机场专线 东直门 三元桥 T2航站楼 T3航站楼
  14. 15号线 望京西 望京 崔各庄 马泉营 孙河 国展 花梨坎 后沙峪
复制代码
要求:
  输入出发地点和终点名  如: 奥体中心 西直门
  显示: 出发点到目的地的最少换乘,和最短线路(以过站数量决定距离) 以及过站数量
   或是列出所有能到达目的地的线路、换乘次数、过站数量。(北京地铁不建议如此,若是穷举的话随便就过百)
   附上地图辅助验证
代码要求: 要有通用性,即以后若要添加站名、线路只需更改a.txt内容即可,不需改代码。
作者: plp626    时间: 2011-6-4 16:45

主要是算法,
但,对于批处理来说,
即使有了好算法,写出来也读不懂,
长!

放到挑战区也是难题
作者: 随风    时间: 2011-6-4 16:55

call 递归 应该是可以完成的,只是太绕,我实在绕不下去了。
思路:模拟列车开出,途中遇可换乘站自动换乘,这样就可以把所有线路都走一篇,计算下距离即可。
只是说起容易做起来难,计算时被call绕晕了。
换种思路
先得出a到b需要乘坐哪几条线,到哪些站中转,再模拟开一趟,计算出最近的
作者: plp626    时间: 2011-6-4 17:01

要通用的话难度颇大,娱乐的话,太耗时间,这类图论问题解决思路不是面向过程是思维,所以批处理来做很难调试,要可扩展更难。
---------仅代表个人观点-------------

namejm以前写过一个超长的公交线路查询,我从来没读完过,随风可否借鉴下。。
作者: 随风    时间: 2011-6-4 17:07

jm的那个公共线路我只听过,从未看过,当初还以为只是查询单线路a到b的站名呢?难道jm早在N年前就做出来了?
不过你都没耐心看完,我想我就更没那耐心了 ^_^
看代码比写还累。
作者: CrLf    时间: 2011-6-4 17:11

好难啊,考虑到转三趟车就太复杂了,还要计算经过的站数...
只会findstr的路过打酱油
作者: hanyeguxing    时间: 2011-6-4 17:39

本帖最后由 hanyeguxing 于 2011-6-4 17:44 编辑

个人观点:
第一次运行时,生成辅助文本,该文本枚举所有可能线路,包含换乘(换乘点前加#,站间用-)。
然后每次查询运行时直接查询此辅助文件,直接统计#和-的个数。
这样做,只有第一次运行会慢,以后都会很快。
作者: namejm    时间: 2011-6-4 17:40

我以前写的那个公交线路查询在这里
批处理版公交线路信息查询器[2006-11-10](http://bbs.bathome.net/viewthread.php?tid=2141
rem ========== 查询换乘方案 ==========
:: 换乘线路只能查到匹配的第一条,可能不是最短线路

所以,那个方案不适用于本题
楼主的题目用批处理也是可以做到的
目前只有一个比较模糊的思路
还有待验证:
首先,用批处理把所有线路的站点数量计算出来并加以保存
然后,把所有线路的所有相交站点罗列出来,并记录下该站点在这些线路上位于第几站,剩余多少站
每两条线路为一对数据,保存在同一行上
然后以起止站点为关键词在配置文件和临时文件中查找
起始站点往前搜索,碰到第一个相交站点暂停下来
终止站点往后回溯,碰到第一个相交站点暂停下来
然后,再以这两个站点继续重复上一步骤
不过需要加上一些判断
总之,就是两头往中间碰
作者: caruko    时间: 2011-6-5 01:03

没去过北京,我说怎么站名这么眼熟,明明是深圳嘛。

我跟楼上想法类似,把相交站点作为变量名,保存该线路上的站点名。
作者: caruko    时间: 2011-6-5 21:01

本帖最后由 caruko 于 2011-6-5 21:17 编辑

计算线路做出来了,有空补上计算站点数的。  文本是 第5行 的 dt.txt
  1. @ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
  2. set /p input=请输入起点站-终点站:
  3. for /f "tokens=1,2 delims=-, " %%a in ("!input!") do set "start=%%a"&set "end=%%b"
  4. ::取得交点。
  5. for /f "tokens=1,2* delims=/ " %%a in (dt.txt) do (
  6.     set "xl_%%a=%%c"
  7.     for %%i in (%%c) do set /a #%%i+=1
  8. )
  9. for /f "tokens=1,2 delims=#=" %%a in ('set #') do (
  10.     if !#%%a! geq 2 set "dd_list=!dd_list! %%a"
  11.     set "#%%a="
  12. )
  13. ::取得每个交点可到达的线路。
  14. for /f "tokens=2,3 delims=_=" %%a in ('set xl_') do (
  15.     set "str=%%b"
  16.     for /f "tokens=1,2" %%x in ("!start! !end!") do (
  17.         if not "!str:%%x=!"=="!str!" set "start_xl=!start_xl! %%a"
  18.         if not "!str:%%y=!"=="!str!" set "end_xl=!end_xl! %%a"
  19.     )
  20.     for %%D in (!dd_list!) do (
  21.         if not "!str:%%D=!"=="!str!" (
  22.             set "%%x=!%%x:%%D=@%%D!"
  23.             set "@%%D=!@%%D! %%a "
  24. )))
  25. ::检查是否可直达
  26. for %%a in (!start_xl!) do for %%b in (!end_xl!) do if %%a==%%b set "路线=^"!start! !end!^""
  27. if not "!路线!"=="" goto :metic
  28. ::计算换乘路线
  29. set "查询表=^"!start!=!start_xl!^""
  30. set "剩余交点表=!dd_list!"
  31. :loop
  32. for %%i in (!查询表!) do (
  33. for /f "tokens=1* delims==" %%A in ("%%~i") do (
  34. for %%a in (%%B) do (
  35.     for %%b in (!剩余交点表!) do (
  36.         for %%c in (!@%%b!) do (
  37.             if %%a==%%c (
  38.                 set "转车点=!转车点! %%b"
  39.                 set "剩余查询表=!剩余查询表! ^"%%A %%b=!@%%b:%%c=!^""
  40.                 for %%d in (!end_xl!) do for %%e in (!@%%b!) do if %%e==%%d (
  41.                     set "路线=!路线! ^"%%A %%b !end!^" "
  42. )))))))
  43. for %%a in (!剩余交点表!) do for %%b in (!转车点!) do set "剩余交点表=!剩余交点表:%%b=!"
  44. set "查询表=!剩余查询表!"
  45. set "剩余查询表="
  46. if !路线!.==. goto :loop
  47. ::计算站点
  48. :metic
  49. echo,路线:!路线!
  50. goto :eof
复制代码

作者: 随风    时间: 2011-6-5 21:18

输入 华强路 岗厦北
路线: "华强路 世界之窗 岗厦北"  "华强路 大剧院 岗厦北"
少了条 "华强路 世界之窗 岗厦北 会展中心 市民中心"

输入 岗厦 岗厦北
路线:"岗厦 岗厦北" "岗厦 世界之窗 岗厦北"  "岗厦 大剧院 岗厦北"  "岗厦 世界之窗
岗厦北"  "岗厦 大剧院 岗厦北"  "岗厦 市民中心 岗厦北"  "岗厦 黄贝岭 岗厦北"
"岗厦 岗厦北" 少了两站
"岗厦 市民中心 岗厦北" 少了"市民中心"
"岗厦 黄贝岭 岗厦北" 少了"大剧院"
作者: caruko    时间: 2011-6-5 21:27

本帖最后由 caruko 于 2011-6-5 21:35 编辑

我这个代码 是只把换乘点写进去。
然后根据这个路线去计算,并找到最短路径。
不是最终结果。

对了...前次提交的有个BUG,把 !路线! 写成 !线路! 了。
现在正常了。

运行结果如下:
  1. 请输入起点站-终点站:华强路 岗厦北
  2. 路线: "华强路 世界之窗 岗厦北"  "华强路 大剧院 岗厦北"
  3. 请输入起点站-终点站:岗厦 岗厦北
  4. 路线:"岗厦 岗厦北"
  5. 可能是字符替换导致出问题了 =。=
复制代码

作者: caruko    时间: 2011-6-5 21:42

代码是按层次计算的,找到匹配的就退出了。 所以层次多的不包括在内。
但是把  if !路线!.==. goto :loop
改成  set /a n+=1&if !n! lss 10 goto :loop

即可得到更多次换乘的结果。
作者: batman    时间: 2011-6-5 22:04

个人感觉制成图,将站标为坐标,然后根据两点间的直线穿过的线路来算可能会容易点。。。。

有图有真相:
作者: batman    时间: 2011-6-5 22:09

plp数学强人制作一个数学模型来计算吧。。。

个人是有心无力哦。。。
作者: 随风    时间: 2011-6-5 22:10

也考虑过坐标,可是批处理不知道如何弄啊
现在是获取出发点的车次到目的地的车次,只要在交接点中查询就可以了
call 在语句块中递归,能最终找到目的,但无法正确计算途中经过的节点,抓狂中。。
作者: CrLf    时间: 2011-6-5 22:11

用坐标如何保证站点之间遵循严格的几何形呢?看上去是正方形的路线难免不会出现上底下底站点数不一样的情况。

现在的想法是双向递归,从两点开始层层遍历(就像小时候走复杂的迷宫一样),直到可行的路线相互碰撞,不过说起来容易,做起来...
作者: batman    时间: 2011-6-5 22:18

我在看此题时写了一个步骤:

首先找出节点站  一级 二级 三级。。。同时将线路和站点均设为变量

1、先打本线路上是不是有这个站 有a-b 没有向下

2、确定目的站在哪条或哪几条线上

3、查找本线路上哪个站在这些线路上 列出所有a-c-b 没有向下

4、查找本线路上所有的节点站 找出这些节点站所在线路的其他节点站是否在目的站所在线路上 a-c-d-b 再没有(四次换乘)脑子不够用了。。。
作者: plp626    时间: 2011-6-5 22:23

我目前对于通用模型没有思路,以下资料有感兴趣的可以参考下:
http://jpkc.cug.edu.cn/08jpkc/pengfang57/bigclass/09/lw/028.htm

http://download.csdn.net/source/1056130/

http://download.csdn.net/source/1710561

http://slcx.sci.bupt.cn/sxjm/paper/source/cumcm2007/cumcm0747.PDF

http://wenku.baidu.com/view/857e4cc5bb4cf7ec4afed04a.html

http://jsj.sict.edu.cn/jpkc/dotnet/jxzy/BS/gjcx/PPT/gjxz06.ppt
作者: 523066680    时间: 2011-6-5 22:39

我勒个去,这就是一个草...马



                                                                                   ,,,,,,,,,,,,,,,,,,,,,,,,.
                                                                                  Gr;.sr.rr.rr.rr.rs,;s:,sr
                                                                                 S@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 r@                        
                                                                                 ;B                        
                              ..      .             ..  .                        S@                        
                         .@#@@BH@@A#@#A@@BB@@A#@#A@@@@@MH@#H@#A@#A@#A@@A@@@@@@BA#@@;                        
                        B@s                                                      ;@#@:                     
                      S@A                                                           ;@@                     
                    @                                                               3@S                  
                   @@                                                                   @r                  
                 3@X                                                                    @s                  
               ;@@                                                                      @r                  
             ,#@,                                                                       @s                  
            H@r                                     .                                   @r                  
          i@B                                       @A                          .#i     @s                  
        :@@                                         @B                        s@@@@     @;                  
       #r:                        .. . .. .  ... .; @@   ..  ...  ...      i@@#: r@  .  @5                  
     5@3                     MH3A3hAGAh3A9G&GA99&&@h@@rSX&&X29Ah229&h2ssH@@@#r,;;M@rX952@M5hi               
   :@X                       #                      GS                rMMr       ;@                        
  @@2 ,;;:          ;ssrrsr:,@2:;;;;;:;;:;;:;;:;;;r:@@,:;:;;;;:;;;;;A@9.         r#                        
  3is2&2r;          rhhS23r2@HXSXSS35iX2i22i2Xi22XA2@@rSXiSX2Xi5X5XS;            s#                        
                          ;2.                       92                           i@                        
                        ;Hi                         H3                           s@                        
                      ,#X                           &5                           5@                        
                     AB.                            @&                           :r                        
                   S#;                              #A                                                      
                 ;M2                                @H                                                      
               .&H,                                 ::                                                      
              5#r                                                                                          
            r@5                                                                                             
          ,MA                                                                                               
        .A#:                                                                                                
       .;.                                                                                                  



作者: caruko    时间: 2011-6-5 22:39

其实 这个算法 类似 路由器的 距离向量路由算法,当然还有更高级的链路状态协议,生成树等等。
作者: caruko    时间: 2011-6-5 22:52

=。= 前面得出的线路基本正确,但是发现根据路线计算出站点数更烦琐。
虽然算法不难。
作者: 随风    时间: 2011-6-6 05:47

本帖最后由 随风 于 2011-6-6 05:50 编辑

总算搞出来了,基本符合要求,复杂路线还没测试.
  1. @echo off&setlocal enabledelayedexpansion
  2. for /f "tokens=1* delims= " %%i in (dt.txt) do (
  3.     set max=0
  4.     for %%a in (%%j) do (
  5.          set xian.%%i=!xian.%%i! %%a
  6.          if defined zan.%%a set jie.%%a=!zan.%%a! %%i
  7.          set zan.%%a=!zan.%%a! %%i
  8.          set /a max+=1
  9.          set /a ###%%i.%%a=!max!
  10.     )
  11. )
  12. :: 获取所有线上的节点站名
  13. for /f "tokens=2,3 delims=.=" %%i in ('set jie.') do (
  14.     for %%a in (%%j) do set #%%a=!#%%a! %%i
  15. )
  16. :start
  17. setlocal&cls
  18. set /p xxx=输入起点站和终点站如: 华强路 岗厦北
  19. for /f "tokens=1,2 delims= " %%a in ("!xxx!") do (
  20.     set qix=!zan.%%a!&set "zx=!zan.%%b!"
  21.     set qidian=%%a&set "zongdian=%%b"
  22.     for %%i in (!zan.%%b!) do set zd.%%i=%%i
  23. )
  24. echo !qidian! --- !zongdian!     !qix!  ---  !zx!
  25. echo;.............................................&echo;
  26. :: 判断是否在同一条线
  27. for %%a in (!qix!) do (
  28.     for %%b in (!zx!) do if "%%a"=="%%b" (
  29.         set tong=!tong! %%a
  30.         call :tong !qidian! !zongdian!
  31.         echo !ok!  共 !zzu! 站
  32.         echo;.............................................
  33.     )
  34. )
  35. if defined tong echo;&pause&endlocal&goto :start
  36. rem        起点线    终点线  
  37. call :kai "!qix!"
  38. for /f "tokens=1* delims==" %%i in ('set $') do (
  39.     set "%%i="&set /a mmm=0
  40.     set tong=!qix!&set L1=!qidian!
  41.     for %%k in (%%j) do (
  42.         for /f "tokens=1,2 delims=/" %%a in ("%%k") do (
  43.             set num=%%a&set tong2=%%b
  44.         )
  45.         call :tong !L1! !num!
  46.         set /a mmm+=zzu,%%i+=1
  47.         set tong=!tong2!&set L1=!num!
  48.         echo            !ok! !zzu! 站
  49.     )
  50.     set tong=!zx!
  51.     call :tong !num! !zongdian!
  52.     set /a mmm+=zzu&set "mmm=  !mmm!"
  53.     echo 累计!mmm:~-3!站  !ok! !zzu!站              
  54.     echo;.............................................&echo;
  55. )
  56. echo;&pause&endlocal&goto :start
  57. :kai
  58. for %%a in (%~1) do (
  59.     set t.%%a=a
  60.     for %%b in (!#%%a!) do (rem %%b为%%a线上的节点站名
  61.         for %%c in (!jie.%%b!) do (rem %%c为节点站上的线名
  62.             if not defined t.%%c (
  63.                 if not defined zd.%%c (
  64.                     set @=!@! %%b/%%c
  65.                     call :kai "%%c"
  66.                     set "t.%%c="
  67.                     set @=!@: %%b/%%c=!
  68.                     ) else (
  69.                         set /a fl.+=1
  70.                         set $!fl.!=!@! %%b/%%c
  71.                 )
  72.             )
  73.         )
  74.     )
  75. )
  76. goto :EOF
  77. :tong
  78. for %%a in (!tong!) do (
  79.     set strq=!###%%a.%1!
  80.     set strz=!###%%a.%2!
  81.     set /a zzu=strq-strz
  82.     set zzu=!zzu:-=!
  83.     set ok=%%a/%1 --- %%a/%2
  84. )
  85. goto :EOF
复制代码

作者: 随风    时间: 2011-6-6 07:36     标题: [挑战]查询北京地铁线路

本帖最后由 随风 于 2011-6-6 14:14 编辑

已在顶楼更新北京地铁
作者: 随风    时间: 2011-6-6 07:42

经验证11楼的比我23楼的精确百倍,也高效百倍..
作者: mxxcgzxxx    时间: 2011-6-6 09:16

如果把换乘站点独立开来只看做一条线路中的一个节点,如:422  502   都是布吉
将路线拉直看做一个大函数以进行正向计算,如:
龙岗(5 16 1 422)表示:龙岗是线路5,16个站点,1个换乘点,1号换乘点通向422(4路22号)
环中(4 27 2 502 228)表示:环中4号线,27站点,2个换乘点,1号502 ,2号228
这样行不行?
作者: batman    时间: 2011-6-6 10:15

23# 随风
if defined zan.%%a set jie.%%a=!zan.%%a! %%i
set zan.%%a=!zan.%%a! %%i
这两句可以合为一句吧:set zan.%%a=!zan.%%a! %%i
作者: caruko    时间: 2011-6-6 12:28

=.= 我就解释一下我的算法吧。。。

第一步: 统计各个站点出现的次数,>=2的是交点。
第二步: 统计每个交点连接哪几条线路。 比如 @世界之窗=蛇口线 罗宝线
第三步: 计算 起点-终点 是否在一条线上,可直达。

换乘的算法:
假如:
起点 在 A 线路上
A线路 ∈ X交点集合(包含能直接到达的线路)
:loop
"X交点(除去A线路) ∩ 除X以外的剩余交点" , 同时计算"X ∩ 终点"是否成立,成立则退出循环返回结果。
如果 X  跟 Y  相交(就是Y交点含有X交点中的线路)
"Y 交点(除去跟X相交的站点) ∩ 除XY以外的交点" ,  计算 "Y ∩ 终点" 是否成立。
goto :loop
作者: caruko    时间: 2011-6-6 12:32

总的来说,就是计算 各个集合之间 相交,相异 的结果。
作者: caruko    时间: 2011-6-6 14:35

本帖最后由 caruko 于 2011-6-6 14:40 编辑

这是完善版本,默认只输出换乘次数最少的路线。要得到更多换乘次数的路线,注释掉49行。

可输出多个: 路线  换乘次数 途经站点数
  1. @ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
  2. set /p input=请输入起点站-终点站:
  3. for /f "tokens=1,2 delims=-, " %%a in ("!input!") do set "start=%%a"&set "end=%%b"
  4. ::取得交点。
  5. for /f "tokens=1* delims= " %%a in (dt.txt) do (
  6.     set "xl_%%a=%%b"
  7.     for %%i in (%%b) do set /a #%%i+=1
  8. )
  9. for /f "tokens=1,2 delims=#=" %%a in ('set #') do (
  10.     if !#%%a! geq 2 set "dd_list=!dd_list! %%a"
  11.     set "#%%a="
  12. )
  13. ::取得每个交点可到达的线路。
  14. for /f "tokens=2,3 delims=_=" %%a in ('set xl_') do (
  15.     set "str=%%b"
  16.     for /f "tokens=1,2" %%x in ("!start! !end!") do (
  17.         if not "!str:%%x=#!"=="!str!" set "start_xl=!start_xl! %%a"
  18.         if not "!str:%%y=#!"=="!str!" set "end_xl=!end_xl! %%a"
  19.     )
  20.     for %%D in (!dd_list!) do (
  21.         if not "!str:%%D=!"=="!str!" (
  22.             set "%%x=!%%x:%%D=@%%D!"
  23.             set "@%%D=!@%%D! %%a "
  24. )))
  25. ::检查是否可直达
  26. for %%a in (!start_xl!) do for %%b in (!end_xl!) do if %%a==%%b set "路线=^"!start! !end!^""
  27. if not "!路线!"=="" goto :metic
  28. ::计算换乘路线
  29. set "查询表=^"!start!=!start_xl!^""
  30. set "剩余交点表=!dd_list!"
  31. :loop
  32. for %%i in (!查询表!) do (
  33. for /f "tokens=1* delims==" %%A in ("%%~i") do (
  34. for %%a in (%%B) do (
  35.     for %%b in (!剩余交点表!) do (
  36.         for %%c in (!@%%b!) do (
  37.             if %%a==%%c (
  38.                 set "转车点=!转车点! %%b"
  39.                 set "剩余查询表=!剩余查询表! ^"%%A %%b=!@%%b:%%c=!^""
  40.                 for %%d in (!end_xl!) do for %%e in (!@%%b!) do if %%e==%%d (
  41.                     set "路线=!路线! ^"%%A %%b !end!^" "
  42. )))))))
  43. for %%a in (!剩余交点表!) do for %%b in (!转车点!) do set "剩余交点表=!剩余交点表:%%b=!"
  44. set "查询表=!剩余查询表!"
  45. set "剩余查询表="
  46. set 最多换乘次数+=1
  47. rem if !最多换乘次数! geq 5 goto :metic
  48. rem 注释掉下面这句,使用上面这句可以找到更多换乘次数的路线。
  49. if !路线!.==. goto :loop
  50. ::计算站点
  51. :metic
  52. if !路线!.==. echo,无法找到换乘路径&goto :eof
  53. set /a xn=0
  54. for %%a in (!路线!) do (
  55.     set /a xn+=1
  56.     set "线路_!xn!=%%~a"
  57.     set "now="
  58.     set "last="
  59.     set /a 换乘次数_!xn!=0
  60.     for %%a in (%%~a) do (
  61.         set /a 换乘次数_!xn!+=1
  62.         if defined now set "last=!now!"
  63.         set "now=%%a"
  64.         if defined last call :js !xn! !last! !now!
  65.     )
  66.     set /a 换乘次数_!xn!-=2
  67. )
  68. for /l %%i in (1,1,!xn!) do echo,线路%%i:"!线路_%%i: =--!",换乘 !换乘次数_%%i! 次,途经 !num_%%i! 站
  69. goto :eof
  70. :js
  71. for /f "tokens=1,2 delims==" %%a in ('set xl_') do (
  72.     set "xl=%%b"
  73.     if not "!xl:%2=!"=="!xl!" if not "!xl:%3=!"=="!xl!" (
  74.         set /a n=0
  75.         for %%x in (%%b) do (
  76.             set /a n+=1
  77.             if %%x.==%2. set /a st=n
  78.             if %%x.==%3. set /a et=n
  79.         )
  80.         set /a num=st-et
  81.         if !num! lss 0 set /a num=0-num
  82.         set /a num_%1+=num
  83. )   )
复制代码
  1. 请输入起点站-终点站:奥体中心 西直门
  2. 线路1:"奥体中心--北土城--海淀黄庄--西直门",换乘 2 次,途经 12 站
  3. 线路2:"奥体中心--北土城--知春路--西直门",换乘 2 次,途经 7 站
  4. 线路3:"奥体中心--北土城--芍药居--西直门",换乘 2 次,途经 16 站
复制代码

作者: plp626    时间: 2011-6-6 15:41

谁有兴趣有时间做个全国城市公交线路查询,地铁线路查询;

全国城市公交线路大全,地铁线路:网上搜索,然后找到网页后wget下载,提取信息,转txt,统一格式;做成数据文件(估计下来有100个城市*40K=4M的数据);
  1. 统一格式为
  2. 城市名-gj.txt
  3. X路(首班时间/末班时间/票价/是否单行线):站点名-站点名...
复制代码
  1. 城市名-dt.txt
  2. X线(票价):站点名-站点名...
复制代码

作者: caruko    时间: 2011-6-6 15:51

太复杂了,公交路线更复杂,计算更慢。

用高级语言,用数据结构数组来做要省事多了。


而且我的代码没有加上防重复处理。

岗厦,岗厦北  这样的站会出错。

需要在读取文本时 把每个站前后加特殊符号,然后输入站也添上特殊符号。
作者: neorobin    时间: 2011-6-6 19:22

2号线是环形线路吗?
这对算法是不可忽视的, 在数据文件中也该有标记方式
作者: caruko    时间: 2011-6-6 23:23

本帖最后由 caruko 于 2011-6-6 23:25 编辑

环路是没问题的,每个交点只使用一次,而且换乘次数有上限限制。

目前代码中只会判断某条线路上一次使用过下一次就不会使用,但间隔一次后还能进入判断列表,所以,可能会出现走1次回头路的情况。


而公交的麻烦在于,可能没有直接换乘的站点,需要走几十或者几百米去另一个就近站点去换乘。
作者: dennisle    时间: 2011-6-10 15:30

看了前輩們的代碼 "暈",
不知何時小弟才能看懂呢




欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2