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

SICE Annual Conference

作者： Yoshitaka Murata Yoshihiro Mitani Ube National College of Technology Ube Japan

There are a lot of studies about shortest path algorithms. They are usually applied to graphs. However, there is little study of maze images by image processing techniques. In this paper, the shortest path algorithms, Dijkstra's and A* search algorithms, have been examined in maze images in terms of a search time. Furthermore, we have proposed a method to apply a thinning technique to maze images in order to solve a maze more quickly.

关键词： Image Processing Techniques Maze Images shortest path algorithms Search Time

来源：评论

学校读者我要写书评

暂无评论

A FAST DISTRIBUTED shortest-path ALGORITHM FOR A CLASS OF HIERARCHICALLY CLUSTERED DATA-NETWORKS

引用

IEEE TRANSACTIONS ON COMPUTERS 1992年第6期41卷 710-724页

作者： ANTONIO, JK HUANG, GM TSAI, WK TEXAS A&M UNIV SYST DEPT ELECT ENGNCOLLEGE STNTX 77843 UNIV CALIF IRVINE DEPT ELECT & COMP ENGNIRVINECA 92717

A new distributed algorithm is presented that can be used to solve the single-destination shortest path (SDSP) problem or the all-pairs shortest path (APSP) problem for a class of clustered data networks. The network graph is assumed to be characterized with a balanced hierarchically clustered (BHC) topology. The BHC topology is introduced in this paper and is shown to be a realistic characterization for a large class of interconnected data networks. For certain types of BHC topologies, the SDSP problem can be solved with computation and communication time complexities of O(log n), assuming one processor is available at each of the n number of nodes. Assuming p processors are available at each node, computation and communication time complexities of O((n/p)log n) and O(n log n) are achievable, respectively, for solving the APSP problem. It is also shown that the algorithm converges in an asynchronous environment. Therefore, some of the difficulties associated with synchronizing the order of events can be avoided in the actual implementation of the proposed algorithm.

关键词： ASYNCHRONOUS COMPUTATION DATA NETWORKS DISTRIBUTED COMPUTATION DYNAMIC PROGRAMMING HIERARCHICAL NETWORK TOPOLOGIES HIERARCHICAL ROUTING algorithms OPTIMAL ROUTING PARALLEL COMPUTATION shortest path algorithms TIME COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

IMPROVEMENTS FOR THE THRESH X2 shortest-path ALGORITHM

引用

OPERATIONS RESEARCH LETTERS 1987年第5期6卷 227-232页

作者： DIVOKY, JJ College of Business The University of Akron Akron OH 44325 USA

The Thresh X2 algorithm has been shown to dominate other shortest path algorithms over a wide variety of conditions. When used on random networks which have exponentially or normally distributed edge weights the perfo... 详细信息

关键词： shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem

引用

APPLIED MATHEMATICS AND COMPUTATION 2015年 265卷 602-618页

作者： Sedeno-Noda, Antonio Alonso-Rodriguez, Sergio Univ La Laguna Dept Matemat Estadist & Invest Operat San Cristobal de La Lagu Santa Cruz De T Spain

We propose an exact method to solve the constrained shortest path (CSP) problem. The new approach takes advantage of the binary partition strategy of a recent K shortest paths (K-SP) algorithm that allows posing numerous additional path constraints in the model without extra difficulty. We adapt and incorporate several pruning strategies from the literature on the CSP problem in this scheme and obtain a robust and scalable algorithm. The method is compared with the current best algorithm to solve the CSP problem and produces significant speedups in a wide range of network configurations. An example is given where the CSP problem is solved in road networks containing a million nodes and arcs. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Constrained shortest paths shortest path algorithms Ranking best solutions

来源：评论

学校读者我要写书评

暂无评论

A simple parallel algorithm for the single-source shortest path problem on planar digraphs

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2000年第9期60卷 1103-1124页

作者： Träff, JL NEC Europe Ltd C&C Res Labs D-53757 St Augustin Germany Univ Patras Inst Comp Technol GR-26500 Patras Greece Univ Patras Dept Comp Engn & Informat GR-26500 Patras Greece Max Planck Inst Informat Saarbrucken Germany Kings Coll London Dept Comp Sci London WC2R 2LS England

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n(2 epsilon) + n(1-epsilon)) log n) time, performing O(n(1+epsilon) log n) work for any 0algorithms. Our algorithm is based on a region decomposition of the input graph and uses a well-known parallel implementation of Dijkstra's algorithm. The logarithmic factor in both the work and the time can be eliminated by plugging in a less practical, sequential planar shortest path algorithm together with an improved parallel implementation of Dijkstra's algorithm. (C) 2000 Academic Press.

关键词： Graphs parallel random access machine model shortest path algorithms algorithms Planar shortest path problem PARALLEL PROCESSING (COMPUTERS) PLUGGING directed graphs Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A shortest path approach to the multiple-vehicle routing problem with split pick-ups

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2006年第4期40卷 265-284页

作者： Lee, CG Epelman, MA White, CC Bozer, YA Univ Toronto Dept Mech & Ind Engn Toronto ON Canada Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA USA

We consider a multiple-vehicle routing problem with split pick-ups (mVRPSP). This problem involves multiple suppliers, a single depot, and a fleet of identical capacity trucks responsible for delivering supplies from the suppliers to the depot. Any supplier may be visited by more than one truck, thus allowing split pick-ups. The problem is to determine, for each truck, which suppliers to visit and the size of loads to pick up so as to minimize the total transportation cost for the fleet, which depends on the number of trucks used and their routes. We develop a fundamentally new model for the mVRPSP, a deterministic dynamic program (DP). Although the most natural DP formulation results in a DP with uncountably-infinite state and action spaces, an optimality-invariance condition we establish leads to an equivalent DP with finite state and action spaces. This DP formulation leads to a new exact algorithm for solving the mVRPSP, based on a shortest path search algorithm, which is conceptually simple and easy to implement. Crown Copyright (c) 2005 Published by Elsevier Ltd. All rights reserved.

关键词： vehicle routing split deliveries/pick-ups dynamic programming shortest path algorithms

来源：评论

学校读者我要写书评

暂无评论

Implementing parallel shortest path for parallel transportation applications

引用

PARALLEL COMPUTING 2001年第12期27卷 1537-1568页

作者： Hribar, MR Taylor, VE Boyce, DE Northwestern Univ ECE Dept Evanston IL 60208 USA Pacific Univ Dept Math Sci Forest Grove OR USA Univ Illinois Dept Civil & mat Engn Chicago IL 60607 USA

shortest path algorithms are required by several transportation applications;furthermore, the shortest path computation in these applications can account for a large percentage of the total execution time. Since these algorithms are very computationally intense, parallel processing can provide the compute power and memory required to solve large problems quickly. Therefore, good parallel shortest algorithms are critical for efficient parallel implementations of transportation applications. The experimental work related to parallel shortest path algorithms has focused on the development of parallel algorithms;however, very little work has been done with analyzing and understanding the performance impact of various implementation issues. In this paper, we conduct a thorough experimental analysis of parallel shortest path algorithms for sparse networks, concentrating on three implementation issues: (1) choice of shortest path algorithm, (2) termination detection and (3) network decomposition. The paper focuses on the choice of shortest path algorithm and network decomposition since the work on termination detection was published previously. We determine that all three issues affect the communication and convergence of the shortest path algorithm. Furthermore, we find that communicating the most information at a time results in the best convergence;this is contrary to most scientific applications where it is optimal to minimize communication. (C) 2001 Published by Elsevier Science B.V.

关键词： parallel transportation applications parallel shortest path network decomposition shortest path algorithms parallel performance traffic equilibrium

来源：评论

学校读者我要写书评

暂无评论

shortest path algorithm for optimal sectioning of hydrocarbon transport pipeline

引用

IFAC-PapersOnLine 2016年第12期49卷 532-537页

作者： Cano-Acosta, A. Fontecha, John Velasco, Nubia Muñoz-Giraldo, Felipe Departament of Chemical Engineering Universidad de los Andes Bogotá Colombia School of Management Universidad de los Andes Bogotá Colombia

Pipeline transportation mode is one of most used modes in oil industries. Transportation of hazardous substances by pipelines involves environmental, social and economic risks since a failure on a pipeline generates a subsequent release of a possible hazardous material. Limiting the amount of the spill volume reduces de losses and in consequence the associated risks; this mitigation is usually achieved by the installation of sectioning valves located along the pipeline. On practice a challenging problem is how much valves and where to locate them in function of the risks presented on each section. In this work, we tackle the valve location problem (VLP) for sectioning. This problem is modeled as a shortest path problem minimizing the maximum volume that could be spilled as well as environmental and social risks. To solve the problem we use the Bellman-Ford's algorithm, assessing the number and location of valves to minimize environmental and social consequences. The approach was tested on a case study for sectioning a pipeline in Colombia. The results show reductions around 75% of the maximum possible spilled volume and the resulting valve configurations effectively cover areas with high vulnerability, guarantying individual risks lower than the acceptable risk on all populated areas and protecting areas of environmental interest. © 2016

关键词： Problem solving Graph theory Hazards Materials handling Petroleum transportation Pipelines Risks Transportation Bellman Ford Hazardous substances Location problems Pipe line transportations Protecting areas shortest path algorithms shortest path problem Social consequences

来源：评论

学校读者我要写书评

暂无评论

Corridor location: the multi-gateway shortest path model

引用

JOURNAL OF GEOGRAPHICAL SYSTEMS 2014年第3期16卷 287-309页

作者： Scaparra, Maria P. Church, Richard L. Medrano, F. Antonio Univ Kent Kent Business Sch Canterbury Kent England Univ Calif Santa Barbara Dept Geog Santa Barbara CA 93106 USA

The problem of corridor location can be found in a number of fields including power transmission, highways, and pipelines. It involves the placement of a corridor or rights-of-way that traverses a landscape starting at an origin and ending at a destination. Since most systems are subject to environmental review, it is important to generate competitive, but different alternatives. This paper addresses the problem of generating efficient, spatially different alternatives to the corridor location problem. We discuss the weaknesses in current models and propose a new approach which is designed to overcome many of these problems. We present an application of this model to a real landscape and compare the results to past work. Overall, the new model called the multi-gateway shortest path problem can generate a wide variety of efficient alignments, which eclipse what could be generated by past work.

关键词： Corridor location shortest path algorithms Alternative generation GIS Spatial optimization

来源：评论

学校读者我要写书评

暂无评论

Parallelization of shortest path Algorithm Using OpenMP and MPI

Parallelization of Shortest Path Algorithm Using OpenMP and ...

引用

International Conference on I-SMAC (IoT in Social, Mobile, Analytics and Cloud) (I-SMAC)

作者： Awari, Rajashri Yeshwantrao Chavan Coll Engn Dept Info Tech Nagpur Maharashtra India

ISBN: (纸本)9781509032433

Graph problem solve by using the standard graph Algorithm. Example isLarge matrix problems, graphs solving problems, equations etc. There is a representation of two algorithms. The algorithm to find all pair shortest path is Floyd War shall algorithm, single source shortest path is Dijkstra'salgorithm. These two algorithm implement in serial formulation. Parallel algorithm is considerably effective for large graph size. By using these algorithm find the shortest distance, such as city to city, routing, networking, social media. Parallel algorithm used for calculating or finding shortest path of graph. With the help of graph algorithm these operations can be done in parallel and reduce the computation time and efficiency. All pair shortest path problem apply for directed and undirected graph whose finite nodes and edges in un-weighted and undirected graph.

关键词： shortest path algorithms OpenMP MPI

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：