Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
基本信息
- 批准号:RGPIN-2016-06253
- 负责人:
- 金额:$ 2.77万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2016
- 资助国家:加拿大
- 起止时间:2016-01-01 至 2017-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
In many applications arising e.g., in Robotics, GIS, Navigation, Social Networks, and Sensor Networks, environments are dynamic. Objects/entities may move, disappear, appear and even change shape. Traditional shortest path algorithms, designed for static environments, would either not be applicable or require frequent recomputations and thus become inefficient.Most activity for dynamic shortest path problems has been in the area of graph (or hyper-graph). These instances allow for graph edges to be inserted and/or deleted and/or weights to be changed. Fully dynamic algorithms allow edges to be both inserted and deleted; partially dynamic algorithms allow for either insertions or deletions, but not both. Results exist for both fully and partially dynamic algorithms.Building on, and motivated by, previous work, we are interested in dynamic shortest path algorithms for solving geometric problems. For example, objects (obstacles for the shortest path computation) may only exist for a fixed time interval [Ts, Te], i.e., the object appears at time Ts and disappears at time Te. Objects may change shape over time (say grow continuously from a point to larger and larger circles – such problems arise when one wants to model uncertainties). Another interesting class of dynamic shortest paths problems arises in time-dependent graphs or networks, where the costs of edges (that is, edge travel times) vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. We have already studied similarities of polygonal curves measured via the frequently used Fréchet Distance. Similarity problems between polygonal curves arise e.g. in Computer Graphics, Pattern Recognition, Clustering, GIS and structural biology, sports scene analysis, human movement, surveillance, and animal behavior. We discovered and/or improved upon some exciting and natural optimization problems involving the Fréchet Distance. The solution often involved solving particular shortest path problems. To solve several new optimization and parameterization problems using the Fréchet Distance and its variants, we will encounter geometric dynamic shortest path problems. Solutions to these are also of independent interest and will enable us to obtain also solutions to these Fréchet Distance problems.
在许多应用中,例如,在机器人、GIS、导航、社交网络和传感器网络中,环境是动态的。物体/实体可以移动、消失、出现,甚至改变形状。传统的最短路径算法主要是针对静态环境设计的,要么不适用,要么需要频繁的重新计算,效率低下,而动态最短路径问题的研究主要集中在图(或超图)领域。这些实例允许插入和/或删除图形边缘和/或改变权重。完全动态算法允许插入和删除边;部分动态算法允许插入或删除,但不能同时插入和删除。结果存在完全和部分动态算法。建立,并受到启发,以前的工作,我们感兴趣的动态最短路径算法解决几何问题。例如,对象(用于最短路径计算的障碍物)可以仅存在固定的时间间隔[Ts,Te],即,物体在时间Ts出现并在时间Te消失。物体可能会随着时间的推移而改变形状(比如从一个点不断地变成越来越大的圆-当人们想要建模不确定性时,就会出现这样的问题)。另一类有趣的动态最短路径问题出现在时间依赖图或网络中,其中边的成本(即边的旅行时间)作为时间的函数而变化,因此两个节点s和d之间的最短路径可以随时间而变化。我们已经研究了通过常用的Fréchet距离测量的多边形曲线的相似性。多边形曲线之间的相似性问题出现在例如计算机图形学、模式识别、聚类、GIS和结构生物学、运动场景分析、人类运动、监视和动物行为中。我们发现和/或改进了一些涉及Fréchet距离的令人兴奋的自然优化问题。解决方案往往涉及解决特定的最短路径问题。为了使用Fréchet距离及其变体解决几个新的优化和参数化问题,我们将遇到几何动态最短路径问题。解决这些问题也是独立的利益,并将使我们能够获得解决这些弗雷歇距离问题。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Sack, JörgRüdiger其他文献
Sack, JörgRüdiger的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Sack, JörgRüdiger', 18)}}的其他基金
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2019
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2018
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2017
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Algorithms design for motion problems: theory & practice
运动问题的算法设计:理论
- 批准号:
332-2011 - 财政年份:2015
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
New Organization for Canadian Computer Science
加拿大计算机科学新组织
- 批准号:
486477-2015 - 财政年份:2015
- 资助金额:
$ 2.77万 - 项目类别:
Unique Initiatives Fund
Algorithms design for motion problems: theory & practice
运动问题的算法设计:理论
- 批准号:
332-2011 - 财政年份:2014
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Consultation of Canadian Computer Science Community on National Organization
加拿大计算机科学界国家组织咨询
- 批准号:
469472-2014 - 财政年份:2014
- 资助金额:
$ 2.77万 - 项目类别:
Unique Initiatives Fund
Algorithms design for motion problems: theory & practice
运动问题的算法设计:理论
- 批准号:
332-2011 - 财政年份:2013
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Algorithms design for motion problems: theory & practice
运动问题的算法设计:理论
- 批准号:
332-2011 - 财政年份:2012
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Algorithms design for motion problems: theory & practice
运动问题的算法设计:理论
- 批准号:
332-2011 - 财政年份:2011
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
相似海外基金
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2021
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
CCF: AF: Small: Algorithms, Parallelism and Communication Efficiency in Shortest Path Computations
CCF:AF:Small:最短路径计算中的算法、并行性和通信效率
- 批准号:
2008241 - 财政年份:2020
- 资助金额:
$ 2.77万 - 项目类别:
Standard Grant
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2020
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2019
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
A new approach to benchmarking the skills of companies and their employees, which then delivers the shortest and most efficient path to learning and career progression.
一种对公司及其员工的技能进行基准测试的新方法,从而提供最短、最有效的学习和职业发展路径。
- 批准号:
33050 - 财政年份:2019
- 资助金额:
$ 2.77万 - 项目类别:
Collaborative R&D
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2018
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Dynamic Shortest Path Algorithms and their Applications
动态最短路径算法及其应用
- 批准号:
RGPIN-2016-06253 - 财政年份:2017
- 资助金额:
$ 2.77万 - 项目类别:
Discovery Grants Program - Individual
Rectilinear shortest path queries with violations
有违规的直线最短路径查询
- 批准号:
451665-2013 - 财政年份:2013
- 资助金额:
$ 2.77万 - 项目类别:
Canadian Graduate Scholarships Foreign Study Supplements
Experimenting with shortest path algorithms in geometric environments
在几何环境中试验最短路径算法
- 批准号:
417772-2011 - 财政年份:2011
- 资助金额:
$ 2.77万 - 项目类别:
University Undergraduate Student Research Awards
Fast algorithm for large-scale time-dependent shortest path problem
大规模瞬态最短路径问题的快速算法
- 批准号:
23700018 - 财政年份:2011
- 资助金额:
$ 2.77万 - 项目类别:
Grant-in-Aid for Young Scientists (B)