复杂的城市轨道交通线网给乘客提供多种出行路径选择,而轨道网络起讫点间可能存在多条可选有效路径,给城市轨道客流清分工作带来难度。为求解相同起讫站点间各路线乘客选择的概率问题,以广州市地铁自动售检票(automaticfarecollection,A...复杂的城市轨道交通线网给乘客提供多种出行路径选择,而轨道网络起讫点间可能存在多条可选有效路径,给城市轨道客流清分工作带来难度。为求解相同起讫站点间各路线乘客选择的概率问题,以广州市地铁自动售检票(automaticfarecollection,AFC)系统刷卡数据为研究对象,提出一种创新性的半监督聚类算法框架。首先基于广度优先(breadth first search, BFS)的K短路径的搜索算法,识别起讫点间的有效路径集,由此确定初始聚类中心及个数;然后以路径距离和换乘次数等特征值依次标定各有效路径权重,由这些标记数据出发,采用加权半监督的方式增强聚类算法的分类能力。最后结合客流调查结果,与经典K-means算法和朴素贝叶斯分类算法进行比对。通过算例证实提出的客流分配算法性能最优,准确率高达94%,具有较好的分类效果。展开更多
【目的】以路径重复率为优化目标解决农业机器人在数字生态农场中的全区域覆盖问题。【方法】首先,将栅格地图中的障碍物进行膨胀处理,在此基础上进行矩形分区以及分区合并操作;然后,通过改进的蚁群算法规划分区间的遍历顺序、通过改进...【目的】以路径重复率为优化目标解决农业机器人在数字生态农场中的全区域覆盖问题。【方法】首先,将栅格地图中的障碍物进行膨胀处理,在此基础上进行矩形分区以及分区合并操作;然后,通过改进的蚁群算法规划分区间的遍历顺序、通过改进的广度优先搜索(Breadth first search, BFS)算法规划分区间终点与起点的衔接路径,从而实现机器人全区域覆盖。2种算法的具体改进方案为:分别通过人工免疫算法与粒子群算法改进遗传算法的选择与交叉算子,并将改进后的选择算子、交叉算子、原遗传算法变异算子与蚁群算法相结合改进传统蚁群算法信息素更新方法;建立动态函数以简化BFS算法规划的路径。【结果】仿真结果表明,改进蚁群算法收敛时的迭代次数较传统蚁群算法减少了83.1%,路径长度相比减少了4.8%;由改进的蚁群算法与改进的BFS算法规划的机器人遍历路径重复率是传统蚁群算法和BFS算法的56%,且农业机器人能实现对农田区域的100%覆盖。【结论】本研究提供了一种农业机器人在复杂环境的数字生态循环农场中进行全遍历覆盖的解决方案。展开更多
为了解决现有船舶电网保护方法难以达到复杂网络对保护选择性要求的弱势,提出基于广度优先搜索法(Breadth First Search)的开关动作排序法。该方法通过控制开关的延时长短,让上下级开关的时间设定值相互配合,达到保护选择性要求。最后用...为了解决现有船舶电网保护方法难以达到复杂网络对保护选择性要求的弱势,提出基于广度优先搜索法(Breadth First Search)的开关动作排序法。该方法通过控制开关的延时长短,让上下级开关的时间设定值相互配合,达到保护选择性要求。最后用3个实例对比原有方法证明了新方法的优势和有效性。展开更多
The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important...The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important design challenge such as lifetime maximization. Therefore, designing effective routing techniques that conserve scarce energy resources is a critical issue in WSN. Though, the chain-based routing is one of significant routing mechanisms but several common flaws, such as data propagation delay and redundant transmission, are associated with it. In this paper, we will be proposing an energy efficient technique based on graph theory that can be used to find out minimum path based on some defined conditions from a source node to the destination node. Initially, a sensor area is divided into number of levels by a base station based on signal strength. It is important to note that this technique will always found out minimum path and even alternate path are also saved in case of node failure.展开更多
Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effecti...Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.展开更多
In recent years,more and more attention has been paid to the research and application of graph structure.As the most typical representative of graph structure algorithm,breadth first search algorithm is widely used in...In recent years,more and more attention has been paid to the research and application of graph structure.As the most typical representative of graph structure algorithm,breadth first search algorithm is widely used in many fields.However,the performance of traditional serial breadth first search(BFS)algorithm is often very low in specific areas,especially in large-scale graph structure traversal.However,it is very common to deal with large-scale graph structure in scientific research.At the same time,the computing performance of supercomputer has also made great progress.China’s self-developed supercomputer system Sunway TaihuLight(SW)has won the top 500 list for three consecutive times.The huge computing performance of supercomputer is the key to solve this problem.It can be seen that if we use the computing power of supercomputing to solve the problem of large-scale graph structure traversal,the efficiency of graph structure traversal will be greatly improved.This paper expounds how to realize the breadth first search algorithm of graph structure on the Sunway TaihuLight,and achieved some results.In this way,MPI and thread library called athread of SW platform are used,and the traversal performance is improved dozens of times through the above related technologies and some partition methods of graph structure.展开更多
文摘复杂的城市轨道交通线网给乘客提供多种出行路径选择,而轨道网络起讫点间可能存在多条可选有效路径,给城市轨道客流清分工作带来难度。为求解相同起讫站点间各路线乘客选择的概率问题,以广州市地铁自动售检票(automaticfarecollection,AFC)系统刷卡数据为研究对象,提出一种创新性的半监督聚类算法框架。首先基于广度优先(breadth first search, BFS)的K短路径的搜索算法,识别起讫点间的有效路径集,由此确定初始聚类中心及个数;然后以路径距离和换乘次数等特征值依次标定各有效路径权重,由这些标记数据出发,采用加权半监督的方式增强聚类算法的分类能力。最后结合客流调查结果,与经典K-means算法和朴素贝叶斯分类算法进行比对。通过算例证实提出的客流分配算法性能最优,准确率高达94%,具有较好的分类效果。
文摘【目的】以路径重复率为优化目标解决农业机器人在数字生态农场中的全区域覆盖问题。【方法】首先,将栅格地图中的障碍物进行膨胀处理,在此基础上进行矩形分区以及分区合并操作;然后,通过改进的蚁群算法规划分区间的遍历顺序、通过改进的广度优先搜索(Breadth first search, BFS)算法规划分区间终点与起点的衔接路径,从而实现机器人全区域覆盖。2种算法的具体改进方案为:分别通过人工免疫算法与粒子群算法改进遗传算法的选择与交叉算子,并将改进后的选择算子、交叉算子、原遗传算法变异算子与蚁群算法相结合改进传统蚁群算法信息素更新方法;建立动态函数以简化BFS算法规划的路径。【结果】仿真结果表明,改进蚁群算法收敛时的迭代次数较传统蚁群算法减少了83.1%,路径长度相比减少了4.8%;由改进的蚁群算法与改进的BFS算法规划的机器人遍历路径重复率是传统蚁群算法和BFS算法的56%,且农业机器人能实现对农田区域的100%覆盖。【结论】本研究提供了一种农业机器人在复杂环境的数字生态循环农场中进行全遍历覆盖的解决方案。
文摘The wireless sensor networks (WSN) are formed by a large number of sensor nodes working together to provide a specific duty. However, the low energy capacity assigned to each node prompts users to look at an important design challenge such as lifetime maximization. Therefore, designing effective routing techniques that conserve scarce energy resources is a critical issue in WSN. Though, the chain-based routing is one of significant routing mechanisms but several common flaws, such as data propagation delay and redundant transmission, are associated with it. In this paper, we will be proposing an energy efficient technique based on graph theory that can be used to find out minimum path based on some defined conditions from a source node to the destination node. Initially, a sensor area is divided into number of levels by a base station based on signal strength. It is important to note that this technique will always found out minimum path and even alternate path are also saved in case of node failure.
基金Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of ChinaProject supported by the Program for New Century Excellent Talents in University of ChinaProjects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China
文摘Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.
基金This work is sponsored by the Sichuan Science and Technology Program(2020YFS0355 and 2020YFG0479).
文摘In recent years,more and more attention has been paid to the research and application of graph structure.As the most typical representative of graph structure algorithm,breadth first search algorithm is widely used in many fields.However,the performance of traditional serial breadth first search(BFS)algorithm is often very low in specific areas,especially in large-scale graph structure traversal.However,it is very common to deal with large-scale graph structure in scientific research.At the same time,the computing performance of supercomputer has also made great progress.China’s self-developed supercomputer system Sunway TaihuLight(SW)has won the top 500 list for three consecutive times.The huge computing performance of supercomputer is the key to solve this problem.It can be seen that if we use the computing power of supercomputing to solve the problem of large-scale graph structure traversal,the efficiency of graph structure traversal will be greatly improved.This paper expounds how to realize the breadth first search algorithm of graph structure on the Sunway TaihuLight,and achieved some results.In this way,MPI and thread library called athread of SW platform are used,and the traversal performance is improved dozens of times through the above related technologies and some partition methods of graph structure.
