論文の概要: Embeddings and labeling schemes for A*

• arxiv url: http://arxiv.org/abs/2111.10041v1
• Date: Fri, 19 Nov 2021 04:42:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-22 16:33:59.433391
• Title: Embeddings and labeling schemes for A*
• Title（参考訳）: A* の埋め込みとラベリング方式
• Authors: Talya Eden, Piotr Indyk, Haike Xu
• Abstract要約: 特徴に基づく学習機能の研究を形式化し、開始する。 特に,埋め込みと距離ラベリングスキームによって誘導されるノルムについて考察する。 自然な仮定の下では、下界はほぼ最適であることを示す。
• 参考スコア（独自算出の注目度）: 17.622284413028346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function $h(u,t)$ that estimates the shortest distance from any input node $u$ to the destination $t$. Traditionally, heuristics have been handcrafted by domain experts. However, over the last few years, there has been a growing interest in learning heuristic functions. Such learned heuristics estimate the distance between given nodes based on "features" of those nodes. In this paper we formalize and initiate the study of such feature-based heuristics. In particular, we consider heuristics induced by norm embeddings and distance labeling schemes, and provide lower bounds for the tradeoffs between the number of dimensions or bits used to represent each graph node, and the running time of the A* algorithm. We also show that, under natural assumptions, our lower bounds are almost optimal.
• Abstract（参考訳）: A*はグラフ検索と経路探索のための古典的で一般的な方法である。 これは、任意の入力ノード$u$から宛先$t$までの最も短い距離を推定するヒューリスティック関数$h(u,t)$の存在を仮定する。 伝統的に、ヒューリスティックはドメインの専門家によって手作りされている。 しかし、ここ数年で、ヒューリスティックな機能を学ぶことへの関心が高まっている。 このような学習的ヒューリスティックスは、与えられたノード間の距離をこれらのノードの「特徴」に基づいて推定する。 本稿では,このような特徴に基づくヒューリスティックスの研究を形式化・開始する。 特に,ノルム埋め込みと距離ラベリングスキームによって誘導されるヒューリスティックスを考察し,各グラフノードを表すために使用される次元やビットの数と,A*アルゴリズムの実行時間とのトレードオフを低くする。 また、自然仮定の下では、下限はほぼ最適であることも示している。

関連論文リスト

• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  探索の効率を顕著に向上させると考えられる,インスタンス依存のプロキシを学習することを提案する。 私たちが最初に学ぶことを提案するプロキシは、補正係数、すなわち、インスタンスに依存しないコスト・ツー・ゴの見積もりと完璧な見積もりの比率である。 第2のプロキシはパス確率であり、グリッドセルが最も短いパスに横たわっている可能性を示している。
  論文  参考訳（メタデータ） (2022-12-22T14:26:11Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• Graph Neural Network Bandits [89.31889875864599]
  グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。 この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。 グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
  論文  参考訳（メタデータ） (2022-07-13T18:12:36Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。 提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
  論文  参考訳（メタデータ） (2022-05-30T16:22:53Z)
• Learning heuristics for A* [9.701208207491879]
  我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。 我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。 その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
  論文  参考訳（メタデータ） (2022-04-11T10:13:53Z)
• Entropic Optimal Transport in Random Graphs [8.7314407902481]
  グラフ解析において、古典的なタスクはノード間の(グループの)類似性の計算によって構成される。 潜在空間におけるノード群間の距離を連続的に推定することは可能であることを示す。
  論文  参考訳（メタデータ） (2022-01-11T13:52:34Z)
• Neural Contextual Bandits with Deep Representation and Shallow Exploration [105.8099566651448]
  本稿では,深部ReLUニューラルネットワークの最後の隠蔽層を用いて,原特徴ベクトルを変換する新しい学習アルゴリズムを提案する。 既存のニューラルネットワークと比較して、ディープニューラルネットワークの最後の層でのみ探索する必要があるため、我々のアプローチは計算的にはるかに効率的です。
  論文  参考訳（メタデータ） (2020-12-03T09:17:55Z)
• Investigating Extensions to Random Walk Based Graph Embedding [0.3867052484157571]
  ランダムウォークに基づくグラフ埋め込みの新たな拡張を提案する。これは、ウォークから最も頻度の低いノードのパーセンテージを異なるレベルで除去する。 この除去により、我々は遠く離れたノードがノードの近傍に存在することをシミュレートし、従ってそれらの接続を明示的に表現する。 その結果、ランダムウォークベースの手法の拡張(うちを含む)は、予測性能をほんの少しだけ改善することがわかった。
  論文  参考訳（メタデータ） (2020-02-17T21:14:02Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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