論文の概要: Deep Distance Sensitivity Oracles

• arxiv url: http://arxiv.org/abs/2211.02681v1
• Date: Wed, 2 Nov 2022 05:15:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-13 23:27:47.054708
• Title: Deep Distance Sensitivity Oracles
• Title（参考訳）: 遠距離感度オラクル
• Authors: Davin Jeong, Chau Pham, Arnav Bhakta, Sarel Cohen, Maximilian Katzmann, Tobias Friedrich, Sang Chin
• Abstract要約: 最も基本的なグラフ問題の1つは、ソースからターゲットノードへの最短経路を見つけることである。 この問題を解決する方法の1つは、クエリからの計算負担を前処理のステップに移行することである。 置換経路の構造を深層学習で活用する方法を示す。
• 参考スコア（独自算出の注目度）: 7.64131208028731
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the most fundamental graph problems is finding a shortest path from a source to a target node. While in its basic forms the problem has been studied extensively and efficient algorithms are known, it becomes significantly harder as soon as parts of the graph are susceptible to failure. Although one can recompute a shortest replacement path after every outage, this is rather inefficient both in time and/or storage. One way to overcome this problem is to shift computational burden from the queries into a pre-processing step, where a data structure is computed that allows for fast querying of replacement paths, typically referred to as a Distance Sensitivity Oracle (DSO). While DSOs have been extensively studied in the theoretical computer science community, to the best of our knowledge this is the first work to construct DSOs using deep learning techniques. We show how to use deep learning to utilize a combinatorial structure of replacement paths. More specifically, we utilize the combinatorial structure of replacement paths as a concatenation of shortest paths and use deep learning to find the pivot nodes for stitching shortest paths into replacement paths.
• Abstract（参考訳）: 最も基本的なグラフ問題の1つは、ソースからターゲットノードへの最短経路を見つけることである。 その基本的な形式では、この問題は広く研究され、効率的なアルゴリズムが知られているが、グラフの一部が失敗に遭うと、かなり難しくなる。 停止毎に一番短い置換パスを再計算できるが、これは時間とストレージの両方でかなり非効率である。 この問題を解決する方法の1つは、クエリからの計算負荷を前処理のステップにシフトさせることで、データ構造が計算され、置換パスの高速なクエリを可能にします(一般的には、DSO(Distance Sensitivity Oracle)と呼ばれる)。 dsosは理論計算機科学のコミュニティで広く研究されてきたが、我々の知る限りでは、深層学習技術を用いてdsosを構築する最初の仕事である。 置換経路の組合せ構造を利用するためにディープラーニングを利用する方法を示す。 具体的には、置換経路の組合せ構造を最短経路の結合として利用し、深層学習を用いて最短経路を置換経路に縫合するピボットノードを求める。

関連論文リスト

• Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version) [0.0]
  そこで本研究では,A*の自然進化により,その興味深い性質を全て保ちながら,同時に時間的複雑性をもった新しい探索アルゴリズムを提案する。 様々なテストベッドでの実験では、しばしば1～2桁のオーダーで、芸術の状況よりもパフォーマンスが大幅に向上した。
  論文  参考訳（メタデータ） (2024-08-15T15:54:25Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。 提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
  論文  参考訳（メタデータ） (2022-05-30T16:22:53Z)
• Combining Optimal Path Search With Task-Dependent Learning in a Neural Network [4.1712273169097305]
  コスト値をシナプス重みに変換することにより,経路探索問題のニューラルネットワーク表現を定義することができることを示す。 ネットワーク学習機構は, ネットワーク内の重みを手作業に応じて強化し, ネットワークの重み付けに適応できることを示す。
  論文  参考訳（メタデータ） (2022-01-26T18:29:00Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner with Evolution-Based Optimization [49.207538634692916]
  そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。 提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。 我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
  論文  参考訳（メタデータ） (2021-10-08T07:22:45Z)
• PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms [59.3879573040863]
  パスプランニングは、モバイルロボティクスの重要なコンポーネントです。 アルゴリズムを全体的あるいは統一的にベンチマークする試みはほとんど行われていない。 本稿では,パスプランニングアルゴリズムの開発,視覚化,トレーニング,テスト,ベンチマークを行うプラットフォームであるPathBenchについて述べる。
  論文  参考訳（メタデータ） (2021-05-04T21:48:18Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Shortest path distance approximation using deep learning techniques [0.43461794560295636]
  埋め込みを施したフィードフォワードニューラルネットワークは、比較的低い歪み誤差で距離を近似できることを示す。 提案手法は,Facebook,BlogCatalog,Youtube,Flickrのソーシャルネットワーク上で評価される。
  論文  参考訳（メタデータ） (2020-02-12T21:59:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。