Fugu-MT 論文翻訳(概要): Parallel Greedy Best-First Search with a Bound on the Number of Expansions Relative to Sequential Search

論文の概要: Parallel Greedy Best-First Search with a Bound on the Number of Expansions Relative to Sequential Search

arxiv url: http://arxiv.org/abs/2412.12221v1
Date: Mon, 16 Dec 2024 05:39:59 GMT
ステータス: 翻訳完了
システム内更新日: 2024-12-18 13:57:42.295309
Title: Parallel Greedy Best-First Search with a Bound on the Number of Expansions Relative to Sequential Search
Title（参考訳）: 逐次探索に関連する拡張数に基づく並列グレディベストファースト検索
Authors: Takumi Shimoda, Alex Fukunaga,
Abstract要約: PUHF は, 逐次 GBFS で拡張された状態数と, 最悪ケースのタイブレング戦略との定数倍数で束縛されていないことを示す。提案手法は,拡張された状態の数が連続GBFSで拡張された状態の数に一定の範囲内にあることを保証する並列グリージー検索である。
参考スコア（独自算出の注目度）: 2.0718016474717196
License:
Abstract: Parallelization of non-admissible search algorithms such as GBFS poses a challenge because straightforward parallelization can result in search behavior which significantly deviates from sequential search. Previous work proposed PUHF, a parallel search algorithm which is constrained to only expand states that can be expanded by some tie-breaking strategy for GBFS. We show that despite this constraint, the number of states expanded by PUHF is not bounded by a constant multiple of the number of states expanded by sequential GBFS with the worst-case tie-breaking strategy. We propose and experimentally evaluate One Bench At a Time (OBAT), a parallel greedy search which guarantees that the number of states expanded is within a constant factor of the number of states expanded by sequential GBFS with some tie-breaking policy.
Abstract（参考訳）: GBFSのような非許容探索アルゴリズムの並列化は、直接並列化がシーケンシャル検索から著しく逸脱する検索動作をもたらすため、課題となる。従来の研究で提案されたPUHFは並列探索アルゴリズムであり、GBFSのタイブリング戦略によって拡張可能な状態の拡張のみを制約する。この制約にもかかわらず、PUHFによって拡張された状態の数は、最悪の場合のタイブレング戦略により、シーケンシャルGBFSによって拡張された状態の定数倍に制限されないことを示す。提案手法は、拡張された状態の数が、連続したGBFSで拡張された状態の定数要素の範囲内にあることを保証する並列グリージー検索である。

関連論文リスト

Separate Generation and Evaluation for Parallel Greedy Best-First Search [2.0718016474717196]
グレディベスト1次探索 (GBFS) の並列化は, 直接並列化が逐次GBFSと大きく異なる検索動作をもたらすため, 困難である。近年の研究では、Bentch Transition System (BTS) 探索に探索を制約する並列GBFSアルゴリズムのクラスが提案されている。本稿では、状態生成と状態評価を分離し、状態評価率を大幅に改善する並列探索の改善を提案する。
論文参考訳（メタデータ） (2024-08-11T03:29:17Z)
Runtime-coherence trade-offs for hybrid SAT-solvers [1.087459729391301]
総ランタイムとコヒーレンスタイムの間には,単純なトレードオフ関係が存在する,と我々は主張する。最適トレードオフを伴うハイブリッドアルゴリズムの実装において,さらなる柔軟性を示唆する数値シミュレーションを提案する。
論文参考訳（メタデータ） (2024-04-23T17:11:39Z)
Hierarchical Topological Ordering with Conditional Independence Test for Limited Time Series [40.236595154429246]
条件付き独立性テスト(HT-CIT)を用いた階層型トポロジカル順序付けアルゴリズムを提案する。 HT-CITアルゴリズムは、刈り取るべきエッジの数を大幅に削減する。合成および実世界のデータセットから得られた実験結果は,提案したHT-CITアルゴリズムの優位性を示している。
論文参考訳（メタデータ） (2023-08-16T05:01:33Z)
A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文参考訳（メタデータ） (2023-06-15T15:37:31Z)
Continuous Monte Carlo Graph Search [61.11769232283621]
連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
論文参考訳（メタデータ） (2022-10-04T07:34:06Z)
Greedy Relaxations of the Sparsest Permutation Algorithm [4.125187280299247]
我々は, 忠実性よりもますます弱い仮定の下で, 効率的かつ点的に整合したアルゴリズム, GRaSP のクラスを開発する。 GRaSPの最も緩和された形式は、シミュレーションにおいて多くの最先端の因果探索アルゴリズムより優れている。
論文参考訳（メタデータ） (2022-06-11T05:00:36Z)
Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
論文参考訳（メタデータ） (2022-01-18T11:16:40Z)
US-Rule: Discovering Utility-driven Sequential Rules [52.68017415747925]
我々は,高ユーティリティシーケンシャルルールを効率的にマイニングする,US-Ruleと呼ばれる高速アルゴリズムを提案する。より厳密な上界(LEEU, REEU, LERSU, RERSU)とそれに対応する刈り取り戦略を提案する。 US-Ruleは実行時間、メモリ消費、スケーラビリティの点でパフォーマンスが向上する。
論文参考訳（メタデータ） (2021-11-29T23:38:28Z)
Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文参考訳（メタデータ） (2021-05-21T22:22:02Z)
Best-First Beam Search [78.71330480725668]
本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
論文参考訳（メタデータ） (2020-07-08T05:56:01Z)
Exact Indexing of Time Series under Dynamic Time Warping [1.3300217947936062]
シーケンス拡張とLB_Keoghをシームレスに組み合わせた新しい下界距離LB_Keogh+を提案する。不等長列に使用することができ、計算複雑性が低い。 LB_Keogh+に基づいて、DTWの下での時系列の正確なインデックスを考案する。
論文参考訳（メタデータ） (2020-02-11T03:34:48Z)

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