論文の概要: A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates
- arxiv url: http://arxiv.org/abs/2208.11489v4
- Date: Tue, 1 Aug 2023 13:42:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-02 18:28:29.692405
- Title: A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates
- Title（参考訳）: 複数のエッジコスト推定を持つグラフに対する最短経路問題の一般化
- Authors: Eyal Weiss, Ariel Felner, Gal A. Kaminka
- Abstract要約: グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
- 参考スコア（独自算出の注目度）: 13.046825574678579
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The shortest path problem in graphs is a cornerstone of AI theory and
applications. Existing algorithms generally ignore edge weight computation
time. We present a generalized framework for weighted directed graphs, where
edge weight can be computed (estimated) multiple times, at increasing accuracy
and run-time expense. This raises several generalized variants of the shortest
path problem. We introduce the problem of finding a path with the tightest
lower-bound on the optimal cost. We then present two complete algorithms for
the generalized problem, and empirically demonstrate their efficacy.
- Abstract（参考訳）: グラフにおける最短経路問題は、AI理論と応用の基礎である。
既存のアルゴリズムは一般にエッジウェイト計算時間を無視する。
本稿では,重み付き有向グラフの一般化フレームワークを提案する。エッジウェイトを複数回計算可能で,精度と実行時間コストが向上する。
これは、最短経路問題のいくつかの一般化された変種を引き起こす。
最適なコストで最短の低バウンドの経路を求める問題を導入する。
次に,一般化問題に対する2つの完全アルゴリズムを提示し,その効果を実証的に示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。