基于带宽来双向搜索路径的方法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利(10)授权公告号(10)授权公告号CNCN102694725102694725B(45)授权公告日2014.10.22(21)申请号201210157473.3靳晓强.双向Dijkstra算法及中间链表加速(22)申请日2012.05.17方法.《计算机仿真》.2004,第21卷(第9期),正文左栏第4行至左栏第6行，图1.(73)专利权人同济大学周躜等.机器人路径规划中的双向地址200092上海市杨浦区四平路1239号Dijkstra二叉树算法.《计算机工程》.2007,第(72)发明人张大陆胡治国匡增美33卷(第10期),第36-40页.(74)专利代理机构上海光华专利事务所31219审查员薛乐梅代理人李仪萍(51)Int.Cl.H04L12/70(2013.01)(56)对比文件CN101358855A,2009.02.04,全文.MostafaH.Dahshan等.Maximum-BandwidthNode-DisjointPaths.《InternationalJournalofAdvancedComputerScienceandApplications》.2012,正文右栏第12行至正文最后一行，图3.权权利要求书1页利要求书1页说明书8页说明书8页附图2页附图2页(54)发明名称基于带宽来双向搜索路径的方法(57)摘要本发明提供基于带宽来双向搜索路径的方法，其包括：1）基于各种族中的每一个节点与各自所拓展的节点之间的链路来确定链路带宽最宽且所述节点之间无父子关系的一个节点，若所确定的节点不属于任何种族，则将所确定的节点归入拓展该节点的节点所属种族中，并将拓展该节点的节点作为所确定的节点的父节点；重复步骤1）直至所确定的节点与拓展该节点的节点分属不同的种族；2）基于各种族中节点与其父节点之间的链路，以及连接各种族的节点之间的链路来确定所述第一节点与第二节点之间的路径，并将所述路径上的各节点标记路径编号。本发明能够以搜索一条路径的复杂度来搜索多条路径，从而提高了运算效率。CN102694725BCN10269475BCN102694725B权利要求书1/1页1.一种基于带宽来双向搜索路径的方法，其特征在于，所述基于带宽来双向搜索路径的方法至少包括：1)预设第一节点与第二节点分属不同种族，且除第一节点和第二节点之外的节点不属于任何种族，且每一个节点均无路径编号；2)基于各种族中的每一个节点与各自所拓展的节点之间的链路来确定链路带宽最宽且各节点之间无父子关系的一个节点，若所确定的节点不属于任何种族，则将所确定的节点归入拓展该节点的节点所属种族中，并将拓展该节点的节点作为所确定的节点的父节点；重复步骤2)，直至所确定的节点与拓展该节点的节点分属不同的种族，则进入步骤3)；3)基于各种族中节点与其父节点之间的链路，以及连接各种族的节点之间的链路来确定所述第一节点与第二节点之间的路径，并将所述路径上的各节点标记路径编号；4)基于已搜索的多条路径的带宽值来将所搜索的多条路径进行排序。2.根据权利要求1所述的基于带宽来双向搜索路径的方法，其特征在于：所述步骤2)还包括：21)基于各种族中的每一个节点与各自所拓展的节点之间的链路来确定除已搜索的节点之间的链路以外的链路带宽最宽且各节点之间无父子关系的一个节点；22)若所确定的节点不属于任何种族，则将所确定的节点归入拓展该节点的节点所属种族中，并将拓展该节点的节点作为所确定的节点的父节点，重复步骤21)；23)若所确定的节点与拓展该节点的节点同属同一种族，且所确定的节点和拓展该节点的节点无路径编号，则重新确定除已搜索的节点之间的链路以外的带宽次宽且各节点之间无父子关系的一个节点，并重复步骤22)，反之，若所确定的节点或拓展该节点的节点具有路径编号，则变更其中无路径编号的节点的种族为一新的种族，并进入步骤3)。3.根据权利要求2所述的基于带宽来双向搜索路径的方法，其特征在于：所述步骤3)还包括：基于各种族中节点与其父节点之间的链路，以及连接各种族的节点之间的链路来确定所述第一节点与第二节点之间的一条路径，并将所述路径上的无路径编号的节点标记一新的路径编号。4.根据权利要求2所述的基于带宽来双向搜索路径的方法，其特征在于：当满足除已搜索的节点之间的链路以外的、节点之间的链路带宽最宽且各节点之间无父子关系条件的节点为多个时，所述步骤2)还包括：以无所属种族的节点优先于具有所属种族的节点的优先级来确定一个节点。5.根据权利要求4所述的基于带宽来双向搜索路径的方法，其特征在于：当满足除已搜索的节点之间的链路以外的、节点之间的链路带宽最宽且各节点之间无父子关系条件的节点为多个时，所述步骤2)还包括：当所述多个节点的优先级