論文の概要: Search for developments of a box having multiple ways of folding by SAT
solver
- arxiv url: http://arxiv.org/abs/2005.02645v1
- Date: Wed, 6 May 2020 08:15:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 06:18:31.891693
- Title: Search for developments of a box having multiple ways of folding by SAT
solver
- Title(参考訳): SATソルバによる複数折り畳み式ボックスの開発
- Authors: Riona Tadaki and Kazuyuki Amano
- Abstract要約: ポリオミノ(英: polyomino)は、ポリオミノを形成する単位正方形の端を折り畳んで箱を作ることができる場合の展開である。
本研究では,SATソルバを用いたコンピュータ検索を行った。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A polyomino is called a development if it can make a box by folding edges of
unit squares forming the polyomino. It is known that there are developments
that can fold into a box (or boxes) in multiple ways. In this work, we
conducted a computer search for finding such developments by using a SAT
solver. As a result, we found thousands of such developments including a
polyomino of area 52 that can fold into a box of size $1 \times 2 \times 8$ in
five different ways.
- Abstract(参考訳): ポリオミノを形成する単位四角形の縁を折って箱を作ることができる場合は、ポリオミノを展開と呼ぶ。
複数の方法でボックス(またはボックス)に折り畳むことができる開発があることが知られている。
本研究では,satソルバを用いて,そのような発展を見出すためのコンピュータ探索を行った。
その結果、エリア52のポリオミノを含む何千もの開発が、サイズ1 \times 2 \times 8$の5つの異なる方法で折り畳むことができることがわかった。
関連論文リスト
- On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile
Puzzles [20.93478961897733]
15ドル(約1万5000円)のゲームでは、ラベル付き四角いタイルが4時間4ドル(約4万4000円)のボードにリセットされ、それぞれの(時間)ステップで隣のタイルがスライドし、それまでタイルが占めていたスペースが新しいエスコートとして残る。
汎用スライディングタイルパズル(GSTP)について検討し,(1)エスコートが1ドル以上、(2)複数タイルが1ステップで同期動作可能であることを示した。
一般的な離散マルチエージェント/ロボットモーションモデルと比較して、GSTPは幅広い高ユーティリティアプリケーションに対してより正確なモデルを提供する。
論文 参考訳(メタデータ) (2023-12-18T02:24:07Z) - Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
分解硬度(d硬度)の概念を導入する。
d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
論文 参考訳(メタデータ) (2023-12-16T12:44:36Z) - Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
本稿では,ポリトープ内の格子数に近似する新しいフレームワークを提案する。
我々のアルゴリズムは、数十次元のポリトープを解くことができ、最先端のカウンタを著しく上回る。
論文 参考訳(メタデータ) (2023-12-14T09:53:54Z) - An AlphaZero-Inspired Approach to Solving Search Problems [63.24965775030674]
探索問題を解くためにAlphaZeroで使用される手法と手法を適応する。
本稿では,簡単な解法と自己還元という観点から表現できる可能性について述べる。
また,探索問題に適応したモンテカルロ木探索法についても述べる。
論文 参考訳(メタデータ) (2022-07-02T23:39:45Z) - A decision-tree framework to select optimal box-sizes for product
shipments [0.700545830845487]
パッケージ取扱施設では、商品の出荷にさまざまな大きさの箱を用いており、製品寸法よりもはるかに大きい不適切な大きさの箱は、無駄を発生させ、出荷コストを不当に増加させる。
i) それぞれのクラスタが特定のサイズの変種で出荷される製品群に対応する長さ、幅、高さの3ドル次元空間におけるクラスタリング問題に還元し、 (ii) 計算複雑性の低い、効率的な前方決定木ベースのクラスタリング手法をN$と$Kで提示する。
論文 参考訳(メタデータ) (2022-02-09T04:46:55Z) - Theoretical and empirical analysis of a fast algorithm for extracting
polygons from signed distance bounds [0.0]
本稿では,符号付き距離境界をポリゴンメッシュに変換するための高速な手法について検討する。
これは、球追跡と従来の多角化スキームの1つを組み合わせることで達成される。
我々は、$O(N2log N)$計算複雑性が$N3$セルを持つ多角化格子であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2021-11-10T16:31:27Z) - PAC Best Arm Identification Under a Deadline [101.10352416022559]
我々は、$(epsilon, delta)$-PACベストアーム識別について研究し、意思決定者は、アームプル(サンプル)の数を最小化しながら、少なくとも1 - delta$の確率で最適なアームを識別しなければならない。
この作業では、決定者はT$ラウンドの期限が与えられ、各ラウンドで、どのアームを引っ張るか、何回引っ張るかを適応的に選ぶことができる。
本稿では,この設定のための新しいアルゴリズムであるElastic Batch Racing (EBR)を提案する。
論文 参考訳(メタデータ) (2021-06-06T19:48:32Z) - SAT-based Circuit Local Improvement [77.36158507255637]
正確な回路サイズを見つけることは、実際よく知られた最適化問題である。
与えられた回路の周りのボール内の小さな回路を検索します。
各種対称関数を用いた実験結果について報告する。
論文 参考訳(メタデータ) (2021-02-19T16:01:50Z) - A space-indexed formulation of packing boxes into a larger box [4.4198435146063355]
現在の整数プログラミングソルバは、12個の単位キューブを1時間以内に1x1x11ボックスに詰め込むことはできない。
我々は、より大きなボックスに箱を梱包する問題の別の緩和を提示し、それははるかに大きなインスタンスを解決することを可能にします。
論文 参考訳(メタデータ) (2021-01-02T12:10:47Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳(メタデータ) (2020-12-14T18:14:08Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳(メタデータ) (2020-06-25T19:59:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。