論文の概要: A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates
- arxiv url: http://arxiv.org/abs/2208.11489v1
- Date: Mon, 22 Aug 2022 22:07:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-25 13:23:04.637161
- Title: A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates
- Title（参考訳）: 複数のエッジコスト推定を持つグラフに対する最短経路問題の一般化
- Authors: Eyal Weiss, Gal A. Kaminka
- Abstract要約: グラフにおける最短経路問題は、理論と応用の両方の基盤となっている。
重み付き有向グラフの一般化フレームワークを提案し,複数の推定器を用いて各エッジコストを動的に推定する。
- 参考スコア（独自算出の注目度）: 2.8326418377665346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The shortest path problem in graphs is a cornerstone for both theory and
applications. Existing work accounts for edge weight access time, but generally
ignores edge weight computation time. In this paper we present a generalized
framework for weighted directed graphs, where each edge cost can be dynamically
estimated by multiple estimators, that offer different cost bounds and
run-times. This raises several generalized shortest path problems, that
optimize different aspects of path cost while requiring guarantees on cost
uncertainty, providing a better basis for modeling realistic problems. We
present complete, anytime algorithms for solving these problems, and provide
guarantees on the solution quality.
- Abstract（参考訳）: グラフにおける最短経路問題は理論と応用の両方の基盤である。
既存の作業にはエッジウェイトアクセス時間があるが、一般にエッジウェイト計算時間を無視している。
本稿では,重み付き有向グラフの一般化フレームワークを提案する。各エッジコストを複数の推定器で動的に推定し,コスト境界と実行時間が異なる。
これは、コストの不確実性を保証しながらパスコストの異なる側面を最適化し、現実的な問題をモデル化するためのより良い基礎を提供する。
我々は,これらの問題を解決するための任意の時間アルゴリズムを提示し,ソリューション品質の保証を提供する。
関連論文リスト
- Tightest Admissible Shortest Path [4.928034044959278]
グラフにおける最短経路問題はAIの基本である。
本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。
我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-15T14:39:05Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - Learning to Solve Combinatorial Graph Partitioning Problems via
Efficient Exploration [72.15369769265398]
実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。
最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
論文 参考訳（メタデータ） (2022-05-27T17:13:10Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。
同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
論文 参考訳（メタデータ） (2021-04-14T07:59:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time [12.43303621344215]
専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。
本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。
最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
論文 参考訳（メタデータ） (2020-06-06T01:35:45Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。