論文の概要: 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木探索アルゴリズムを設計し,高い優先順位制約を持つ課題のいくつかに焦点をあてた。
これらの例では、最もよく知られたソリューションがすぐに見つかる。
関連論文リスト
- On Uniformly Optimal Algorithms for Best Arm Identification in Two-Armed
Bandits with Fixed Budget [53.99808986087965]
ベルヌーイ報奨を伴う二本腕包帯における固定予算によるベストアーム識別の問題について検討した。
我々は,アルゴリズムが各アームを等しくサンプリングするのと同様に,アルゴリズムが機能することはないことを証明した。
論文 参考訳(メタデータ) (2023-08-23T08:38:53Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。
具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。
また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文 参考訳(メタデータ) (2023-07-25T12:33:53Z) - UNSAT Solver Synthesis via Monte Carlo Forest Search [11.729374460065745]
木MDPにおける学習ポリシーのための強化学習(RL)アルゴリズムであるモンテカルロ森林探索(MCFS)を紹介する。
そのような問題の例としては、SAT公式の不満足性の証明、SAT公式の解の数を数えることがある。
我々は,満足度(SAT)問題を解決するためにDPLL分岐ポリシーを学習するMCFSアルゴリズムであるKnuth Synthesisをダブした。
論文 参考訳(メタデータ) (2022-11-22T20:52:50Z) - Decision Diagram-Based Branch-and-Bound with Caching for Dominance and
Suboptimality Detection [9.175779296469194]
本稿では動的プログラミングモデルの構造を利用して探索を高速化する新しい要素を提案する。
鍵となる考え方は、検索中にキャッシュされた拡張しきい値に問い合わせることによって、同じ動的プログラミング状態に対応するノードの繰り返し拡張を防止することである。
このキャッシング機構によって引き起こされるプルーニングは、アルゴリズムによって拡張されたノード数を著しく削減できることを示す実験である。
論文 参考訳(メタデータ) (2022-11-22T10:18:33Z) - 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) - A Heuristic Based on Randomized Greedy Algorithms for the Clustered
Shortest-Path Tree Problem [2.099922236065961]
本稿では, RGA とショート・パス・ツリー・アルゴリズム (SPTA) の主な特徴を組み合わせたクラスタ・ショート・パス・ツリー問題 (CluSPT) を扱うアルゴリズムを提案する。
提案アルゴリズムの性能を評価するため,ユークリッドベンチマークが選択される。
論文 参考訳(メタデータ) (2020-05-05T08:34:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。