This paper describes a topological routing path search algorithm embedded in our rubber-band-based autorouter for single-layer printed circuit boards, The algorithmsearches for a topological path that is guaranteed t...
详细信息
This paper describes a topological routing path search algorithm embedded in our rubber-band-based autorouter for single-layer printed circuit boards, The algorithmsearches for a topological path that is guaranteed to be transformable into a physical wire satisfying design rules. Topological path search algorithms used in existing autorouters verify design rules only locally and approximately. However, it is preferable to satisfy design rules exactly in the global routing phase, especially for routing a densely wired printed circuit board. We propose a method for incrementally verifying design rules during the topological routing pathsearch and describe several improvements to the algorithm that reduce the overhead of the routability test and suppress combinatorial explosion. We also discuss the practical feasibility of the proposed algorithm on the basis of the results of experiments using several printed circuit boards.
Net by net routing is still a very important technique used to make connections in VLSI circuits. The maze routing algorithms used for this purpose correspond to shortest pathsearches derived from basic BFS or from A...
详细信息
ISBN:
(纸本)9780769508436
Net by net routing is still a very important technique used to make connections in VLSI circuits. The maze routing algorithms used for this purpose correspond to shortest pathsearches derived from basic BFS or from A*, with many dedicated improvements. This paper proposes the use of a new path search algorithm, LCS*, for routing individual connections in VLSI circuits. LCS* is a generic and simultaneous bidirectional heuristic algorithm which is faster than A* in most graph domains, such as VLSI routing grids. This is achieved by using dynamic estimation with the separation of computed values for open and closed nodes. Results show that the running time is reduced and little storage space is needed.
作者：
Huang, KeCai, MingXiao, YaoSun Yat sen Univ
Sch Intelligent Syst Engn Guangdong Prov Key Lab Intelligent Transportat Sys Shenzhen Campus Shenzhen 518107 Peoples R China
Intelligence has emerged as an integral trend within Intelligent Transportation Systems (ITS), making the comprehension of interrelations among its key elements critical for unveiling potential influence mechanisms. T...
详细信息
Intelligence has emerged as an integral trend within Intelligent Transportation Systems (ITS), making the comprehension of interrelations among its key elements critical for unveiling potential influence mechanisms. To foster research in this domain, we present an innovative method aimed at unearthing explainable correlations among these pivotal ITS elements. Our approach is underpinned by two primary stages: the construction of a knowledge graph drawn from ITS-related patents, followed by the application of an enhanced breadth-first path calculation algorithm. This novel algorithm carefully balances consideration between element correlations and the structural nuances of the knowledge graph. To verify the robustness of our algorithm, we engage in meticulous node similarity calculations and undertake an assessment of its effectiveness using an array of performance indicators. Furthermore, to provide practical insight, we offer two case studies exploring the correlation among elements within the realms of Vehicle-to-Everything (V2X) communication system and smart logistics center. These case studies not only validate the method's effectiveness but also illustrate its broad applicability. Our method's utility extends beyond merely unraveling evolution mechanisms and forecasting development trends within transportation systems, and it has the potential to significantly contribute to correlation research across a broad spectrum of fields.
Many web-sites provide a variety of electronic mapping services. Currently, many studies are underway to develop vehicle navigation software for PDA maps using GPS data. Popular among these services is one that comput...
详细信息
Many web-sites provide a variety of electronic mapping services. Currently, many studies are underway to develop vehicle navigation software for PDA maps using GPS data. Popular among these services is one that computes the optimal route between two locations input by a user. This service of computing the optimal route plays an important role in vehicular navigation and distribution and delivery industries. The calculation and manipulation of the optimal route for navigation and vehicular delivery system improve the efficiency of vehicle use and delivery times, thereby reducing costs. The purpose of this study is to compute the optimal route by considering the direction of distribution vehicles and the delivery location and develop a genetic based algorithm that quickly generates the shortest route for delivery. The algorithm also generates the optimal route for itineraries having several destinations. (C) 2012 Elsevier B. V. All rights reserved.
The goal of rescue robotics is to extend the capabilities and to increase the safety of human rescue teams. During a rescue mission a mobile robot is deployed on a rescue site and is operated from a safe place by a hu...
详细信息
ISBN:
(纸本)9781424466757
The goal of rescue robotics is to extend the capabilities and to increase the safety of human rescue teams. During a rescue mission a mobile robot is deployed on a rescue site and is operated from a safe place by a human operator. The operator can not see the robot and the environment and a decision on the path selection is very complicated. Our goal is to provide a kind of automatic "pilot system" to propose an operator a good direction or several options to traverse the environment, taking into an account the robot's static and dynamic properties. To find a good path we need a special path search algorithm on debris and a proper definition of a search tree, which can ensure smooth exploration. While the main goal of the algorithm is to keep the robot maximally stable at every step of its path, in some cases we need the robot to lose its balance and to change a 3D orientation discontinuously. Losing balance on purpose is an important feature for safe climbing up and going down the debris and it is the central issue of this paper. Exhaustive simulations were used to structure and analyze data and experiments were used to verify our approach to removing unsuitable directions of the search from the search tree.
The shortest path problem, one of classic topic in the field of Graph Theory and pathsearch, majors in the method about how to find the shortest path between two nodes in a directed-graph. Based on observing the rela...
详细信息
ISBN:
(纸本)9781467376440
The shortest path problem, one of classic topic in the field of Graph Theory and pathsearch, majors in the method about how to find the shortest path between two nodes in a directed-graph. Based on observing the relationship between water flow rate and pipe diameter in a pipeline network, the paper puts forward a kind of multi-thread parallel path search algorithm deriving of Hydrokinetics, namely Water flow searchalgorithm, WFS. Besides, the author has designed a multi-thread program to conduct test. It has been proved that WFS is of great feasibility and applicability to deal with the shortest path problem.
The frequent occurrence of financial fraud caused by listed companies has seriously hindered the healthy development of the capital market. Existing studies usually analyze financial fraud through the effectiveness of...
详细信息
The frequent occurrence of financial fraud caused by listed companies has seriously hindered the healthy development of the capital market. Existing studies usually analyze financial fraud through the effectiveness of audit opinion or the correlation between auditor change rate and financial fraud, ignoring the relationship between different participants. By using the audit relationships among corporations, audit firms and auditors, this paper constructs an audit information knowledge graph and proposes a knowledge graph reasoning framework based on the Sub Feature Extraction method to detect potential fraud corporations. In the process of analyzing the audit data of 376 companies in the China Growth Enterprises Market from 2013 to 2019, it is found that potential fraud corporations can be well identified by searching from the known fraud corporations using searched paths. In addition, we find two new audit features of financial fraud corporations which are respectively related to abnormal audit opinions issued by auditors and abnormal associations of audit firms. They can help regulators more effectively find the potential financial fraud corporations that need to be supervised. (C) 2021 The Authors. Published by Elsevier B.V.
A theoretically most efficient searchalgorithm is presented which uses an exhaustive search to find all of the elementary circuits of a graph. The algorithm can be easily modified to find all of the elementary circui...
详细信息
Nowadays modern cities develop in a very rapid speed. Buildings become larger than ever and the interior structures of the buildings are even more complex. This drives a high demand for precise and accurate indoor nav...
详细信息
Nowadays modern cities develop in a very rapid speed. Buildings become larger than ever and the interior structures of the buildings are even more complex. This drives a high demand for precise and accurate indoor navigation systems. Although the existing commercially available 2D indoor navigation system can help users quickly find the best path to their destination, it does not intuitively guide users to their destination. In contrast, an indoor navigation system combined with augmented reality technology can efficiently guide the user to the destination in real time. Such practical applications still have various problems like position accuracy, position drift, and calculation delay, which causes errors in the navigation route and result in navigation failure. During the navigation process, the large computation load and frequent correction of the displayed paths can be a huge burden for the terminal device. Therefore, the navigation algorithm and navigation logic need to be improved in the practical applications. This paper proposes an improved navigation algorithm and navigation logic to solve the problems, creating a more accurate and effective augmented reality indoor navigation system.
暂无评论