检索结果-内蒙古大学图书馆

1st International Conference on Intelligent Computing, Communication and Convergence (ICCC)

作者： AvadheshPratapSingh DhirendraPratapSingh MANIT Bhoapl Bhopal MP India

K-shortest path algorithm is generalization of the shortest path algorithm. K-shortest path is used in various fields like sequence alignment problem in molecular bioinformatics, robot motion planning, path finding in gene network where speed to calculate paths plays a vital role. Parallel implementation is one of the best ways to fulfill the requirement of these applications. A GPU based parallel algorithm is developed to find k number of shortest path in a positive edge-weighted directed large graph. In calculated shortest path repetition of the vertices is not allowed. Implemented algorithm calculates a k-shortest path between two pair of vertices of a graph with n nodes and m vertices. This approach is based on Yen's algorithm to find k-shortest loopless path. We implemented our algorithms in Nvidia's GPU using Compute Unified Device Architecture (CUDA). This paper presents comparative analysis between CPU and GPU based implementation of Yen's algorithm. Our approach achieves the 6 time speed up in comparison of serial algorithm. (C) 2015 The Authors. Published by Elsevier B.V.

关键词： Compute Unified Device Architecture (CUDA) Graphical Processing Unit (GPU) shortest path algorithm Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Experimental Study of Dynamic Single-Source shortest path algorithm

引用

International Conference on Information Technology for Manufacturing Systems (ITMS 2011)

作者： Xiao Qiancai Li Mingqi Guo Wenqiang Univ Elect Sci & Technol China Sch Math Sci Chengdu 611731 Peoples R China Xinjiang Univ Finance & Econom Sch Comp Sci Engn Urumqi Peoples R China

ISBN: (纸本)9783037851494

In this paper, software met 3.0 is applied to generate topology, which randomly generates dynamic topology nodes. Based on dynamic shortest path algorithms put forward by ***, Xiaobin et al, we analyzed the time efficiency of dynamic and static shortest path algorithms, the different time efficiency inner dynamic shortest path algorithms, and the relationship of time efficiency between topology and dynamic shortest path algorithms. The result shows that Xiaobin algorithm is statistically better than Narvaez algorithm about 20-30 percent. Dynamic algorithms are not always better than static algorithms considering the amount of changed topology. Dynamic and static algorithms are roughly same when the amount of changed topology holds 10 percent. Dynamic algorithms perform better when less than 10 percent, otherwise static algorithms will be better. The time efficiency of dynamic algorithms is related to special topology.

关键词： shortest path algorithm SPT Dynamic shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

Source Recovery of Underdetermined Blind Source Separation Based on Modified shortest path algorithm 2

Source Recovery of Underdetermined Blind Source Separation B...

引用

IEEE 2nd International Conference on Electronic Information and Communication Technology (ICEICT)

作者： Wang, Chuanchuan Zeng, Yonghu Wang, Liandong State Key Lab Complex Electromagnet Environm Effe Luoyang Peoples R China

ISBN: (纸本)9781538692981

shortest path algorithm is a simple algorithm used for source recovery of underdetermined blind source separation (UBSS), but this algorithm is only applicable to the case where the number of sensors is two. However, in most real-life scenarios, the number of sensors is more than two. Then we proposed a smoothing method to improve the shortest path algorithm. The main thought is as follows: assume the number of sensors is m, select two adjacent observed signals to form a combination each time, then m = 1 kinds of combination are generated. As to each combination, recover their source signals by using the traditional shortest path algorithm, and m = 1 groups of recovered source signals are derived, and then average the sum of all the corresponding signal values of m =1 groups. To verify the modified shortest path algorithm, simulations are performed when source signals are sufficiently sparse and insufficiently sparse respectively, and results show that the modified algorithm proposed in this paper is applicable when the number of sensors is two or more. The modified method enriches the tools that can be utilized for underdetermined source signal recovery.

关键词： Source signal recovering Sparsity shortest path algorithm Underdetermined blind source separation

来源：评论

学校读者我要写书评

暂无评论

The Middle of the Specified Node Set of shortest path algorithm 13

The Middle of the Specified Node Set of Shortest Path Algori...

引用

13th IEEE International Conference on Signal Processing (ICSP)

作者： Jia, Jie Pan, Jeng-Shyang Xu, Hua-Rong Harbin Inst Technol IIIRC HITSZ Shenzhen Grad Sch Innovat Informat Ind Res Ctr Shenzhen Peoples R China Fujian Univ Technol Fujian Prov Key Lab Big Data Min & Applicat Fuzhou Fujian Peoples R China Harbin Inst Technol Shenzhen Grad Sch Innovat Informat Ind Res Ctr Shenzhen Peoples R China Xiamen Univ Technol Dept Comp Sci & Technol CST XMUT Xiamen Peoples R China

ISBN: (纸本)9781509013456

the vast majority of researches about the shortest path algorithm, nowadays, focus just on the case starting from the beginning point and ending at the ending point. If additional condition that the shortest path must go through some given nodes of which number is uncertain must be met, then most of the existing classic algorithms are not applicable. A general method based on the Virus Co-Evolutionary Genetic algorithm and greedy algorithm is presented to solve this kind of problem. The time complexity of the algorithm is given by theoretical analysis and the effectiveness of the algorithm is verified by programming calculation. Furthermore, this algorithm in HUAWEI Code Craft 2016 makes 17th score in preliminary to the semi-finals.

关键词： shortest path algorithm VEGA greedy algorithm path planning

来源：评论

学校读者我要写书评

暂无评论

A Design of Intelligent Route Guidance System Based on shortest path algorithm 10

A Design of Intelligent Route Guidance System Based on Short...

引用

IEEE 10 Int Conf on Service Operations and Logistics and Informatics(SOLI)

作者： Zhang, Xipeng Xiong, Gang Xiao, Liang Zhu, Fenghua Yang, Xiongguang Nyberg, Timo R. Tianjin Univ Sch Elect Engn & Automat Tianjin 300072 Peoples R China Chinese Acad Sci Cloud Comp Ctr Dongguan 523000 Peoples R China Chinese Acad Sci Beijing Engn Res Ctr Intelligent Syst & Technol Inst Automat Beijing 100190 Peoples R China Tianjin Ind Dev Area Infrastruct Management Ctr Tianjin 300072 Peoples R China Aalto Univ Dept Ind Engn & Management FI-00076 Aalto Finland

ISBN: (纸本)9781467384803

With the accelerated urbanization and the development of automobile industry, traffic congestion has become serious gradually for many metropolises. Thus, it is an important and extensive method in many countries to use the intelligent transportation systems (ITS) to control traffic and to induce vehicle flows so that road congestion may be mitigated and the traffic may be more efficient. As an important part of intelligent transportation, an intelligent route guidance system (IRGS) not only regulates traffic flow of every crossroads intersections to make full use of insufficient road infrastructure, but also reduces running distance and average waiting time for every driver to reach region traffic balance. This paper explores a design of IRGS and proposes a way to address the task decomposition of traffic guidance and path selection issues. Results from the simulation experiments suggest that IRGS with shortest path algorithm can achieve better network performance and increased traffic control system efficiency. The study provides theory and method guide for the development of real application system.

关键词： Intelligent Route Guidance System dynamic traffic assignment task decomposition shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

path Planning of A Four-Rotor Aircraft Based on shortest path algorithm and Statistical Analysis

Path Planning of A Four-Rotor Aircraft Based on Shortest Pat...

引用

10th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)

作者： Shi, Tianwei Wang, Hong Wang, Fuwang Northeastern Univ Sch Mech Engn & Automat Shenyang 110189 Peoples R China

ISBN: (纸本)9781467352536

Nowadays, the four-rotor aircraft path planning is an important research subject. To control the single four-rotor aircraft, we propose a path pre-planning algorithm and integrate the shortest path algorithm and the statistical analysis method into the algorithm. According to the certainty of path planning, we set the pre-planned paths in the electronic map for 3-d coordinate as trajectories. The aircraft gets the valid data from the three-dimensional coordinate. Then it adjusts the attitude and position in real-time to complete the path planning by using the data. In this paper, the algorithm improves the aircraft control accuracy and stability. We apply the path pre-planning algorithm to the four-rotor aircraft and verify the algorithm with simulations. The results of simulations show the accuracy and feasibility of the algorithm.

关键词： shortest path algorithm statistic analysis path pre-planning algorithm four-rotor aircraft

来源：评论

学校读者我要写书评

暂无评论

Optimal user pairing using the shortest path algorithm 15

Optimal user pairing using the shortest path algorithm

引用

15th IEEE International Conference on Advanced Networks and Telecommunications Systems (IEEE ANTS)

作者： Katta, Kanchana Mishra, Ramesh Ch Deka, Kuntal IIIT Senapati Imphal Manipur India IIT Goa Ponda India

ISBN: (纸本)9781665448932

In Power Domain Non-Orthogonal Multiple Access, user pairing is based on a distance difference between users as well as power allocation. When the distance difference between the users becomes small, the interference caused by users can affect the system performance. Therefore, it is very important to implement an efficient pairing algorithm in NOMA systems to maintain a minimum distance and pair with the shortest path among the users available in the same cell. In this paper, we have proposed the shortest path algorithm for user pairing which separates the strong and weak users in order to promote massive connectivity. This algorithm performs better for the weak users when we compare it to the conventional Hungarian algorithm in terms of user capacity. Further, results show that the proposed method achieves an average BER performance is similar to the Hungarian algorithm-based scheme but with much lower complexity.

关键词： User Pairing Linear Assignment Problem Hungarian algorithm shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient Constrained shortest path algorithm for Traffic Navigation

An Efficient Constrained Shortest Path Algorithm for Traffic...

引用

International Conference on Energy, Environment and Sustainable Development (ICEESD 2011)

作者： Wang, Zonghui Shi, Shusu Yu, Licheng Chen, Wenzhi Zhejiang Univ Coll Comp Sci & Technol Hangzhou 310003 Zhejiang Peoples R China

ISBN: (纸本)9783037852675

FCD-based traffic navigation system is getting more and more attention from countries all over the world. shortest path algorithm is one of the key techniques of a traffic navigation system. Since classical Dijkstra algorithm and heuristic A* algorithm cannot support some constrained conditions in practice, and existing algorithms supporting constraints require the road network to be modified ahead and have low efficiency. The paper studies the model of road network, and analyzes two types of constraints, one-way street and intersection turning prohibitions, then proposes the constrained A* algorithm and gives the Heuristic function. Finally, the paper tests and analyzes the algorithm, and evaluation performance of the prototype system which employs it. The result shows that the algorithm's efficiency is fairly good.

关键词： Constrained A(star) algorithms shortest path algorithm traffic navigation

来源：评论

学校读者我要写书评

暂无评论

A novel single source shortest path algorithm

引用

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY 2009年第6期12卷 671-680页

作者： Rani, R. Uma Sri Sarada Coll Women Autonomous Dept Comp Sci Salem 16 Tamil Nadu India

This paper presents a new algorithm for computing shortest paths in a nearly directed graph G = (V, E). The existing Dijkstra's algorithm finds the shortest distance between given two vertices. This paper proposes a new algorithm which proves to be better than Dijkstra's and Floyd's algorithm in certain cases. The proposed algorithm is a single source shortest path algorithm which finds the shortest path and shortest distance from a single vertex in a graph to all other vertices in the graph.

关键词： shortest path algorithm Dijkstra's Floyd's shortest distance

来源：评论

学校读者我要写书评

暂无评论

Offering a New Bus Route Between Campus and Bus Terminal Using shortest path algorithm 7th

Offering a New Bus Route Between Campus and Bus Terminal Usi...

引用

7th International Conference on Logistics and Supply Chain Management (LSCM)

作者： Ozceylan, Eren Gaziantep Univ Dept Ind Engn TR-27027 Gaziantep Turkey

ISBN: (纸本)9783030897437;9783030897420

More than 50 thousand students are studying at Gaziantep University. Most of these students reside around the campus of Gaziantep University, while their hometown is outside Gaziantep. Therefore, they use the intercity bus station in the southeast of Gaziantep very often. In this paper, it is aimed to detect the shortest route between Gaziantep University campus and Gaziantep intercity bus station. Within the aim of the study, the shortest path (SPP) problem was considered. The purpose of the shortest path algorithm is to find the shortest distance between the start and end points in a road network. In this problem, 11 different municipal bus routes operating on the route starting from Gaziantep University campus and ending point Gaziantep bus stationwere examined and a road network consisting of 46 points was obtained. Then, the distance between each point was calculated with the help of Google Earth and the data was entered to mathematical model developed for the shortest path algorithm. The model was solved by the GAMS 23.1 optimization package and the shortest distance between the two points (10.4 km) was found to be optimal. As a result, a new bus route including 18 destination stops with shorter distances than the existing 11 bus routes has been proposed.

关键词： shortest path algorithm Mathematical modeling Bus route

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：