[挑战]查询北京地铁线路

随风

已在顶楼更新北京地铁

dennisle

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

caruko

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

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


而公交的麻烦在于，可能没有直接换乘的站点，需要走几十或者几百米去另一个就近站点去换乘。

neorobin

2号线是环形线路吗?
这对算法是不可忽视的, 在数据文件中也该有标记方式

caruko

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

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


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

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

需要在读取文本时 把每个站前后加特殊符号，然后输入站也添上特殊符号。

plp626

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

全国城市公交线路大全，地铁线路：网上搜索，然后找到网页后wget下载，提取信息，转txt，统一格式；做成数据文件（估计下来有100个城市*40K=4M的数据）；

统一格式为
城市名-gj.txt
X路(首班时间/末班时间/票价/是否单行线)：站点名-站点名...COPY

城市名-dt.txt
X线(票价)：站点名-站点名...COPY

caruko

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

可输出多个： 路线  换乘次数 途经站点数

@ECHO OFF&SETLOCAL ENABLEDELAYEDEXPANSION
set /p input=请输入起点站-终点站:
for /f "tokens=1,2 delims=-, " %%a in ("!input!") do set "start=%%a"&set "end=%%b"
::取得交点。
for /f "tokens=1* delims= " %%a in (dt.txt) do (
    set "xl_%%a=%%b"
    for %%i in (%%b) do set /a #%%i+=1
)
for /f "tokens=1,2 delims=#=" %%a in ('set #') do (
    if !#%%a! geq 2 set "dd_list=!dd_list! %%a"
    set "#%%a="
)
::取得每个交点可到达的线路。
for /f "tokens=2,3 delims=_=" %%a in ('set xl_') do (
    set "str=%%b"
    for /f "tokens=1,2" %%x in ("!start! !end!") do (
        if not "!str:%%x=#!"=="!str!" set "start_xl=!start_xl! %%a"
        if not "!str:%%y=#!"=="!str!" set "end_xl=!end_xl! %%a"
    )
    for %%D in (!dd_list!) do (
        if not "!str:%%D=!"=="!str!" (
            set "%%x=!%%x:%%D=@%%D!"
            set "@%%D=!@%%D! %%a "
)))
::检查是否可直达
for %%a in (!start_xl!) do for %%b in (!end_xl!) do if %%a==%%b set "路线=^"!start! !end!^""
if not "!路线!"=="" goto :metic
::计算换乘路线
set "查询表=^"!start!=!start_xl!^""
set "剩余交点表=!dd_list!"
:loop
for %%i in (!查询表!) do (
for /f "tokens=1* delims==" %%A in ("%%~i") do (
for %%a in (%%B) do (
    for %%b in (!剩余交点表!) do (
        for %%c in (!@%%b!) do (
            if %%a==%%c (
                set "转车点=!转车点! %%b"
                set "剩余查询表=!剩余查询表! ^"%%A %%b=!@%%b:%%c=!^""
                for %%d in (!end_xl!) do for %%e in (!@%%b!) do if %%e==%%d (
                    set "路线=!路线! ^"%%A %%b !end!^" "
)))))))
for %%a in (!剩余交点表!) do for %%b in (!转车点!) do set "剩余交点表=!剩余交点表:%%b=!"
set "查询表=!剩余查询表!"
set "剩余查询表="
set 最多换乘次数+=1
rem if !最多换乘次数! geq 5 goto :metic
rem 注释掉下面这句，使用上面这句可以找到更多换乘次数的路线。
if !路线!.==. goto :loop
::计算站点
:metic
if !路线!.==. echo,无法找到换乘路径&goto :eof
set /a xn=0
for %%a in (!路线!) do (
    set /a xn+=1
    set "线路_!xn!=%%~a"
    set "now="
    set "last="
    set /a 换乘次数_!xn!=0
    for %%a in (%%~a) do (
        set /a 换乘次数_!xn!+=1
        if defined now set "last=!now!"
        set "now=%%a"
        if defined last call :js !xn! !last! !now!
    )
    set /a 换乘次数_!xn!-=2
)
for /l %%i in (1,1,!xn!) do echo,线路%%i:"!线路_%%i: =--!"，换乘 !换乘次数_%%i! 次，途经 !num_%%i! 站
goto :eof
:js
for /f "tokens=1,2 delims==" %%a in ('set xl_') do (
    set "xl=%%b"
    if not "!xl:%2=!"=="!xl!" if not "!xl:%3=!"=="!xl!" (
        set /a n=0
        for %%x in (%%b) do (
            set /a n+=1
            if %%x.==%2. set /a st=n
            if %%x.==%3. set /a et=n
        )
        set /a num=st-et
        if !num! lss 0 set /a num=0-num
        set /a num_%1+=num
)   )COPY

请输入起点站-终点站:奥体中心 西直门
线路1:"奥体中心--北土城--海淀黄庄--西直门"，换乘 2 次，途经 12 站
线路2:"奥体中心--北土城--知春路--西直门"，换乘 2 次，途经 7 站
线路3:"奥体中心--北土城--芍药居--西直门"，换乘 2 次，途经 16 站COPY

caruko

总的来说，就是计算 各个集合之间 相交，相异 的结果。

caruko

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

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

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

batman

23# 随风
if defined zan.%%a set jie.%%a=!zan.%%a! %%i
set zan.%%a=!zan.%%a! %%i
这两句可以合为一句吧：set zan.%%a=!zan.%%a! %%i

mxxcgzxxx

如果把换乘站点独立开来只看做一条线路中的一个节点，如：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
这样行不行？

随风

经验证11楼的比我23楼的精确百倍，也高效百倍..

随风

总算搞出来了，基本符合要求，复杂路线还没测试.

@echo off&setlocal enabledelayedexpansion
for /f "tokens=1* delims= " %%i in (dt.txt) do (
    set max=0
    for %%a in (%%j) do (
         set xian.%%i=!xian.%%i! %%a
         if defined zan.%%a set jie.%%a=!zan.%%a! %%i
         set zan.%%a=!zan.%%a! %%i
         set /a max+=1
         set /a ###%%i.%%a=!max!
    )
)
:: 获取所有线上的节点站名
for /f "tokens=2,3 delims=.=" %%i in ('set jie.') do (
    for %%a in (%%j) do set #%%a=!#%%a! %%i
)
:start
setlocal&cls
set /p xxx=输入起点站和终点站如: 华强路 岗厦北
for /f "tokens=1,2 delims= " %%a in ("!xxx!") do (
    set qix=!zan.%%a!&set "zx=!zan.%%b!"
    set qidian=%%a&set "zongdian=%%b"
    for %%i in (!zan.%%b!) do set zd.%%i=%%i
)
echo !qidian! --- !zongdian!     !qix!  ---  !zx!
echo;.............................................&echo;
:: 判断是否在同一条线
for %%a in (!qix!) do (
    for %%b in (!zx!) do if "%%a"=="%%b" (
        set tong=!tong! %%a
        call :tong !qidian! !zongdian!
        echo !ok!  共 !zzu! 站
        echo;.............................................
    )
)
if defined tong echo;&pause&endlocal&goto :start
rem        起点线    终点线  
call :kai "!qix!"
for /f "tokens=1* delims==" %%i in ('set $') do (
    set "%%i="&set /a mmm=0
    set tong=!qix!&set L1=!qidian!
    for %%k in (%%j) do (
        for /f "tokens=1,2 delims=/" %%a in ("%%k") do (
            set num=%%a&set tong2=%%b
        )
        call :tong !L1! !num!
        set /a mmm+=zzu,%%i+=1
        set tong=!tong2!&set L1=!num!
        echo            !ok! !zzu! 站
    )
    set tong=!zx!
    call :tong !num! !zongdian!
    set /a mmm+=zzu&set "mmm=  !mmm!"
    echo 累计!mmm:~-3!站  !ok! !zzu!站              
    echo;.............................................&echo;
)
echo;&pause&endlocal&goto :start
:kai
for %%a in (%~1) do (
    set t.%%a=a
    for %%b in (!#%%a!) do (rem %%b为%%a线上的节点站名
        for %%c in (!jie.%%b!) do (rem %%c为节点站上的线名
            if not defined t.%%c (
                if not defined zd.%%c (
                    set @=!@! %%b/%%c
                    call :kai "%%c"
                    set "t.%%c="
                    set @=!@: %%b/%%c=!
                    ) else (
                        set /a fl.+=1
                        set $!fl.!=!@! %%b/%%c
                )
            )
        )
    )
)
goto :EOF
:tong
for %%a in (!tong!) do (
    set strq=!###%%a.%1!
    set strz=!###%%a.%2!
    set /a zzu=strq-strz
    set zzu=!zzu:-=!
    set ok=%%a/%1 --- %%a/%2
)
goto :EOFCOPY

caruko

=。= 前面得出的线路基本正确，但是发现根据路线计算出站点数更烦琐。
虽然算法不难。

caruko

其实 这个算法 类似 路由器的 距离向量路由算法，当然还有更高级的链路状态协议，生成树等等。