論文の概要: Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search

• arxiv url: http://arxiv.org/abs/2606.07047v2
• Date: Mon, 08 Jun 2026 08:14:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:05.067326
• Title: Front-to-Attractors: Modifying the Front-to-Front Heuristic in Bidirectional Search
• Title（参考訳）: フロント・ツー・アトラクタ:双方向探索におけるフロント・ツー・ファント・ヒューリスティックの修正
• Authors: Alvin Zou, Muhammad Suhail Saleem, Maxim Likhachev,
• Abstract要約: ヒューリスティックスは双方向探索アルゴリズムの性能において中心的な役割を果たす。 front-to-front (F2F) は、s から逆の検索フロンティアまでの距離をペア関数で推定する。 フロント・ツー・アトラクタ(F2A)は、sから、反対の探索方向にある小さな動的に維持されたアトラクタのセットまでの距離を推定する。
• 参考スコア（独自算出の注目度）: 16.310440859027317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristics play a central role in the performance of bidirectional search algorithms, which commonly rely on two main classes. Front-to-end (F2E) heuristics estimate the distance from a state s to the target of the search (the goal for forward search or the start for backward search). In contrast, front-to-front (F2F) heuristics estimate the distance from s to the opposite search frontier using a pairwise function h(s, s'), where s' ranges over frontier states. Although F2F heuristics are typically more informative and therefore reduce the number of node expansions, their reliance on extensive pairwise evaluations incurs substantial computational overhead. To address this limitation, we introduce a new heuristic class, front-to-attractors (F2A), that preserves much of the informativeness of F2F while dramatically reducing its computational cost. Rather than evaluating distances to all states on the opposite frontier, F2A estimates the distance from s to a small, dynamically maintained set of attractors in the opposite search direction. These attractors serve as a surrogate for the full frontier, enabling rich heuristic guidance at a fraction of the computational expense while maintaining the optimality guarantees offered by F2F. We evaluate F2A across multiple domains and show that it reduces the number of pairwise evaluations by up to 11.2x compared to F2F, while achieving 4.8x fewer node expansions than F2E on average.
• Abstract（参考訳）: ヒューリスティックスは、一般的に2つの主要なクラスに依存する双方向探索アルゴリズムの性能において中心的な役割を果たす。 Front-to-end (F2E) ヒューリスティックスは、状態sから検索対象までの距離を推定する(前方探索の目標や後方探索の開始)。 対照的に、F2F ( Front-to-front) ヒューリスティックスは、s から対向する探索フロンティアまでの距離を、対角関数 h(s, s') を用いて推定する。 F2Fヒューリスティックスは一般により情報的であり、したがってノード拡張の数を減少させるが、それらが広いペアワイズ評価に依存しているため、かなりの計算オーバーヘッドが生じる。 この制限に対処するため、計算コストを劇的に削減しつつ、F2Fの多くの情報を保存する新しいヒューリスティッククラス、F2Aを導入する。 反対側のフロンティア上の全ての状態への距離を評価するのではなく、F2Aはsから反対の探索方向における小さな動的に維持されたアトラクタの集合までの距離を推定する。 これらのアトラクタは、フルフロンティアのサロゲートとして機能し、F2Fが提供する最適性保証を維持しながら、計算コストのごく一部で豊かなヒューリスティックガイダンスを可能にする。 我々はF2Aを複数の領域で評価し、F2Fと比較して最大11.2倍のペア評価を減らし、F2Eよりも平均4.8倍少ないノード展開を実現した。

関連論文リスト

• Posterior Augmented Flow Matching [64.1559809786948]
  後拡張フローマッチング(PAFM)はフローマッチング(FM)の一般化である PAFMは、異なるモデルスケールで最大3.4FID50KでFMよりも改善されていることを示す。
  論文  参考訳（メタデータ） (2026-05-01T17:59:59Z)
• Active Measurement of Two-Point Correlations [21.039994126374584]
  2点相関関数 (2PCF) は空間における点のクラスタリングの特徴付けに広く用いられている。 本稿では,ターゲット源の2PCFを効率的に推定するためのHuman-in-the-loopフレームワークを提案する。
  論文  参考訳（メタデータ） (2026-04-06T22:43:12Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  NLHFにおける最適乗算重み更新(mathtOMWU$)に対する最初の収束保証を提供する。 本分析では, 稀に発生する行動の確率が指数関数的に小さい値から指数関数的に増大する新たな限界収束挙動を同定する。
  論文  参考訳（メタデータ） (2025-12-31T12:08:29Z)
• Towards Competitive Search Relevance For Inference-Free Learned Sparse Retrievers [7.976154147999298]
  推測のないスパースモデルは 検索の関連という点で はるかに遅れています スパースモデルと密集したサイムズモデルの両方と比較して 性能改善のための2つのアプローチを提案する。 まず,IDFトークンの寄与を抑えるマッチング関数に対するIDF対応ペナルティを提案する。 第2に,シロイヌナズナと疎水性レトリーバーを組み合わせたヘテロジニアスアンサンブル知識蒸留フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-11-07T03:46:43Z)
• SHAP values via sparse Fourier representation [31.824587432702057]
  SHAP(SHapley Additive exPlanations)値は、解釈可能で説明可能なAIにおいて、局所的特徴属性の広く用いられる方法である。 ブラックボックス設定とツリーベースモデルの両方において、SHAP値を計算するための効率的な2段階アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-08T19:05:50Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• FeDXL: Provable Federated Learning for Deep X-Risk Optimization [105.17383135458897]
  我々は、既存のアルゴリズムが適用できないXリスクのファミリーを最適化するために、新しい連邦学習(FL)問題に取り組む。 Xリスクに対するFLアルゴリズムを設計する際の課題は、複数のマシンに対する目的の非可逆性と、異なるマシン間の相互依存にある。
  論文  参考訳（メタデータ） (2022-10-26T00:23:36Z)
• Achieving Statistical Optimality of Federated Learning: Beyond Stationary Points [19.891597817559038]
  Federated Learning(FL)は、プライバシ保護とクラウドでの計算負荷の低減に大きな可能性を持つ、有望なフレームワークである。 最近の研究は、(1)その固定点が元の最適化問題の定常点に対応していないこと、(2)見いだされた共通モデルが局所的にうまく一般化できないこと、の2つの方法に対する懸念を提起している。 一般的なカーネル回帰設定では、FedAvgとFedProxの両方が極小最大誤差率に収束することを示す。
  論文  参考訳（メタデータ） (2021-06-29T09:59:43Z)
• Debiasing a First-order Heuristic for Approximate Bi-level Optimization [38.068090269482425]
  近似バイレベル最適化(ABLO)は、数値的な(インナーレベルの)最適化ループを含む(外部レベルの)最適化問題からなる。 FOMの収束性に関する理論的理解の欠如がある。 本稿では,メモリの複雑さを一定に保った非バイアスなFOMを$r$の関数として提案する。
  論文  参考訳（メタデータ） (2021-06-04T13:46:48Z)

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

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