最近刚刚接到了一个项目

默难

我老师让我做的, 一个公交车查询系统.
大致是说用户输入起点站和终点站, 系统告诉用户乘坐公交车的路线
和go2map提供的功能类似,但是没有地图功能~具体做什么用我也不知道.
写了一个文档, 把大概方法描述了一下, 目前正在想一些改进方案, 不知道各位有什么意见.

注意: 关于缓存问题 用户模糊查询问题暂时在这个文档中不考虑, 会在以后加进去的. 现在主要讨论的是搜索算法.

[code:1]
        公交车查询系统设计文档

0 约定:
        o 本文档中对大小写敏感.
        o 文档中, 当表示公交车的路次时, 用小写字母a b c...表示.
                例如, 公交车q 则表示q路公交车.
        o 文档中, 当表示公交车的站名时, 用大写字母A B C...表示.
                例如, S站 则表示站名为S的车站.
        o 文档中, 当表示某路公交车在某地设立车站时, 用动词"经过"
                表示. 例如, 公交车x经过S站 则表示公交车x在地名为S
                的地点设立了车站.
        o 文档中, 用字符串STATIONS表示所有车站的集合.
        o 文档中, 用字符串BUSSES表示所有路次的公交车集合.
        o 文档中, <x> = { S | S属于STATIONS; x经过S站 }.
                (x为小写)
        o 文档中, <S> = { x | x属于BUSSES; x经过S站 }.
                (S为大写)

1 资料的存储:
        o 需要存储的资料包括公交车的路次和站次的相关信息, 以及系
                统运行时所用到的相关状态 属性等信息.
        o 资料都将被存储在数据库中.

2 数据库中的表
        o 数据库中的资料被组织成为不同类型的表.
        o 数据库中的表被划分为4种类型.
        o 同一种类型的表可以被多次实现.
        o 不同类型的表之间存在着逻辑上的联系.
        o 不同类型的表在表示的意义上存在着冗余, 其目的是为了加快
                搜索速度.

3 相关数据的表示
        o 为了提高效率, 将会把某些数据以一种便于查找的方式存储
        o 每一个公交车站名将会由一个唯一的数字来表示, 为了表述方
                便,　称表示此类信息的数字为SID(Station ID).
        o 属于不同路次的公交车站, 若其站名相同, 则其SID也相同.
                例如, 公交车x和y同时经过S站, 则S站的SID唯一, 即
                不因其同时属于<x> <y>而不同.
        o 每一路公交车由一个唯一的数字来表示, 为了表述方便, 称表
                示此类信息的数字为BID(Bus ID).
        o BID与其所表示的公交车车次号不存在逻辑上的联系.
                例如, 919路公交车不是必须要用数字919来表示.
        o S-x用来唯一表示属于<x>中的车站S.
        o 若要唯一指定属于<x>中的车站S, 则需同时指定x的BID和S的SID.

4 表的类型
        o 第一种类型(为描述方便, 以后将称此类的表为A类表).
                * A类表中每一项存储着车站站名及其对应的SID.
                * A类表用于系统运行时SID与其对应站名之间的转换.
        o 第二种类型(为描述方便, 以后将称此类的表为B类表).
                * B类表中每一项存储着公交车路次及其对应的BID.
                * B类表用于系统运行时BID与其对应路次之间的转换.
        o 第三种类型(为描述方便, 以后将称此类的表为C类表).
                * C类表中每一项存储着一个SID及一个实数.
                * 每一张C类表对应着一个路次的公交车.
                * 一张C类表中存储的所有的SID表示某一路公交车所经过
                        的所有车站的集合. 例如,        公交车x对应的C类
                        表中存储的SID集合即为<x>.
                * 设一张C类表中的任意一项存储着S站的SID和实数dis.
                        dis即表示: 从起点起沿规定路线至S站所走过的
                        路程长度.
        o 第四种类型(为描述方便, 以后称此类型的表为D类表).
                * D类表中每一项存储着一个BID.
                * 每一张D类表对应着一个车站.
                * 一张D类表中存储的所有BID表示所有经过某一车站的公
                        交车的集合. 例如, S站对应的D类表中存储
                        BID的集合即为<S>.
        o 为了避免产生歧异, 在本文档中字母A B C D将尽量不被用来表
                示其他意义而仅在表示"A类表" "B类表" "C类表" "D类
                表"时使用.

5 路径搜索概述
        o 对于任意站点S, 都可得到<S>; 对于任意属于<S>的公交车x, 可
                得到<x>; 而对于任意属于<x>的车站K, 又可得到<K>...
                依此类推, 则可建立以S为根节点的树. 为了描述方便,
                用Tree(S)来表示以上述方式建立的以S为根节点的树.
        o 对于任意站点S所构建的Tree(S), 设根节点S所处的层为第1层,
                则有: 第2i层中的所有元素均属于集合BUSSES. 第2i-1层
                中的所有元素均属于集合STATIONS.其中i为整数且i>0.
        o 当用户输入起始站S和终点站T时, 系统将对Tree(S)进行搜索, 当
                沿着某一路径搜索, 可以找到某个结点与T相等, 则说明该
                路径满足用户要求.
        o 系统对部分满足要求的路径进行筛选 处理并最终返回给用户.
        o 搜索算法应优先搜索同一层次的元素, 当该层次中的元素没有满
                足要求的元素时, 再考虑进行更深一层次的搜索. 即广度
                优先. 这种做法可以尽量减少换乘车的次数.
        o 设起始站为S, 终点站T. 在搜索过程中, 如果搜索到公交车x并且
                <x>中不包含T, 则在更深一层的子树搜索中, 可以不再搜
                索以x为根的子树. 换言之, 对于同一层中以x为根的子树
                依然要进行搜索.

6 多线程在搜索算法中的运用
        o 一种运用方法是: 对于起始站S和终点站T, 同时建立Tree(S)和
                Tree(T), 从两个方向进行搜索, 寻找一个元素x同时属于
                Tree(S)和Tree(T).
        o 另一种方法是: 仅建立Tree(S), 在搜索过程中, 开启线程搜索
                Tree(S)中的某一子树. 开启数量根据运行环境情况而定.
        o 若采用第一种方法, 需要搜索过程中使搜索Tree(S)和Tree(T)的
                两个线程在一定程度上保持同步. 若采用第二种方法, 数
                据同步的要求相对较低, 且效率不会受到影响.
[/code:1]

Kan

a-star算法,把数据都存在数据库中，把公交线的线路当作道路来处理，站点当做路口来处理