The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the verti...
详细信息
The minimum vertex cover problem is a basic combinatorial optimization problem. Given an undirected graph the objective is to determine a subset of the vertices which covers all edges such that the number of the vertices in the subset is minimized. In the paper, based on dijkstra algorithm, an approximation algorithm is obtained for the minimum vertex cover problem. In the process of getting a vertex cover, the maximum value of shortest paths is considered as a standard, and some criteria are defined. The time complex of the algorithm is O(n(3)), where n is the number of vertices in a graph. In the end, an example is given to illustrate the process and the validity of the algorithm. (C) 2016 Published by Elsevier Ltd.
3D Path planning for multi-robot one-target pursuit is an interesting topic. Bioinspired neural network is frequently implemented for path planning of multi-robot, and the bioinspired neural network neural activity va...
详细信息
ISBN:
(纸本)9781728142425
3D Path planning for multi-robot one-target pursuit is an interesting topic. Bioinspired neural network is frequently implemented for path planning of multi-robot, and the bioinspired neural network neural activity value computational cost and time cost will increase sharply with the increase of the number of neurons. This paper explores an improved 3D path planning method based on multi-scale map method to reduce the time cost. Combining the multi-scale map method with the dijkstra algorithm, the optimal paths of 3D coarse-scale map of multi-robot one-target can be generated. The weights created from the coarse-scale map are employed to yield the 3D path planning of the fine-scale map for the same terrain. Therefore, this improved bioinspired neural network algorithm has proven the ability to calculate the multi-robot 3D optimal paths. By introducing this multi-scale map method into the multirobot bioinspired neural network algorithm, the time cost and mathematical complexity of the path planning algorithm can be greatly reduced. MATLAB simulation results further reveal the effectiveness and superiority of this method.
We proposes a novel routing decisions method based on comprehensive trust value to solve the multi-source heterogeneous data routing problem in the smart city. The method combines four parameters-trust value, intensit...
详细信息
In large or medium retail enterprises, the downstream of the supply chain is usually composed by distribution centers or various warehouses. Since the distance of each distribution route is large, so the optimization ...
详细信息
In large or medium retail enterprises, the downstream of the supply chain is usually composed by distribution centers or various warehouses. Since the distance of each distribution route is large, so the optimization of path is very important for the cost control and profit maximization of the enterprise. This paper uses dijkstra algorithm to solve the shortest path problem, and uses the method of map labeling, simplifying the solving process Finally through the abstracting model of the problem, and designing of structure and combining with the process oriented C language, the paper realizes this function.
Aiming at the problem of the shortest path's optimization for direct navigation of ships,the dijkstra algorithm search is *** environment of the ship's navigation area was modeled by rasterization and *** the ...
详细信息
Aiming at the problem of the shortest path's optimization for direct navigation of ships,the dijkstra algorithm search is *** environment of the ship's navigation area was modeled by rasterization and *** the four-direction search,eight-direction search and arbitrary-angle search based on the dijkstra algorithm were improved,and the three search methods were *** experiments and research results show that the improved arbitrary angle search method can best meet the requirement of the shortest direct flight path.
The paper studies motion path planning problem using improved A* searching algorithm, and implements the movement scenario using mobile robot system. Solving the shortest path problem, dijkstra algorithm can finds the...
详细信息
ISBN:
(纸本)9783037856512
The paper studies motion path planning problem using improved A* searching algorithm, and implements the movement scenario using mobile robot system. Solving the shortest path problem, dijkstra algorithm can finds the shortest path to solve the path searching problem. The searching depth is not applicable in certain circumstances to be a disadvantage. The paper proposed improved A* searching algorithm using the intelligent node judgment method, it not only be able to retain the advantages of the traditional A* algorithm but also improve the shortcomings. It programs the on-time motion path in dynamic environment;it also programs the motion path more closed to the best path. Finally, the paper uses multiple strategies to improve the searching motion path to be the best motion path, and compares with the traditional A* algorithm to reduce the searching time.
Recently, autonomous vehicles navigation (AVN) attracted many researches trying to improve road traffic without the human intervention. One of the main challenges in AVN is allowing a vehicle to discover its moving tr...
详细信息
ISBN:
(纸本)9781728171586
Recently, autonomous vehicles navigation (AVN) attracted many researches trying to improve road traffic without the human intervention. One of the main challenges in AVN is allowing a vehicle to discover its moving trajectory with a reduced computational complexity. To cope with this issue, we propose in this paper a new simulated annealing algorithm to discover an optimal trajectory when the vehicle encounters an obstacle using LiDAR perception. The found trajectory is then sent to a roadside unit (RSU), which communicates this discovery to other nodes in the network for further use. During its navigation, the vehicle perceives the environment by a LiDAR sensor to detect an eventual obstacle and launches an optimal path discovery to reach the final destination in a reduced time. The results obtained showed the effectiveness of our proposal to find an optimal route compared to dijkstra algorithm.
There are only two variables including vehicle speed and the length of path in existing search algorithms for minimum-time path. The model does not include weather and road environment which impact the travel time. So...
详细信息
ISBN:
(纸本)9781424441334
There are only two variables including vehicle speed and the length of path in existing search algorithms for minimum-time path. The model does not include weather and road environment which impact the travel time. So the practical application of the model is not satisfactory. Important variables are considered in this paper, such as length of path, road grade, weather and human activities. We put forward the concept of virtual length of the path, and present the solution of the algorithm. Compared with the present search algorithm, the average travel time is saved by 17.73% according to the simulation result, and it improves the practical value in engineering applications.
In this paper, it is studied a blockade problem about suspect escape with using graph theory. A minimum encirclement generation algorithm is proposed to convert this problem into a matching problem. Then the specific ...
详细信息
ISBN:
(纸本)9789881563842
In this paper, it is studied a blockade problem about suspect escape with using graph theory. A minimum encirclement generation algorithm is proposed to convert this problem into a matching problem. Then the specific blockade plan is obtained. As the algorithm is a sort of polynomial time algorithm, it can obtain the global optimum in a relative shorter time compared with other algorithms. A series of evaluation criterion and numerical example are finally simulated to measure the effectiveness of proposed the blockade plan.
In this paper it is propose a routing algorithm using PSO (Particle Swarm Optimization). The PSO outperforms the classical dijkstra algorithm in that PSO could handle multi-objective routing problems while the Dijkstr...
详细信息
ISBN:
(纸本)9781467311762
In this paper it is propose a routing algorithm using PSO (Particle Swarm Optimization). The PSO outperforms the classical dijkstra algorithm in that PSO could handle multi-objective routing problems while the dijkstra cannot. A simulation model was build where PSO is distributed implemented and the optimum route is calculated on each node until destination is reached. This distributed approach gives the proposed algorithm extra avails in that no centralized arbiter is needed. The optimization also considers supporting Quality-of-Service (QoS) to routing in CRNs. It has been shown that algorithm would adapt multi-hop routing according to different QoS requirements, which makes it achievable in future CRNs.
暂无评论