論文の概要: Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics

• arxiv url: http://arxiv.org/abs/2606.05956v1
• Date: Thu, 04 Jun 2026 09:53:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-05 22:39:44.706233
• Title: Bidirectional Search for Longest Paths: Case for Front-to-Front Heuristics
• Title（参考訳）: 最も長い道の双方向探索--前向きヒューリスティックスの場合
• Authors: Tzur Shubi, Ariel Felner, Solomon Eyal Shimony, Shahaf S. Shperberg,
• Abstract要約: 本稿では,BixDFBnBを提案する。BixDFBnBは,BixDFBnBとBingle-Frontier Bidirectional Searchフレームワークを併用した,双方向のディープファースト分岐結合アルゴリズムである。 SFBDSはペア状態で動作するため、双方向のフロンティア管理に関連するオーバーヘッドを回避することができる。 BiXDFBnBは、LSP(Longest Simple Path)、Snakes(Snakes)、CIB(Coil-in-the-Box)といった最長パス問題に適用される。
• 参考スコア（独自算出の注目度）: 5.729787815551408
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bidirectional heuristic search can potentially reduce search effort for problems amenable to backward search. Therein, it is well-known that front-to-front heuristics can reduce the number of node expansions, but their overhead is so high that overall runtime almost always increases. We propose BiXDFBnB, a bidirectional depth-first branch-and-bound algorithm that adapts the Single-Frontier Bidirectional Search (SFBDS) framework - originally developed for shortest-path (MIN) problems - to the Generalized Longest Simple Path (GLSP) setting. Because SFBDS inherently operates on paired states, front-to-front (F2F) heuristic evaluation arises naturally and avoids the overhead typically associated with bidirectional frontier management. We show that this adaptation can be successfully applied to maximization (MAX) problems while efficiently handling overlapping constraints. BiXDFBnB is applied to several types of longest-path problems: Longest Simple Path (LSP), Snakes, and Coil-in-the-Box (CIB). Empirical evaluation shows that the new algorithm frequently reduces the number of node expansions and, in some cases, also improves overall runtime.
• Abstract（参考訳）: 双方向ヒューリスティック検索は、後方探索に有効な問題の探索労力を減らす可能性がある。 したがって、フロント・ツー・フロントのヒューリスティックスがノード拡張数を削減できることはよく知られているが、そのオーバーヘッドが非常に高く、ランタイム全体が常に増加する。 本稿では,最短パス(MIN)問題に対して開発されたSFBDS(Single-Frontier Bidirectional Search)フレームワークをGLSP(Generalized Longest Simple Path)設定に適応させる,双方向の深度優先分岐結合アルゴリズムであるBiXDFBnBを提案する。 SFBDSは本質的にペア状態で動作するため、フォワード・ツー・フロント(F2F)ヒューリスティック評価は自然に発生し、通常双方向フロンティア管理に関連するオーバーヘッドを回避する。 この適応は、重なり合う制約を効率的に処理しながら、最大化(MAX)問題にうまく適用できることを示す。 BiXDFBnBは、LSP(Longest Simple Path)、Snakes(Snakes)、CIB(Coil-in-the-Box)といった最長パス問題に適用される。 経験的評価では、新しいアルゴリズムはノード拡張の回数を減らし、場合によっては全体の実行時間も改善する。

関連論文リスト

• Bidirectional Incremental Generalized Hybrid A* [5.811502603310249]
  本稿では, Bi-IGHA* が R3, R4, R6 の計画問題の拡張を大幅に削減することを示す。 また,Bi-IGHA*は高速オフロード自律化のためのキノダイナミック計画により,等価な閉ループ性能を実現することを示す。
  論文  参考訳（メタデータ） (2026-05-28T23:04:37Z)
• A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings [60.48717743667377]
  A*-Thoughtは、最も本質的な思考を識別し、分離するために設計された効率的なツリー検索ベースの統合フレームワークである。 LRMの推論過程を探索木として定式化し、各ノードは巨大な推論空間における推論スパンを表す。 低予算でQwQ-32Bを2.39$times$で改善し、高予算で出力トークンの長さを50%近く削減できる。
  論文  参考訳（メタデータ） (2025-05-30T12:58:34Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) は大規模言語モデル(LLM)推論を強化し、分散木としての問題解決を構造化する。 推論における推論経路を動的に最適化することを目的とした,新しい並列化フレームワークであるDynamic Parallel Tree Search (DPTS)を提案する。 Qwen-2.5とLlama-3のMath500とGSM8Kデータセットによる実験では、DPTSは平均で2-4倍効率が向上した。
  論文  参考訳（メタデータ） (2025-02-22T14:13:37Z)
• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• 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)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• 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)

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

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