論文の概要: An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem

• arxiv url: http://arxiv.org/abs/2004.00963v1
• Date: Thu, 2 Apr 2020 12:51:26 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-17 12:38:31.576604
• Title: An anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem
• Title（参考訳）: 2018 roadef/euroチャレンジガラス切断問題に対するanytime tree searchアルゴリズム
• Authors: Luc Libralesso, Florian Fontan
• Abstract要約: 我々は、2018年のROADEF/EUROチャレンジガラス切断問題のために、フランスの企業であるサン=ゴバンが提案した木探索アルゴリズムを提示する。 主な構成要素は、ガイド関数、対称性破壊戦略、擬似支配ルールを備えたメモリバウンドA* (MBA*) と呼ばれる新しい検索アルゴリズムである。 さらに,擬似支配ルールに基づく第2木探索アルゴリズムを設計し,高い優先順位制約を持つ課題事例のいくつかに焦点をあてた。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this article, we present the anytime tree search algorithm we designed for the 2018 ROADEF/EURO challenge glass cutting problem proposed by the French company Saint-Gobain. The resulting program was ranked first among 64 participants. Its key components are: a new search algorithm called Memory Bounded A* (MBA*) with guide functions, a symmetry breaking strategy, and a pseudo-dominance rule. We perform a comprehensive study of these components showing that each of them contributes to the algorithm global performances. In addition, we designed a second tree search algorithm fully based on the pseudo-dominance rule and dedicated to some of the challenge instances with strong precedence constraints. On these instances, it finds the best-known solutions very quickly.
• Abstract（参考訳）: 本稿では、フランス企業サン=ゴバインが提唱した2018 ROADEF/EUROチャレンジガラス切断問題のために設計した木探索アルゴリズムについて述べる。 このプログラムは64人中1位にランクインした。 主な構成要素は、ガイド関数、対称性破壊戦略、擬似支配ルールを備えたメモリバウンドA* (MBA*) と呼ばれる新しい検索アルゴリズムである。 それぞれのコンポーネントがアルゴリズム全体のパフォーマンスに寄与することを示す,これらのコンポーネントの包括的研究を行う。 さらに,擬似支配ルールをベースとした第2木探索アルゴリズムを設計し,高い優先順位制約を持つ課題のいくつかに焦点をあてた。 これらの例では、最もよく知られたソリューションがすぐに見つかる。

関連論文リスト

• RethinkMCTS: Refining Erroneous Thoughts in Monte Carlo Tree Search for Code Generation [65.5353313491402]
  本稿では,モンテカルロ木探索(MCTS)アルゴリズムを用いて,コードを生成する前に思考レベルの探索を行うRethinkMCTSを紹介する。 我々は,検索中の誤った思考を洗練させるために,微動コード実行フィードバックからの言語フィードバックを構築した。 RethinkMCTSは従来の検索ベースおよびフィードバックベースのコード生成ベースラインよりも優れていることを実証する。
  論文  参考訳（メタデータ） (2024-09-15T02:07:28Z)
• Pathfinding with Lazy Successor Generation [12.02023514105999]
  位置のみを付与し,エッジを暗黙的に定義するパスフィンディング問題について検討する。 単純な構造にもかかわらず、この問題は膨大な数の位置で非自明になる。 そこで我々は,LaCAS*アルゴリズムを提案する。これは,全ての後継を一度に生成するのではなく,探索が進むにつれて徐々に後継を生成できる。
  論文  参考訳（メタデータ） (2024-08-27T23:25:25Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• UNSAT Solver Synthesis via Monte Carlo Forest Search [10.754275929551593]
  木MDPにおける学習ポリシーのための強化学習(RL)アルゴリズムであるモンテカルロ森林探索(MCFS)を紹介する。 そのような問題の例としては、SAT公式の不満足性の証明、SAT公式の解の数を数えることがある。 我々は,満足度(SAT)問題を解決するためにDPLL分岐ポリシーを学習するMCFSアルゴリズムであるKnuth Synthesisをダブした。
  論文  参考訳（メタデータ） (2022-11-22T20:52:50Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。 このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。 我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-03-28T21:34:16Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Exploring search space trees using an adapted version of Monte Carlo tree search for combinatorial optimization problems [0.6882042556551609]
  このアプローチでは,問題インスタンスの探索空間木を探索するアルゴリズムを用いる。 このアルゴリズムはモンテカルロ木探索(Monte Carlo tree search)をベースとしている。
  論文  参考訳（メタデータ） (2020-10-22T08:33:58Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems [0.0]
  アルゴリズムは64人中1位でした 私たちはそれを一般化し、それが本来設計された特定の問題に有効であるだけでなく、非常に競争力があることを示す。 このアルゴリズムはPackingrと呼ばれる新しいソフトウェアパッケージで実装されている。
  論文  参考訳（メタデータ） (2020-04-02T13:41:07Z)

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

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