論文の概要: Learning heuristics for A*

• arxiv url: http://arxiv.org/abs/2204.08938v1
• Date: Mon, 11 Apr 2022 10:13:53 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-24 15:48:06.187858
• Title: Learning heuristics for A*
• Title（参考訳）: a*の学習ヒューリスティック
• Authors: Danilo Numeroso, Davide Bacciu, Petar Veli\v{c}kovi\'c
• Abstract要約: 我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。 我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。 その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
• 参考スコア（独自算出の注目度）: 9.701208207491879
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Path finding in graphs is one of the most studied classes of problems in computer science. In this context, search algorithms are often extended with heuristics for a more efficient search of target nodes. In this work we combine recent advancements in Neural Algorithmic Reasoning to learn efficient heuristic functions for path finding problems on graphs. At training time, we exploit multi-task learning to learn jointly the Dijkstra's algorithm and a consistent heuristic function for the A* search algorithm. At inference time, we plug our learnt heuristics into the A* algorithm. Results show that running A* over the learnt heuristics value can greatly speed up target node searching compared to Dijkstra, while still finding minimal-cost paths.
• Abstract（参考訳）: グラフにおける経路探索は、コンピュータ科学における最も研究されている問題の1つである。 この文脈では、探索アルゴリズムはより効率的なターゲットノード探索のためのヒューリスティックで拡張されることが多い。 本研究では,ニューラルネットワークの最近の進歩を組み合わせることで,グラフ上の経路探索問題に対する効率的なヒューリスティック関数を学習する。 トレーニング時にはマルチタスク学習を利用して,DijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のあるヒューリスティック関数を共同で学習する。 推論時には、学習したヒューリスティックをa*アルゴリズムに挿入します。 その結果、学習したヒューリスティックス値上でa*を実行すると、dijkstraに比べてターゲットノード検索が大幅にスピードアップすることが示された。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• A Cover Time Study of a non-Markovian Algorithm [18.23492383352517]
  提案手法は,無作為なランダムウォークサーチよりも負のフィードバック戦略(カウントベース探索法)が優れていることを示す。 また、クリッドグラフやツリーグラフなど、特別なが重要なグラフのカバータイムも小さくする。
  論文  参考訳（メタデータ） (2023-06-08T03:09:49Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Learning Graph Search Heuristics [48.83557172525969]
  本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。 我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。 実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
  論文  参考訳（メタデータ） (2022-12-07T22:28:00Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  アルゴリズムの学習表現は機械学習の新たな領域であり、ニューラルネットワークから古典的なアルゴリズムで概念をブリッジしようとしている。 本稿では,従来のアルゴリズムを包括するCLRS Algorithmic Reasoning Benchmarkを提案する。 我々のベンチマークは、ソート、探索、動的プログラミング、グラフアルゴリズム、文字列アルゴリズム、幾何アルゴリズムなど、様々なアルゴリズムの推論手順にまたがっている。
  論文  参考訳（メタデータ） (2022-05-31T09:56:44Z)
• How to transfer algorithmic reasoning knowledge to learn new algorithms? [23.335939830754747]
  我々は,実行トレースにアクセス可能なアルゴリズムを用いて,そうでない同様のタスクを解く方法について検討する。 9つのアルゴリズムと3つの異なるグラフタイプを含むデータセットを作成します。 我々はこれを実証的に検証し、その代わりにマルチタスク学習を用いてアルゴリズム推論知識の伝達を実現する方法を示す。
  論文  参考訳（メタデータ） (2021-10-26T22:14:47Z)
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks [70.0197695666261]
  Q*検索は,ノードの子どもの移動コストと値の和を利用するために,深いQ-networksを用いて探索をガイドする検索アルゴリズムである。 我々は1872のメタアクションを含む大きなアクション空間で定式化された場合、Q*探索を用いてルービックキューブを解く。 Q*検索は最大129倍速く、A*検索の最大1288倍のノードを生成する。
  論文  参考訳（メタデータ） (2021-02-08T20:36:41Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)

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

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