Considering the travel time and transfer frequency, transit passengers will choose to walk between two bus stops within an acceptable distance, which was rarely discussed by previous research on transit shortestpath ...
详细信息
ISBN:
(纸本)9781510600294
Considering the travel time and transfer frequency, transit passengers will choose to walk between two bus stops within an acceptable distance, which was rarely discussed by previous research on transit shortestpath problem. This paper proposes a practical shortest path algorithm taking walking behavior into consideration. The algorithm can describe passengers' behavior when they select travel routes. The feasibility and efficiency of this algorithm has also been preliminarily tested through an example by comparing with the existing shortest path algorithms.
A numerical method consisting of an off-line part and an on-line part for optimal control problems is proposed in this paper. In the off-line part, the state space is discretized into a Cartesian grid structure and th...
详细信息
A numerical method consisting of an off-line part and an on-line part for optimal control problems is proposed in this paper. In the off-line part, the state space is discretized into a Cartesian grid structure and then define a graph over all grid points by connecting two points if the Euclidean norm between them is closer than a positive number called adjacent radius, the minimum cost between them is estimated using difference method and stored in a matrix. After that the matrix is updated by a shortest path algorithm and a matrix holding the information of the shortestpaths between any two grid points is generated. In the on-line part, the optimal control vector at each time step can be generated by reading data from the matrix according to the current state and target state and doing some simple calculations. Since there is no need to do a lot of calculation in the on-line part, this method can satisfy the real-time requirements in some engineering control problems. We prove that the solution of the proposed method converge to the analytical solution when the adjacent radius and the grid size tend to zero and the grid size tend is a higher order infinitesimal of the adjacent radius. At the end of this paper, some numerical examples are taken to illustrate the effectiveness of the proposed method.
Breast cancer, the most prevalent cancer in women, develops from breast tissue. Its incidence has increased in recent years due to environmental risk factors. Thus, it is urgent to uncover the mechanism underlying bre...
详细信息
Breast cancer, the most prevalent cancer in women, develops from breast tissue. Its incidence has increased in recent years due to environmental risk factors. Thus, it is urgent to uncover the mechanism underlying breast cancer to design effective treatments. Identification of all breast cancer-related genes is one way to help elucidate the underlying breast cancer mechanism. In this study, a computational method was built and applied to discover new candidate breast cancer-related genes. Based on the known breast cancer-related genes retrieved from public databases, the shortest path algorithm was applied to discover new candidate genes in the protein-protein interaction network. The analysis results of the selected genes suggest that some of them are deemed breast cancer-related genes according to the most recent published literature, while others have direct or indirect associations with the initiation and development of breast cancer.
Segmenting common objects that have variations in color, texture and shape is a challenging problem. In this paper, we propose a new model that efficiently segments common objects from multiple images. We first segmen...
详细信息
Segmenting common objects that have variations in color, texture and shape is a challenging problem. In this paper, we propose a new model that efficiently segments common objects from multiple images. We first segment each original image into a number of local regions. Then, we construct a digraph based on local region similarities and saliency maps. Finally, we formulate the co-segmentation problem as the shortestpath problem, and we use the dynamic programming method to solve the problem. The experimental results demonstrate that the proposed model can efficiently segment the common objects from a group of images with generally lower error rate than many existing and conventional co-segmentation methods.
Hershberger and Suri proposed an extremely simple approximation scheme for computing shortestpaths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two po...
详细信息
Hershberger and Suri proposed an extremely simple approximation scheme for computing shortestpaths on the surface of a convex polytope in three dimensions in 1998. Given a convex polytope P with n vertices and two points p, q on irs surface, let d(p)(p, q) denote the shortestpath distance between p and q on the surface of P. Their algorithm, shortestpath, produces a path of length at most 2d(p)(p, q) in time O(n). This algorithm is revised, and achieves a ratio of 1.786.
Tumor metastasis is defined as the spread of tumor cells from one organ or part to another that is not directly connected to it, which significantly contributes to the progression and aggravation of tumorigenesis. Bec...
详细信息
Tumor metastasis is defined as the spread of tumor cells from one organ or part to another that is not directly connected to it, which significantly contributes to the progression and aggravation of tumorigenesis. Because it always involves multiple organs, the metastatic process is difficult to study in its entirety. Complete identification of the genes related to this process is an alternative way to study metastasis. In this study, we developed a computational method to identify such genes. To test our method, we selected breast cancer bone metastasis. A large network was constructed using human protein-protein interactions. On the basis of the validated genes related to breast and bone cancer, a shortest path algorithm was applied to the network to search for novel genes that may mediate breast cancer metastasis to bone. In addition, further rules constructed using the permutation FDR, the betweenness ratio, and the maxmin interaction score were also employed in the method to make the inferred genes more reliable. Eighteen putative genes were identified by the method and were extensively analyzed. The confirmation results indicate that these genes participate in metastasis.
Background: Hepatitis is a type of infectious disease that induces inflammation of the liver without pinpointing a particular pathogen or pathogenesis. Type C hepatitis, as a type of hepatitis, has been reported to in...
详细信息
Background: Hepatitis is a type of infectious disease that induces inflammation of the liver without pinpointing a particular pathogen or pathogenesis. Type C hepatitis, as a type of hepatitis, has been reported to induce cirrhosis and hepatocellular carcinoma within a very short amount of time. It is a great threat to human health. Some studies have revealed that trace elements are associated with infection with and immune rejection against hepatitis C virus (HCV). However, the mechanism underlying this phenomenon is still unclear. Methods: In this study, we aimed to expand our knowledge of this phenomenon by designing a computational method to identify genes that may be related to both HCV and trace element metabolic processes. The searching procedure included three stages. First, a shortest path algorithm was applied to a large network, constructed by protein-protein interactions, to identify potential genes of interest. Second, a permutation test was executed to exclude false discoveries. Finally, some rules based on the betweenness and associations between candidate genes and HCV and trace elements were built to select core genes among the remaining genes. Results: 12 lists of genes, corresponding to 12 types of trace elements, were obtained. These genes are deemed to be associated with HCV infection and trace elements metabolism. Conclusions: The analyses indicate that some genes may be related to both HCV and trace element metabolic processes, further confirming the associations between HCV and trace elements. The method was further tested on another set of HCV genes, the results indicate that this method is quite robustness. General significance: The newly found genes may partially reveal unknown mechanisms between HCV infection and trace element metabolism. This article is part of a Special Issue entitled "System Genetics" (C) 2016 Elsevier B.V. All rights reserved.
This paper presents development and implementation of a unique shortest path algorithm for navigation of mobile robot in a dynamic environment. A grid of passive RFID (Radio Frequency Identification) tags is utilized ...
详细信息
ISBN:
(纸本)9781728107295
This paper presents development and implementation of a unique shortest path algorithm for navigation of mobile robot in a dynamic environment. A grid of passive RFID (Radio Frequency Identification) tags is utilized for the localization of swarm robots in the warehouse. The RFID tags, the mobile robots and the remote Control unit are the key components for the MRWA algorithm. On the desire of the robots are able to move objects in parallel from one place of the warehouse to another in an efficient and effective manner. Control unit controls the movement of all robots and navigate the selected robot to the desired location using shortestpath MRWA algorithm. The algorithm also takes consideration of obstacles placed in the path, avoiding the collision of The validity of the design was also tested and verified by practical implementation of a 5x5 gird in an experimental lab environment.
作者：
Lu, FengLai, Poh-ChinChinese Acad Sci
Inst Geog Sci & Nat Resources Res State Key Lab Resources & Environm Informat Syst Beijing 100101 Peoples R China Univ Hong Kong
Dept Geog Hong Kong Hong Kong Peoples R China
Dijkstra's algorithm is arguably the most popular computational solution to finding single source shortestpaths. Increasing complexity of road networks, however, has posed serious performance challenge. While heu...
详细信息
ISBN:
(纸本)3540341668
Dijkstra's algorithm is arguably the most popular computational solution to finding single source shortestpaths. Increasing complexity of road networks, however, has posed serious performance challenge. While heuristic procedures based on geometric constructs of the networks would appear to improve performance, the fallacy of depreciated accuracy has been an obstacle to the wider application of heuristics in the search for shortestpaths. The authors presented a shortest path algorithm that employs limited search heuristics guided by spatial arrangement of networks. The algorithm was tested for its efficiency and accuracy in finding one-to-one and one-to-all shortestpaths among systematically sampled nodes on a selection of real-world networks of various complexity and connectivity. Our algorithm was shown to outperform other theoretically optimal solutions to the shortestpath problem and with only little accuracy lost. More importantly, the confidence and accuracy levels were both controllable and predictable.
This paper deals with Dijkstra's shortest path algorithm and with the possibilities of speeding-up this algorithm. This algorithm is a breadth-first-search algorithm. The search spreads circularly around the sourc...
详细信息
ISBN:
(纸本)9781607506881;9781607506874
This paper deals with Dijkstra's shortest path algorithm and with the possibilities of speeding-up this algorithm. This algorithm is a breadth-first-search algorithm. The search spreads circularly around the source node in order to find the shortestpath from the source node to other nodes. Each following iteration is based on the results of the previous iteration, therefore parallelization of such an algorithm is complicated. The parallel Dijkstra algorithm, proposed in this paper, is based on the bidirectional Dijkstra algorithm and popular multicore technology. Such a technology enables to create a parallel algorithm based on the shared memory and most of the time for data synchronization thereby is saved. The proposed algorithm has been tested using the real road network data. The proposed parallel algorithm is almost 3 times faster than the standard Dijkstra algorithm.
暂无评论