論文の概要: Research Re: search & Re-search

• arxiv url: http://arxiv.org/abs/2403.13705v1
• Date: Wed, 20 Mar 2024 16:08:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-21 16:18:41.913519
• Title: Research Re: search & Re-search
• Title（参考訳）: Research Re: Search & Re-search
• Authors: Aske Plaat,
• Abstract要約: 本研究では,深度優先アルゴリズムのABと最良優先アルゴリズムのSSSについて詳しく検討する。 これらのアルゴリズムの一般的な意見は、SSSはより効率的な探索の可能性をもっているが、その複雑な定式化と指数記憶の要求はそれを非現実的にしている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Search algorithms are often categorized by their node expansion strategy. One option is the depth-first strategy, a simple backtracking strategy that traverses the search space in the order in which successor nodes are generated. An alternative is the best-first strategy, which was designed to make it possible to use domain-specific heuristic information. By exploring promising parts of the search space first, best-first algorithms are usually more efficient than depth-first algorithms. In programs that play minimax games such as chess and checkers, the efficiency of the search is of crucial importance. Given the success of best-first algorithms in other domains, one would expect them to be used for minimax games too. However, all high-performance game-playing programs are based on a depth-first algorithm. This study takes a closer look at a depth-first algorithm, AB, and a best-first algorithm, SSS. The prevailing opinion on these algorithms is that SSS offers the potential for a more efficient search, but that its complicated formulation and exponential memory requirements render it impractical. The theoretical part of this work shows that there is a surprisingly straightforward link between the two algorithms -- for all practical purposes, SSS is a special case of AB. Subsequent empirical evidence proves the prevailing opinion on SSS to be wrong: it is not a complicated algorithm, it does not need too much memory, and it is also not more efficient than depth-first search.
• Abstract（参考訳）: 探索アルゴリズムは、しばしばノード拡張戦略によって分類される。 1つの選択肢はディープファースト戦略であり、後続ノードが生成される順序で検索空間を横切る単純なバックトラック戦略である。 別の方法は、ドメイン固有のヒューリスティック情報の使用を可能にするために設計されたベストファースト戦略である。 探索空間の有望な部分を探索することによって、最優先のアルゴリズムは通常、深さ優先のアルゴリズムよりも効率的になる。 チェスやチェッカーなどのミニマックスゲームをするプログラムでは、探索の効率が重要である。 他のドメインでのベストファーストアルゴリズムの成功を考えると、ミニマックスゲームにも使われるだろう。 しかし、全ての高性能ゲームプレイングプログラムはディープファーストアルゴリズムに基づいている。 本研究では,深度優先アルゴリズムのABと最良優先アルゴリズムのSSSについて詳しく検討する。 これらのアルゴリズムの一般的な意見は、SSSはより効率的な探索の可能性を秘めているが、その複雑な定式化と指数記憶の要求はそれを非現実的とするものである。 この研究の理論的部分は、2つのアルゴリズムの間に驚くほど単純なリンクがあることを示しています。 その後の実証的な証拠は、SSSに関する一般的な意見が間違っていることを証明している:それは複雑なアルゴリズムではなく、メモリをあまり必要とせず、深度優先探索よりも効率的ではない。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
  SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。 ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。 これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
  論文  参考訳（メタデータ） (2024-06-07T13:42:15Z)
• An optimized quantum minimum searching algorithm with sure-success probability and its experiment simulation with Cirq [4.987556615430226]
  本稿では,確実な確率で最適化された量子最小探索アルゴリズムを提案する。 性能評価の結果,本アルゴリズムはDHAアルゴリズムよりも精度と効率が高いことがわかった。
  論文  参考訳（メタデータ） (2023-09-25T14:07:27Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• The CLRS Algorithmic Reasoning Benchmark [28.789225199559834]
  アルゴリズムの学習表現は機械学習の新たな領域であり、ニューラルネットワークから古典的なアルゴリズムで概念をブリッジしようとしている。 本稿では,従来のアルゴリズムを包括するCLRS Algorithmic Reasoning Benchmarkを提案する。 我々のベンチマークは、ソート、探索、動的プログラミング、グラフアルゴリズム、文字列アルゴリズム、幾何アルゴリズムなど、様々なアルゴリズムの推論手順にまたがっている。
  論文  参考訳（メタデータ） (2022-05-31T09:56:44Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Waypoint Planning Networks [66.72790309889432]
  本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。 我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。 WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
  論文  参考訳（メタデータ） (2021-05-01T18:02:01Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Best-First Beam Search [78.71330480725668]
  本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。 ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
  論文  参考訳（メタデータ） (2020-07-08T05:56:01Z)

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

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