caruko

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

我跟楼上想法类似，把相交站点作为变量名，保存该线路上的站点名。

caruko

计算线路做出来了，有空补上计算站点数的。  文本是 第5行 的 dt.txt

@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,2* delims=/ " %%a in (dt.txt) do (
    set "xl_%%a=%%c"
    for %%i in (%%c) 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 "剩余查询表="
if !路线!.==. goto :loop
::计算站点
:metic
echo,路线:!路线!
goto :eof
复制代码

caruko

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

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

运行结果如下：

请输入起点站-终点站:华强路 岗厦北
路线: "华强路 世界之窗 岗厦北"  "华强路 大剧院 岗厦北"

请输入起点站-终点站:岗厦 岗厦北
路线:"岗厦 岗厦北"
可能是字符替换导致出问题了 =。=
复制代码

caruko

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

即可得到更多次换乘的结果。

caruko

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

caruko

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

caruko

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

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

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

caruko

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

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
)   )
复制代码

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

caruko

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

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


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

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

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

caruko

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

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


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