論文の概要: Smoothed Analysis of Inconsistent A*

• arxiv url: http://arxiv.org/abs/2609.23680v1
• Date: Sun, 20 Sep 2026 14:42:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-23 18:04:03.941154
• Title: Smoothed Analysis of Inconsistent A*
• Title（参考訳）: 不整合A*の平滑解析
• Abstract要約: A*検索は人工知能の基本的な経路探索アルゴリズムである。 不整合性 A* が実際に極めて効率的に動作することを示す。 また、この結果はDijkstraのアルゴリズムの負重みグラフの関数的に等価な問題にまで自然に拡張されることを示す。
• 参考スコア（独自算出の注目度）: 2.919436283272136
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of $Ω(2^n)$. However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m κ)$, where $n$ is the number of nodes, $m$ is the number of edges, and $κ$ controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.
• Abstract（参考訳）: A*検索は人工知能の基本的な経路探索アルゴリズムである。 許容的かつ一貫性のあるヒューリスティックスは、各状態を最大1回拡張することで効率を保証しますが、現代の検索アプリケーションは、機械学習やランダム化評価などから派生した、強力だが一貫性のないヒューリスティックを頻繁に採用します。 これらの矛盾したヒューリスティックを使用するための長年の理論的障壁は、破滅的なノード再膨張のリスクであり、これは最悪の指数時間複雑性をΩ(2^n)$とする。 しかし、経験的観察はこの悲観的境界に矛盾し、非矛盾なA*が実際に非常に効率的に動作することを示す。 この理論と実践の間に大きなギャップを埋めるために,不整合ヒューリスティックスを用いたA*アルゴリズムのスムーズな解析を行った。 最悪の探索グラフのエッジ重みにランダムな摂動を適用することで、典型的な実世界の雑音をモデル化する。 我々の主な結果は、不整合 A* の期待される滑らかな時間複雑性が多項式、具体的には総反復数$O(n^2 m κ)$,$n$ はノード数、$m$ はエッジ数、$κ$ はランダム摂動のスケールを制御することを証明している。 さらに、この結果は、負重グラフ上のダイクストラのアルゴリズムの関数的に等価な問題にまで自然に拡張されることも示している。

関連論文リスト

• Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs [39.163609792464506]
  Lanczos Iteration と Lanczos Push は、大きなグラフ上での抵抗を計算するための効率的なアルゴリズムとして提示される。 様々なサイズと統計特性の8つの実世界のデータセットに関する広範な実験を通じて、我々のアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2026-01-16T10:22:07Z)
• 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)
• Towards Understanding the Generalizability of Delayed Stochastic Gradient Descent [63.43247232708004]
  非同期で実行される勾配降下は、大規模機械学習モデルのトレーニングにおいて重要な役割を果たす。 既存の一般化誤差境界は悲観的であり、非同期遅延と一般化の相関を明らかにすることはできない。 我々の理論的結果は、非同期遅延は遅延SGDアルゴリズムの一般化誤差を低減することを示唆している。
  論文  参考訳（メタデータ） (2023-08-18T10:00:27Z)
• Linear-Time Algorithms for Front-Door Adjustment in Causal Graphs [3.707290781951909]
  観測データから因果効果を推定することは経験科学の基本的な課題である。 本論文は, 観測媒介者を用いて, 保存されていない共同設立者の存在下においても, 因果関係を識別できる古典的な手法である, 正面調整に焦点を当てたものである。
  論文  参考訳（メタデータ） (2022-11-29T18:44:03Z)
• Finite-Time Error Bounds for Greedy-GQ [20.51105692499517]
  We show that Greedy-GQ algorithm converges fast-time error。 我々の分析は、ステップサイズを選択するために、より高速な収束ステップサイズを提供する。
  論文  参考訳（メタデータ） (2022-09-06T15:04:57Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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