論文の概要: Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)

• arxiv url: http://arxiv.org/abs/2408.08227v1
• Date: Thu, 15 Aug 2024 15:54:25 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-16 13:26:45.300608
• Title: Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)
• Title（参考訳）: A* の進化による k 最短経路問題の解法(拡張版)
• Authors: Carlos Linares López, Ian Herman,
• Abstract要約: そこで本研究では,A*の自然進化により,その興味深い性質を全て保ちながら,同時に時間的複雑性をもった新しい探索アルゴリズムを提案する。 様々なテストベッドでの実験では、しばしば1～2桁のオーダーで、芸術の状況よりもパフォーマンスが大幅に向上した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of finding the shortest path in a graph G(V, E) has been widely studied. However, in many applications it is necessary to compute an arbitrary number of them, k. Even though the problem has raised a lot of interest from different research communities and many applications of it are known, it has not been addressed to the same extent as the single shortest path problem. The best algorithm known for efficiently solving this task has a time complexity of O (|E| + |V|log{|V|}+k|V|)$ when computing paths in explicit form, and is based on best-first search. This paper introduces a new search algorithm with the same time complexity, which results from a natural evolution of A* thus, it preserves all its interesting properties, making it widely applicable to many different domains. Experiments in various testbeds show a significant improvement in performance over the state of the art, often by one or two orders of magnitude.
• Abstract（参考訳）: グラフ G(V, E) における最短経路を求める問題は広く研究されている。 しかし、多くのアプリケーションでは、任意の数の k を計算する必要がある。 この問題は異なる研究コミュニティから多くの関心を集めており、多くの応用が知られているが、単一の最短経路問題と同じ程度では解決されていない。 このタスクを効率的に解くために知られている最良のアルゴリズムは、O (|E| + |V|log{|V|}+k|V|)$ の時間複雑性を持つ。 そこで本研究では,A* の自然進化にともなって,A* のすべての興味深い特性を保存し,多くの異なる領域に広く適用することができる新しい探索アルゴリズムを提案する。 様々なテストベッドでの実験では、しばしば1～2桁の精度で、最先端よりもパフォーマンスが大幅に向上した。

関連論文リスト

• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
  WCSPP(Weight Constrained Shortest Path Problem)は、AIにおいてよく研究されているが、難しいトピックである。 本稿では, A* 探索に基づく WCSPP に対する2つの新しい解法を提案する。 我々は,大規模で現実的な問題事例の集合に対して,アルゴリズムの性能を実証的に評価した。
  論文  参考訳（メタデータ） (2022-07-29T15:32:45Z)
• Multidimensional Assignment Problem for multipartite entity resolution [69.48568967931608]
  Multipartiteエンティティ解決は、複数のデータセットから1つのエンティティにレコードを統合することを目的としている。 代入問題を解くために、グリーディアルゴリズムと大規模近傍探索という2つの手順を適用する。 データベースのサイズが大きくなるにつれて、設計ベースのマルチスタートがより効率的であることを示す。
  論文  参考訳（メタデータ） (2021-12-06T20:34:55Z)
• 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)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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