一种导航路线的路段扩张方法及其装置

1.一种导航路线的路段扩张方法，其特征在于，所述方法包括：
在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；
针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，并根据确定的匹配程度对所述备选路段的初始路权值进行修正，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；
分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；
根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。
2.根据权利要求1所述的方法，其特征在于，所述根据确定的匹配程度对所述备选路段的初始路权值进行修正，具体包括：
根据确定的匹配程度确定当前路段与所述备选路段的继承系数；
根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。
3.根据权利要求2所述的方法，其特征在于，所述道路属性为道路类型，道路类型包括高速路、快速路和其他道路，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，具体为：判断所述当前路段的道路类型与备选路段的道路类型是否一致；
根据确定的匹配程度确定当前路段与所述备选路段的继承系数，具体包括：
若所述当前路段与所述备选路段的道路类型一致且均为高速路或快速路，则执行以下步骤：从导航路线中确定出与当前路段连续相连且道路类型一致的路段，并计算确定出的路段与该当前路段的长度和值；将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数；
若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则执行以下步骤：将预置的继承系数作为所述当前路段与备选路段的继承系数。
4.根据权利要求3所述的方法，其特征在于，所述根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数，具体包括：
当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；
当所述长度和值落入的长度范围为所述当前路段对应第二长度范围，则按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；
当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围，则将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。
5.根据权利要求3所述的方法，其特征在于，根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正，具体包括：
若所述当前路段与所述备选路段的道路类型一致，且均为高速路或快速路，则将所述备选路段的初始路权值和当前路段与备选路段的继承系数的乘积，作为所述备选路段修正后的路权值；
若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则将所述备选路段的初始路权值与预置的继承系数的和值，作为所述备选路段修正后的路权值。
6.根据权利要求1至5中任何一项所述的方法，其特征在于，所述分别根据各备选路段的长度、初始路权值和修正后的路权值，确定各备选路段的代价，具体根据下式得到：
P代价＝[(1-p)×Q修正前+p×Q修正后]×L；
其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为预置的初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]；
根据备选路段的代价，从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段，具体为：
将代价最小的备选路段作为所述导航路线的当前路段的下一路段。
7.一种导航路线的路段扩张装置，其特征在于，所述装置包括：路权值获取模块、匹配度确定模块、路权值修正模块、代价确定模块以及路段扩张模块，其中：
所述路权值获取模块，用于在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；
所述匹配度确定模块，用于针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；
所述路权值修正模块，用于根据确定的匹配程度对所述备选路段的初始路权值进行修正；
所述代价确定模块，用于分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；
所述路段扩张模块，用于根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。
8.根据权利要求7所述的装置，其特征在于，所述路权值修正模块包括系数确定单元和路权值修正单元，其中：
所述系数确定单元，用于根据确定的匹配程度确定当前路段与所述备选路段的继承系数；
所述路权值修正单元，用于根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。
9.根据权利要求8所述的装置，其特征在于，所述道路属性为道路类型，所述道路类型包括高速路、快速路和其他道路，所述匹配度确定模块具体用于：判断所述当前路段的道路类型与备选路段的道路类型是否一致；
所述系数确定单元，具体包括：
触发单元，用于在匹配度确定模块判断所述当前路段的道路类型与备选路段的道路类型一致，且均为高速路或快速路时，触发系数确定第一单元；以及，在匹配度确定模块判断所述当前路段的道路类型与备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路时，触发系数确定第二单元；
系数确定第一单元包括路段确定子单元、长度和计算子单元、匹配子单元、系数确定子单元，其中：路段确定子单元，用于从导航路线中确定出与当前路段连续相连且道路类型一致的路段；所述长度和计算子单元，用于计算确定出的路段与该当前路段的长度和值；所述匹配子单元，用于将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；所述系数确定子单元，用于根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数；
系数确定第二单元，用于将预置的继承系数作为所述当前路段与备选路段的继承系数。
10.根据权利要求9所述的装置，其特征在于，所述系数确定子单元，具体用于：
当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；
当所述长度和值落入的长度范围为所述当前路段对应第二长度范围时，按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；
当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围时，将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。
11.根据权利要求8所述的装置，其特征在于，所述路权值修正单元包括求积运算子单元和求和运算子单元，其中：
所述求积运算子单元，用于在所述当前路段与所述备选路段的道路类型一致，且均为高速路或快速路时，将所述备选路段的初始路权值和当前路段与备选路段的继承系数进行求积运算，将求积运算的结果作为所述备选路段修正后的路权值；
所述求和运算子单元，用于在所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路时，将所述备选路段的初始路权值与预置的继承系数进行求和运算，将求和运算得到的和值作为所述备选路段修正后的路权值。
12.根据权利要求7至11中任何一项所述的装置，其特征在于，所述代价确定模块分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价，具体根据下式得到：
P代价＝[(1-p)×Q修正前+p×Q修正后]×L；
其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]；
所述路段扩张模块具体用于：将代价最小的备选路段作为所述导航路线的当前路段的下一路段。

一种导航路线的路段扩张方法及其装置\n技术领域\n[0001] 本申请的实施方式涉及导航领域，尤其涉及一种导航路线的路段扩张方法及其装置。\n背景技术\n[0002] 随着经济社会的迅速发展，路网结构越来越复杂、路网里程越来越长，相同的起终点往往存在多条连接起点和终点的行驶路线，用户选择不同的路线带来的体验存在较大的差别，如某条行驶路线长度最短，某条路线耗时最少，某条路线最为顺畅。通常，用户更愿意选择一条经济合理的路线。目前，为了给用户推荐一条经济合理的路线，用户利用导航工具(如安装有导航软件的设备或导航仪等)根据用户输入的起点和终点规划出一条满足用户要求的导航路线，并将该导航路线推荐给用户。\n[0003] 导航工具在接收到用户输入的起点和终点后，根据路网信息(如路网中各路段的长度、路段的拓扑关系等)从起点开始进行一个路段一个路段的扩张，直至扩张到终点，再将扩张过程中所历经的各个路段所构成的导航路线推荐给用户。\n[0004] 在现有技术中，导航工具实现导航路线的路段扩张的一种技术是最短路段扩张技术。该技术利用DJ搜索算法，在由导航路线的当前路段扩张到下一个路段时，选择与当前路段具有连通关系的距离最短的路段作为本次路段扩展的扩张路段，直至达到目的地。\n[0005] 然而，这种导航路线的路段扩张方式，仅仅考虑路段的长度，而没有考虑路段的其他属性，导致给出的导航路线准确性较低，降低了用户体验。\n发明内容\n[0006] 为了解决现有技术的问题，本申请实施方式提供了一种导航路线的路段扩张方法及其装置，以提高导航路线的准确性。\n[0007] 本申请的实施方式提供的导航路线的路段扩张方法包括：\n[0008] 在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；\n[0009] 针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，并根据确定的匹配程度对所述备选路段的初始路权值进行修正，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；\n[0010] 分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；\n[0011] 根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。\n[0012] 优选地，所述根据确定的匹配程度对所述备选路段的初始路权值进行修正，具体包括：\n[0013] 根据确定的匹配程度确定当前路段与所述备选路段的继承系数；\n[0014] 根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。\n[0015] 优选地，所述道路属性为道路类型，道路类型包括高速路、快速路和其他道路，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，具体为：判断所述当前路段的道路类型与备选路段的道路类型是否一致；\n[0016] 根据确定的匹配程度确定当前路段与所述备选路段的继承系数，具体包括：\n[0017] 若所述当前路段与所述备选路段的道路类型一致，且均为高速路或快速路，则执行以下步骤：从导航路线中确定出与当前路段连续相连且道路类型一致的路段，并计算确定出的路段与该当前路段的长度和值；将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数；\n[0018] 若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则执行以下步骤：将预置的继承系数作为所述当前路段与备选路段的继承系数。\n[0019] 优选地，所述根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数，具体包括：\n[0020] 当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；\n[0021] 当所述长度和值落入的长度范围为所述当前路段对应第二长度范围，则按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；\n[0022] 当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围，则将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。\n[0023] 优选地，根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正，具体包括：\n[0024] 若所述当前路段与所述备选路段的道路类型一致且均为高速路或快速路，则将所述备选路段的初始路权值和当前路段与备选路段的继承系数的乘积，作为所述备选路段修正后的路权值；\n[0025] 若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则将所述备选路段的初始路权值与预置的继承系数的和值，作为所述备选路段修正后的路权值。\n[0026] 优选地，所述分别根据各备选路段的长度、初始路权值和修正后的路权值，确定各备选路段的代价，具体根据下式得到：\n[0027] P代价＝[(1-p)×Q修正前+p×Q修正后]×L；\n[0028] 其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为预置的初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]；\n[0029] 根据备选路段的代价，从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段，具体为：\n[0030] 将代价最小的备选路段作为所述导航路线的当前路段的下一路段。\n[0031] 本申请的实施方式还提供了一种导航路线的路段扩张装置。该装置包括：路权值获取模块、匹配度确定模块、路权值修正模块、代价确定模块以及路段扩张模块，其中：\n[0032] 所述路权值获取模块，用于在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；\n[0033] 所述匹配度确定模块，用于针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；\n[0034] 所述路权值修正模块，用于根据确定的匹配程度对所述备选路段的初始路权值进行修正；\n[0035] 所述代价确定模块，用于分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；\n[0036] 所述路段扩张模块，用于根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。\n[0037] 优选地，所述路权值修正模块包括系数确定单元和路权值修正单元，其中：\n[0038] 所述系数确定单元，用于根据确定的匹配程度确定当前路段与所述备选路段的继承系数；\n[0039] 所述路权值修正单元，用于根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。\n[0040] 优选地，所述道路属性为道路类型，所述道路类型包括高速路、快速路和其他道路，所述匹配度确定模块具体用于：判断所述当前路段的道路类型与备选路段的道路类型是否一致；\n[0041] 所述系数确定单元，具体包括：\n[0042] 触发单元，用于在匹配度确定模块判断所述当前路段的道路类型与备选路段的道路类型一致，且均为高速路或快速路时，触发系数确定第一单元；以及，在匹配度确定模块判断所述当前路段的道路类型与备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路时，触发系数确定第二单元；\n[0043] 系数确定第一单元包括路段确定子单元、长度和计算子单元、匹配子单元、系数确定子单元，其中：路段确定子单元，用于从导航路线中确定出与当前路段连续相连且道路类型一致的路段；所述长度和计算子单元，用于计算确定出的路段与该当前路段的长度和值；\n所述匹配子单元，用于将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；所述系数确定子单元，用于根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数；\n[0044] 系数确定第二单元，用于将预置的继承系数作为所述当前路段与备选路段的继承系数。\n[0045] 优选地，所述系数确定子单元，具体用于：\n[0046] 当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；\n[0047] 当所述长度和值落入的长度范围为所述当前路段对应第二长度范围时，按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；\n[0048] 当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围时，将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。\n[0049] 优选地，所述路权值修正单元包括求积运算子单元和求和运算子单元，其中：\n[0050] 所述求积运算子单元，用于在所述当前路段与所述备选路段的道路类型一致，且均为高速路或快速路时，将所述备选路段的初始路权值和当前路段与备选路段的继承系数进行求积运算，将求积运算的结果作为所述备选路段修正后的路权值；\n[0051] 所述求和运算子单元，用于在所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路时，将所述备选路段的初始路权值与预置的继承系数进行求和运算，将求和运算得到的和值作为所述备选路段修正后的路权值。\n[0052] 优选地，所述代价确定模块分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价，具体根据下式得到：\n[0053] P代价＝[(1-p)×Q修正前+p×Q修正后]×L；\n[0054] 其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为预置的初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]；\n[0055] 所述路段扩张模块具体用于：将代价最小的备选路段作为所述导航路线的当前路段的下一路段。\n[0056] 本申请的实施方式在进行路段扩张过程中，首先，确定当前路段的道路属性分别与该当前路段具有连通关系的备选路段的道路属性之间的匹配程度(匹配程度反映当前路段与所述备选路段之间继承平滑性的程度)；其次，根据确定的匹配程度对各备选路段的初始路权值进行修正；再次，根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；最后，根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。本申请提供的技术方案，从备选路段中扩张导航路线的下一路段时，不仅仅考虑了备选路段的初始路权值，还考虑备选路段与当前路段之间的匹配程度(即继承平滑性)，从而使得到的导航路线中相邻路段之间的继承平滑性尽可能大，在较大程度上符合用户在一次导航中行驶在继承平滑性较好的路段中的需求，进而提高了路线导航的准确性。\n附图说明\n[0057] 通过参考附图阅读下文的详细描述，本发明示例性实施方式的上述以及其他目的、特征和优点将变得易于理解。在附图中，以示例性而非限制性的方式示出了本发明的若干实施方式，其中：\n[0058] 图1为一种路网结构中路段的示意图；\n[0059] 图2为本申请的导航路线的路段扩张方法的一个实施例的流程图；\n[0060] 图3为确定继承系数的一种示意图；\n[0061] 图4a为匹配道路类型为高速路时确定继承系数的实例示意图；\n[0062] 图4b为匹配道路类型为快速路时确定继承系数的实例示意图；\n[0063] 图5为本申请的导航路线的路段扩张装置的一个实施例的结构示意图。\n具体实施方式\n[0064] 下面将参考若干示例性实施方式来描述本发明的原理和精神。应当理解，给出这些实施方式仅仅是为了使本领域技术人员能够更好地理解进而实现本发明，而并非以任何方式限制本发明的范围。相反，提供这些实施方式是为了使本申请更加透彻和完整，并且能够将本申请的范围完整地传达给本领域的技术人员。\n[0065] 为便于本领域技术人员对技术方案的理解，此处对“路段扩张”的概念进行如下说明：在导航软件根据用户输入的起点和终点进行导航路线规划的过程中，需要通过对一段一段路段进行选择而逐步实现，即确定出导航路线的一个路段(后续称为当前路段)之后，从与该当前路段具有连通关系的路段(后续称为备选路段)中选取一条路段作为导航路线的下一路段，该过程便是路段扩张过程的体现。参见图1，假设导航路线的当前路段为ac，则与当前路段ac具有连通关系的备选路段包括ce1、ce2、ce3，从该三条备选路段中选取其中一条备选路段作为导航路线的下一路段即体现为路段扩张。\n[0066] 下面说明本申请实施方式的技术方案。参见图2，该图为本申请的导航路线的路段扩张方法的一个实施例的流程，该流程包括：\n[0067] 步骤S21：在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；\n[0068] 本申请实施例中，步骤S21中与当前路段具有连通关系的路段是指与当前路段的终点连接，且与该当前路段具有连通关系的路段。\n[0069] 如前所述，在当前路段的终点(即当前路段的末端点)可能连接有多条与当前路段具有连通关系的备选路段，从而，由当前路段进行路段扩张到下一个路段存在多种路段选择的可能。优选地，为确定出一条更合理的导航路线，本申请实施方式可以是先获取与当前路段具有连接关系的至少一条通向目的地方向的(注：这里通向目的地方向是指最终通向目的地的方向，在某些情况下，可能在局部出现“折返”现象，但是，这条“折返”路段最终也是能够通向目的地的)备选路段的初始路权值(本申请实施例中，初始路权值可以为预先设置的值，路权值为路段的一个属性，用于表征路段的优劣性，如该路权值可以是对路段长度进行归一化处理之后得到的值，或者，该路权值为根据路段长度、路段的道路级别、路段所属的道路类别等综合计算得到的值)。\n[0070] 本申请实施例中，步骤S21中，获取与当前路段具有连通关系的至少两条备选路段的初始路权值可以是获取所有与当前路段具有连通关系的备选路段的初始路权值。优选地，为进一步提高路段扩张效率，本申请实施例中，步骤S21中，获取与当前路段具有连通关系的至少两条备选路段的初始路权值，并不严格限定是获取所有与当前路段具有连通关系的备选路段的路权值，而是可以获取部分较优的备选路段的路权值。比如，在实际应用过程中，与当前路段具有连通关系的备选路段有3条，而其中有1条备选路段明显较差(如该备选路段的长度太长或太拥堵)，则排除该条备选路段，而将剩下的2条备选路段作为后续操作的对象。\n[0071] 步骤S22：针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；\n[0072] 本申请实施例中，路段的道路属性可以为道路类型，通常可以将道路类型划分为高速路、快速路及其他道路等。道路属性还可以为道路级别，道路级别可以划分为国道、省道、乡村道路等。道路属性还可以是路面质量，路面质量可以划分为上等、中等、下等。\n[0073] 本申请实施例中，确定当前路段的道路属性与备选路段的道路属性的匹配程度，具体可包括：将当前路段的道路属性与备选路段的道路属性进行比较，若相同，则确定两者的匹配程度为一致，若不相同则确定两者的匹配程度为不一致。或者，本申请实施例中，确定当前路段的道路属性与备选路段的道路属性的匹配程度，具体可包括：计算当前路段的道路属性与备选路段的道路属性的相似度，将计算得到的相似度确定为两者的匹配程度；\n或者，将计算得到的相似度与预置的相似度范围进行比较，判断计算得到的相似度落入的相似度范围，并从预置的相似度范围与匹配程度的对应关系中确定出计算得到的相似度对应的匹配程度。\n[0074] 本申请实施例中，匹配程度反映了当前路段与备选路段之间继承平滑性的程度。\n即匹配程度表示当前路段的道路属性值与备选路段的道路属性值的差异程度，匹配程度越高则两者的差异越小，相反，匹配程度越低则两者的差异越大。\n[0075] 举例说明，以道路属性为道路类型为例，假设当前路段为高速路。若备选路段为高速路，由于相同类型的道路建立的标准较为一致(比如，在道路宽度、道路行驶速度、路面质量等方面基本一致)，因此，用户从当前路段驶入到与当前路段的道路类型一致的备选路段时，对于用户而言，差异度并不大，由当前路段过渡到这条备选路段的继承平滑性较高，这表明备选路段与当前路段的匹配程度最高。若备选路段为快速路，由于快速路与高速路建立的标准差异不大(比如，在道路宽度、道路行驶速度、路面质量等方面差异并不大，通常大部分的标准较为一致)，因此，用户从高速路的当前路段驶入到快速路的备选路段时，对于用户而言，虽有一定的差异，但是差异度并不是很大，由当前路段过渡到这条备选路段的继承平滑性相对还可以，这表明，备选路段与当前路段的匹配程度中上等。若备选路段为其他道路(如一些较为狭窄、偏僻的土路)，由于其他道路与高速路建立的标准相差较大，用户从高速路的当前路段驶入到与其他道路的备选路段时，对于用户而言，差异度较大，由当前路段过渡到这条备选路段的继承平滑性较低，这表明，备选路段与当前路段的匹配程度较低。\n由此可见，本发明实施例中，道路类型相同的路段之间的匹配程度最高，高速路与快速路之间的匹配程度高于高速路与其他道路之间的匹配程度，快速路与其他道路之间的匹配程度高于高速路与其他道路之间的匹配程度。\n[0076] 步骤S23：根据确定的匹配程度对所述备选路段的初始路权值进行修正；\n[0077] 步骤S24：分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；\n[0078] 步骤S25：根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。\n[0079] 在上述步骤S23中，根据确定的匹配程度对所述备选路段的初始路权值进行修正，具体实现可如下：根据确定出的匹配程度确定当前路段与备选路段的继承系数；再根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。\n[0080] 本申请实施例中，继承系数能够反映匹配程度，也就是说，该继承系数是与匹配程度关联的一个量，这种关联关系可以体现为各种具体形式，在本申请中可以让继承系数与匹配程度之间存在如下的关系：\n[0081] 如果一条备选路段与当前路段的匹配程度越高，那么，确定出来的继承系数应当能够使得该条备选路段相对于其他备选路段具有更大的概率被选作导航路线的当前路段的下一路段。举例而言，假设多条备选路段的长度相同，如果某条备选路段与当前路段的匹配程度越高，则根据当前路段与备选路段的匹配程度对应的运算策略以及确定出来的继承系数修正该备选路段的初始路权值后所得到的修正路权值应该越小，即这种情况下，匹配程度与修正后路权值成反比例关系。\n[0082] 为便于本领域技术人员对本方案的理解，下面给出两种示例说明根据匹配程度确定继承系数。\n[0083] 示例性方式之一：以道路属性为道路类型为例。在步骤S23中，根据确定的匹配程度确定当前路段与所述备选路段的继承系数，具体可以包括：\n[0084] 1)若所述当前路段与所述备选路段的道路类型一致且均为高速路或快速路，则执行以下步骤A至步骤C：\n[0085] 步骤A：从导航路线中确定出与当前路段连续相连且道路类型一致的路段，并计算确定出的路段与该当前路段的长度和值；例如：假设导航路线从起点开始依次包括ab、bc、cd三个路段，三个路段的长度分别为d1、d2、d3，三个路段的道路类型依次为快速路、高速路、高速路，其中：cd为当前路段，则确定出与当前路段cd连续相连且道路类型一致的路段为bc，则计算路段bc与cd的长度和值为d2+d3。\n[0086] 步骤B：将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；例如：道路类型为高速路，则预置的长度范围可包括[0,10km]、(10km,25km)、[25km,+∞)；道路类型为快速路，则预置的长度范围可包括[0,2km]、(2km,4km)、[4km,+∞)。\n[0087] 步骤C：根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数；具体实现可如下：当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；当所述长度和值落入的长度范围为所述当前路段对应第二长度范围，则按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数，如可根据图3所示的斜率为负值的直线递减函数确定出对应的第二系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围，则将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。\n[0088] 参见图4a、4b，它们示出了按照上述方式确定继承系数的两个实例。图4a示出的第一个实例是当前路段为高速路，备选路段为高速路，第一长度范围为0～10km，第二长度范围为10～25km，第三长度范围为25km以上，相应的第一系数为1.2、第三系数为0.6，第二系数为1.2～0.6之间的数。图4b示出的第二个实例是当前路段为快速路，备选路段为快速路，第一长度范围为0～2km，第二长度范围为2～4km，第三长度范围为4km以上，相应的第一系数为1.0、第三系数为0.8，第二系数为1.0～0.8之间的数。\n[0089] 2)若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则执行以下步骤：将预置的继承系数作为所述当前路段与备选路段的继承系数。一般情况下，匹配程度越高对应的预置的继承系数越低，匹配程度越高对应的预置的继承系数越高。例如：若当前路段为高速路，备选路段为快速路则预置的继承系数为0.2；若前路段为高速路，备选路段为其他道路则预置的继承系数为0.8；若当前路段为快速路，备选路段为高速路则预置的继承系数为0.2；若当前路段为快速路，备选路段为其他道路则预置的继承系数为0.3；若当前路段为其他道路，备选路段为高速路则预置的继承系数为1.0；若当前路段为其他道路，备选路段为快速路则预置的继承系数为0.5。\n[0090] 本申请实施例中，前述步骤S23根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正，具体实现可如下：\n[0091] 若所述当前路段与所述备选路段的道路类型一致且均为高速路或快速路，则将所述备选路段的初始路权值和当前路段与备选路段的继承系数的乘积，作为所述备选路段修正后的路权值；\n[0092] 若所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致且均不为高速路或快速路，则将所述备选路段的初始路权值与预置的继承系数的和值，作为所述备选路段修正后的路权值。\n[0093] 示例性方式之二：以道路属性为路面质量为例，路面质量可划分为上等、中等和下等。路面质量的高低用于评价道路路面平整程度的高低，比如，路面较为平整，通常情况下车辆在该路面上驾驶较为顺畅，难度较低，则可认为路面质量较好；路面坑坑洼洼，则车辆在该路面上驾驶难度较高，则可认为路面质量较差。假设当前路段的路面质量为“上等”，从与当前路段具有连通关系的通向目的地方向存在两条同等长度的备选路段，一条备选路段的路面质量为“中等”(称为第一备选路段)，另一条备选路段的路面质量为“下等”(称为第二备选路段)。当确定备选路段与当前路段的道路属性的匹配程度时，得到当前路段与第一备选路段的匹配程度高于当前路段与第二备选路段的匹配程度(因为由上等路面质量过渡到中等路面质量显然比由上等路面质量过渡到下等路面质量更为平滑，即过渡前后道路属性的差异性更小)，因此，应当让确定的继承系数满足如下要求“根据第一备选路段对应的继承系数对第一备选路段的初始路权值进行修正得到的路权值小于根据第二备选路段对应的继承系数对第二备选路段的初始路权值进行修正后得到的路权值”，在第一备选路段与第二备选路段的初始路权值相等的情况下，需要使得第一备选路段的继承系数小于第二备选路段的继承系数。通常，这种方式使得最终选择的备选路段为中等路面质量的第一备选路段。举例来说，如果第一备选路段的初始路权值为1.2，第二备选路段的初始路权值为\n1.5，如果设定第一备选路段的继承系数为0.8，第二备选路段的继承系数为x，则应当按照这样公式来确定x的值：1.2×0.8＜1.5×x，即x应当大于0.64。当然，在实际应用过程中，可以确定第一备选路段的继承系数的设定规则，还可以规定第二备选路段的继承系数的上下限范围。本发明实施例中，路面质量等级一致的路段之间的匹配程度最高，路面质量为上等的路段与路面质量为中等的路段之间的匹配程度高于路面质量为上等的路段与路面质量为下等的路段之间的匹配程度，路面质量为中等的路段与路面质量为下等的路段之间的匹配程度高于路面质量为上等的路段与路面质量为下等的路段之间的匹配程度。\n[0094] 本申请实施例中，步骤S24分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价，具体根据下式(1)进行：\n[0095] P代价＝[(1-p)×Q修正前+p×Q修正后]×L；  式(1)\n[0096] 其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为预置的初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]。\n[0097] 本申请实施例中，步骤S25根据备选路段的代价，从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段，具体实现可如下：\n[0098] 将代价最小的备选路段作为所述导航路线的当前路段的下一路段。\n[0099] 本申请的实施方式在进行路段扩张过程中，首先，确定当前路段的道路属性分别与该当前路段具有连通关系的备选路段的道路属性之间的匹配程度(匹配程度反映当前路段与所述备选路段之间继承平滑性的程度)；其次，根据确定的匹配程度对各备选路段的初始路权值进行修正；再其次，根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；最后，根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。本申请提供的技术方案，从备选路段中扩张导航路线的下一路段时，不仅仅考虑了备选路段的初始路权值，还考虑备选路段与当前路段之间的匹配程度(即继承平滑性)，从而使得到的导航路线中相邻路段之间的继承平滑性尽可能较大，在较大程度上符合用户在一次导航中行驶在继承平滑性较好的路段中的需求，进而提高了路线导航的准确性。\n[0100] 上述内容详细描述了本申请的导航路线的路段扩张方法的实施方式，与此相应地，本申请还提供了导航路线的路段扩张装置的实施方式。参见图5，该图示出了导航路线的路段扩张装置的一个实施例的组成结构。该装置包括：路权值获取模块51、匹配度确定模块52、路权值修正模块53、代价确定模块54以及路段扩张模块55，其中：\n[0101] 路权值获取模块51，用于在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；\n[0102] 匹配度确定模块52，用于针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，其中所述匹配程度反映当前路段与所述备选路段之间继承平滑性的程度；\n[0103] 路权值修正模块53，用于根据确定的匹配程度对所述备选路段的初始路权值进行修正；\n[0104] 代价确定模块54，用于分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；\n[0105] 路段扩张模块55，用于根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。\n[0106] 上述装置实施例的工作过程是：首先，路权值获取模块51在导航路线的当前路段进行下一路段扩张时，获取与当前路段具有连通关系的至少两条备选路段的初始路权值；\n然后，匹配度确定模块52针对每条备选路段，确定当前路段的道路属性与所述备选路段的道路属性的匹配程度，再由路权值修正模块53根据确定的匹配程度对所述备选路段的初始路权值进行修正；其次，代价确定模块54分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价；最后，路段扩张模块55根据备选路段的代价从所述备选路段中选取一条备选路段作为所述导航路线的当前路段的下一路段。本装置实施例可以取得与前述方法实施例相同或类似的技术效果，为避免重复，这里不再赘言。\n[0107] 在上述装置实施例中，各个功能模块实现其功能的方式不同，其内部组成结构则可能存在差异。比如，对于路权值修正模块53，其可以采用各种方式来实现对初始路权值的修正，从而可以具有不同的内部结构。优选地，本申请路权值修正模块53具体可以包括系数确定单元531和路权值修正单元532，其中：\n[0108] 系数确定单元531，用于根据确定的匹配程度确定当前路段与所述备选路段的继承系数；\n[0109] 路权值修正单元532，用于根据所述当前路段与所述备选路段的匹配程度对应的运算策略、所述当前路段与所述备选路段的继承系数，对所述备选路段的初始路权值进行修正。\n[0110] 优选地，上述路权值修正模块53的结构还可能与匹配度确定模块52采取何种匹配方式相关。在下述的一个示例性场景中，上述路权值修正模块53的系数确定单元531可能包括更细的结构。该场景是道路属性为道路类型，道路类型划分为高速路、快速路和其他道路三种，匹配度确定模块52可以具体用于：判断所述当前路段的道路类型与备选路段的道路类型是否一致；\n[0111] 这种情况下，系数确定单元531具体可以包括触发单元531a、系数确定第一单元\n531b、系数确定第二单元531c，其中：触发单元531a，用于在匹配度确定模块52判断所述当前路段的道路类型与备选路段的道路类型一致，且均为高速路或快速路时，触发系数确定第一单元531b；以及，在匹配度确定模块52判断所述当前路段的道路类型与备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致，且均不为高速路或快速路时，触发系数确定第二单元531c；系数确定第一单元531b可以包括：路段确定子单元\n5311、长度和计算子单元5312、匹配子单元5313、系数确定子单元5314，其中：\n[0112] 路段确定子单元5311，用于从导航路线中确定出与当前路段连续相连且道路类型一致的路段；\n[0113] 长度和计算子单元5312，用于计算确定出的路段与该当前路段的长度和值；\n[0114] 匹配子单元5313，用于将所述长度和值与预置的与所述当前路段的道路类型对应的长度范围进行匹配，确定出所述长度和值落入的长度范围；\n[0115] 系数确定子单元5314，用于根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数。系数确定子单元5314根据所述长度和值落入的长度范围对应的计算策略确定出所述当前路段与所述备选路段的继承系数，具体可以按照下述方式实现：\n[0116] 当所述长度和值落入的长度范围为所述当前路段对应的第一长度范围时，将预置的与第一长度范围对应的第一系数作为所述当前路段与所述备选路段的继承系数；\n[0117] 当所述长度和值落入的长度范围为所述当前路段对应第二长度范围时，按照预置的直线递减函数确定出所述长度和值对应的第二系数，并将第二系数作为所述当前路段与所述备选路段的继承系数；其中所述第二长度范围大于所述第一长度范围，第二系数小于第一系数；\n[0118] 当所述长度和值落入的长度范围为所述当前路段对应的第三长度范围时，将预置的与第三长度范围对应的第三系数作为所述当前路段与所述备选路段的继承系数；其中所述第三长度范围大于第二长度范围，第三系数小于第二系数。\n[0119] 系数确定第二单元531c可以具体用于：将预置的继承系数作为所述当前路段与备选路段的继承系数。\n[0120] 在前述不同的确定继承系数的情形下，路权值修正单元532可以进一步包括求积运算子单元5321和求和运算子单元5322，其中：\n[0121] 求积运算子单元5321，用于在所述当前路段与所述备选路段的道路类型一致，且均为高速路或快速路时，将所述备选路段的初始路权值和当前路段与备选路段的继承系数进行求积运算，将求积运算的结果作为所述备选路段修正后的路权值；\n[0122] 求和运算子单元5322，用于在所述当前路段与所述备选路段的道路类型不一致，或者所述当前路段与所述备选路段的道路类型一致，且均不为高速路或快速路时，将所述备选路段的初始路权值与预置的继承系数进行求和运算，将求和运算得到的和值作为所述备选路段修正后的路权值。\n[0123] 此外，上述装置实施例中的代价确定模块54可以有多种实现其功能的方式，比如，代价确定模块54分别根据各备选路段的长度、初始路权值和修正后的路权值确定各备选路段的代价，可以按照下式进行：\n[0124] P代价＝[(1-p)×Q修正前+p×Q修正后]×L；\n[0125] 其中：P代价为备选路段的代价，Q修正后为备选路段修正后的路权值，Q修正前为备选路段的初始路权值，L为备选路段的长度，p为预置的初始路权值与修正后的路权值的权重比，p取值范围为(0，0.5]；\n[0126] 路段扩张模块55则可以具体用于：将代价最小的备选路段作为所述导航路线的当前路段的下一路段。\n[0127] 应当注意，尽管在上文详细描述中提及了导航路线的路段扩张装置的若干模块、单元，但是这种划分并非强制性的。实际上，根据本申请的实施方式，上文描述的两个或更多单元的特征和功能可以在一个装置中具体化，也可以在不同的装置中具体化。并且，相反地，上文描述的一个单元的特征和功能可以进一步划分为由多个子单元来具体化。\n[0128] 此外，尽管在附图中以特定顺序描述了本申请方法的操作，但是，这并非要求或者暗示必须按照该特定顺序来执行这些操作，或是必须执行全部所示的操作才能实现期望的结果。附加地或备选地，可以省略某些步骤，将多个步骤合并为一个步骤执行，和/或将一个步骤分解为多个步骤执行。\n[0129] 虽然已经参考若干具体实施方式描述了本发明的精神和原理，但是应该理解，本发明并不限于所公开的具体实施方式，对各方面的划分也不意味着这些方面中的特征不能组合以进行受益，这种划分仅是为了表述的方便。本发明旨在涵盖所附权利要求的精神和范围内所包括的各种修改和等同布置。