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

Solving the shortest path Problem with QAOA

SPIN 2023年第1期13卷

作者： Fan, Zhiqiang Xu, Jinchen Shu, Guoqiang Ding, Xiaodong Lian, Hang Shan, Zheng Univ Zhengzhou State Key Lab Math Engn Zhengzhou 450000 Henan Peoples R China Univ Zhengzhou Adv Comp Informat Engn Zhengzhou 450000 Henan Peoples R China Songshan Lab Zhengzhou 450000 Henan Peoples R China

Graph computation is a core technique for solving realistic problems of graph representations. In solving the shortest path problem (SPP), the current classical methods are encountering a huge performance bottleneck. Attempting to solve this dilemma, we try to solve the SPP with a Quantum Approximate Optimal algorithm (QAOA)-based quantum method. In this paper, we propose a QAOA-based shortest path algorithm (SPA) by constructing a suitable Hamiltonian quantity and using the idea of variational quantum computing, and verify the algorithm using a quantum simulator and an International Business Machines cloud quantum computer. The proposed algorithm is able to achieve a near-optimal solution with a correct rate that significantly exceeds the invalid solutions, reaching a good preliminary result. Furthermore, the proposed algorithm is expected to achieve a huge advantage over the classical algorithm and the SPA based on Grover's algorithm with a suitable selection of parameters and number of steps. In addition, the proposed algorithm requires fewer quantum bits than other quantum algorithms, thus promising quantum computing superiority on current noisy intermediate-scale quantum (NISQ) quantum computing devices.

关键词： Quantum computation graph theory quantum computing application QAOA shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

A Method of shortest path Raytracing with Dynamic Networks

引用

Chinese Journal of Geophysics 2013年第5期47卷 1013-1018页

作者： Jian-Zhong Zhang Shi-Jun Chen Chu-Wei Xu Department of Communications Engineering Xiamen University Xiamen 361005 China Geophysical Research Institute of Shengli Oilfield Dongying 257022 China

The shortest path raytracing algorithm in networks has been widely applied to calculate seismic ray paths and traveltimes, in which the beelines between network nodes are used to approximate the ray paths. When using a few nodes the ray usually follows a zigzag path that is longer than the real raypath, and the calculated traveltime at a receiver is also larger than the real one. To solve this problem, we develop a shortest path raytracing method with dynamic networks based on the shortest path algorithm. In the process of expanding wavefront away from a source throughout the entire model, the wavefront times are sampled at all nodes on the cell edges. In each cell the traveltime at any point on an edge is expressed with linear interpolation between calculated traveltimes at adjacent nodes on the same cell edge, and then Fermat's Principle is used to determine the first arrival times at the nodes on the other edges of this cell. After the first arrival times at all nodes are calculated, trace raypath from a receiver to a source in the same way as the forward sampling for all pairs of receivers and sources is performed. So the drawbacks of conventional shortest path raytracing methods are overcome, and the precision of calculated minimal traveltimes and the correspondent raypaths are improved greatly.

关键词： shortest path algorithm Dynamic network Wavefront Ray paths

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm to determine all shortest paths in Sierpinski graphs

引用

DISCRETE APPLIED MATHEMATICS 2014年 177卷 111-120页

作者： Hinz, Andreas M. auf der Heide, Caroline Holz Ludwig Maximilians Univ Munchen Fac Math Comp Sci & Stat Munich Germany Univ Maribor Fac Nat Sci & Math Maribor Slovenia

In the Switching Tower of Hanoi interpretation of Sierpinski graphs S-p(n) the P2 decision problem is to find out whether the largest moving disc has to be transferred once or twice in a shortest path between two given states/vertices. We construct an essentially optimal algorithm thus extending Romik's approach for p = 3 to the general case. The algorithm makes use of three automata and the underlying theory includes a simple argument for the fact that there are at most two shortest paths between any two vertices. The total number of pairs leading to non-unique solutions is determined and employing a Markov chain argument it is shown that the number of input pairs needed for the decision is bounded above by a number independent of n. Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented. (C) 2014 Elsevier B.V. All rights reserved.

关键词： shortest path algorithm Automata Sierpinski graphs Switching Tower of Hanoi

来源：评论

学校读者我要写书评

暂无评论

Solving shortest paths efficiently on nearly acyclic directed graphs

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期370卷 94-109页

作者： Saunders, Shane Takaoka, Tadao Univ Canterbury Dept Comp Sci & Software Engn Christchurch 1 New Zealand

shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O (mn) worst-case time, which allowed it to be integrated as part of an O (mn + nr log r) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dontinator set injust O (m) time. This can be integrated as part of the O (m + r log r) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O (m) time and included as part of the O (m + r log r) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O (mn + nr(2)) to O (mn + r(3)). (c) 2006 Elsevier B.V. All rights reserved.

关键词： shortest path algorithm nearly acyclic graph graph decomposition

来源：评论

学校读者我要写书评

暂无评论

Analysis of Security Vulnerability Levels of In-Vehicle Network Topologies Applying Graph Representations

引用

JOURNAL OF ELECTRONIC TESTING-THEORY AND APPLICATIONS 2021年第5-6期37卷 613-621页

作者： Petho, Zsombor Khan, Intiyaz Torok, Arpad Budapest Univ Technol & Econ Dept Automot Technol Budapest Hungary

This article investigates cybersecurity issues related to in-vehicle communication networks. In-vehicle communication network security is evaluated based on the protection characteristics of the network components and the topology of the network. The automotive communication network topologies are represented as undirected weighted graphs, and their vulnerability is estimated based on the specific characteristics of the generated graph. Thirteen different vehicle models have been investigated to compare the vulnerability levels of the in-vehicle network using the Dijkstra's shortest route algorithm. An important advantage of the proposed method is that it is in accordance with the most relevant security evaluation models. On the other hand, the newly introduced approach considers the Secure-by-Design concept principles.

关键词： In-vehicle network shortest path algorithm Vulnerability Security analysis

来源：评论

学校读者我要写书评

暂无评论

Fully Automated Colon Segmentation for the Computation of Complete Colon Centerline in Virtual Colonoscopy

引用

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING 2012年第4期59卷 996-1004页

作者： Lu, Lin Zhang, Danfeng Li, Lei Zhao, Jun Shanghai Jiao Tong Univ Dept Biomed Engn Shanghai 200240 Peoples R China

Virtual colonoscopy detects polyps by navigating along a colon centerline. Complete colon segmentation based on computed tomography (CT) data is a prerequisite to the computation of complete colon centerline. There are two main problems impeding complete segmentation: overdistention/underdistention of colon and the use of oral contrast agents. Overdistention produces loops in the segmented colon, while underdistention may cause the segmented colon collapse into a series of disconnected segments. Use of oral contrast agents, which have high attenuation on CT, may add redundant structures (bones and small bowels) to the segmented colon. A fully automated colon segmentation method is proposed in this paper to address the two problems. We tested the proposed method in 170 cases, including 37 "moderate" and 133 "challenging" cases. Computer-generated centerlines were compared with human-generated centerlines (plotted by three radiologists). The proposed method achieved a 90.56% correct coverage rate with respect to the human-generated centerlines. We also compared the proposed method with two existing colon segmentation methods: Uitert's method and Nappi's method. The results of these two methods were 75.16% and 72.59% correct coverage rates, respectively. Our experimental results indicate that the proposed method could yield more complete colon centerlines than the existing methods.

关键词： Complete colon centerline geodesic distance map (GDM) shortest path algorithm virtual colonoscopy (VC)

来源：评论

学校读者我要写书评

暂无评论

Comparative Assessment of Intervehicular Communication algorithms for Real-Time Traffic Route Guidance

引用

JOURNAL OF INTELLIGENT TRANSPORTATION SYSTEMS 2009年第4期13卷 199-217页

作者： Hawas, Yaser E. Napenas, Marc Joseph B. Hamdouch, Younes UAE Univ Dept Civil & Environm Engn Al Ain U Arab Emirates UAE Univ RTTSRC Al Ain U Arab Emirates UAE Univ Coll Business & Econ Al Ain U Arab Emirates

This article presents two algorithms for intervehicular communication (IVC)-based route guidance in a traffic network. The first algorithm enables communication between a searcher vehicle and other vehicles traveling the network in the opposite direction of the searcher vehicle. The second algorithm enables sharing information among the searcher vehicle and other vehicles traveling in the same direction and within a specific communication range. The mathematical formulations of the two algorithms are presented. A microscopic simulation model is utilized to assess the effectiveness of these algorithms against the well-known shortest path algorithm. Travel time and network productivity are used as the measures of performance. The overall network performance is captured under various congestion levels and link speeds and lengths. Two distinct methods are used in assessment: free simulation runs to evaluate the network productivity under various communication schemes and forced simulation runs to estimate the network travel while fixing the network productivity under various communication schemes.

关键词： Intervehicular Communication Real-time Route Guidance algorithms Mathematical Formulations Microscopic Simulation shortest path algorithm Network Performance

来源：评论

学校读者我要写书评

暂无评论

Considering displacement modes in the fleet management problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2005年第6期43卷 1171-1184页

作者： Bigras, LP Gamache, M Ecole Polytech Montreal Dept Genies Civil Geol & Mines Montreal PQ H3C 3A7 Canada

This paper presents two solution approaches for taking into account the displacement mode ( forward or in reverse) of vehicles during the solution of the shortest path problem. In the first approach, a graph including all aspects of the problem is constructed and a classical shortest path algorithm is used to solve the problem. In the second approach, a more simple graph is constructed, and all the constraints of the problem are considered during the solution of the shortest path problem. This problem is important for routing a fleet of automated vehicles on a one-lane bidirectional graph.

关键词： fleet management routing graph design shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

Novel efficient two-pass algorithm for closed polygonal approximation based on LISE and curvature constraint criteria

引用

JOURNAL OF VISUAL COMMUNICATION AND IMAGE REPRESENTATION 2008年第4期19卷 219-230页

作者： Chung, Kuo-Liang Liao, Po-Hsuan Chang, Jia-Ming Natl Taiwan Univ Sci & Technol Dept Comp Sci & Informat Engn Taipei 10672 Taiwan

Given a closed curve with n points, based on the local integral square error and the curvature constraint criteria, this paper presents a novel two-pass O(Fn + mn(2))-time algorithm for solving the closed polygonal approximation problem where m(<< n) denotes the minimal number of covering feasible segments for one point and empirically the value of m is rather small, and F (<< n(2)) denotes the number of feasible approximate segments. Based on some real closed curves, experimental results demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality and execution-time performance when compared to the previous algorithm by Chung et al. Experimental results also demonstrate that under the same number of segments used, our proposed two-pass algorithm has better quality, but has some execution-time degradation when compared to the currently published algorithms by Wu and Sarfraz et al. (c) 2008 Elsevier Inc. All rights reserved.

关键词： algorithm closed curve closed polygonal approximation algorithm curvature local integral square error shortest path algorithm

来源：评论

学校读者我要写书评

暂无评论

Crowd simulation for emergency response using BDI agents based on immersive virtual reality

引用

SIMULATION MODELLING PRACTICE AND THEORY 2008年第9期16卷 1415-1429页

作者： Shendarkar, Ameya Vasudevan, Karthik Lee, Seungho Son, Young-Jun Univ Arizona Tucson AZ 85721 USA

This paper presents a novel methodology involving a Virtual Reality (VR)-based Belief, Desire, and Intention (BDI) software agent to construct crowd simulation and demonstrates the use of the same for crowd evacuation management under terrorist bomb attacks in public areas. The proposed BDI agent framework allows modeling of human behavior with a high degree of fidelity. The realistic attributes that govern the BDI characteristics of the agent are reverse-engineered by conducting human-in-the-loop experiments in the VR-based Cave Automatic Virtual Environment (CAVE). To enhance generality and interoperability of the proposed crowd simulation modeling scheme, input data models have been developed to define environment attributes (e.g., maps, demographics, evacuation management parameters). The validity of the proposed data models are tested with two different evacuation scenarios. Finally, experiments are conducted to demonstrate the effect of various crowd evacuation management parameters on the key performance indicators in the evacuation scenario Such as crowd evacuation rate and densities. The results reveal that constructed simulation can be used as an effective emergency management tool. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Agent-based simulation CAVE shortest path algorithm Crowd simulation Emergency response management

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：