論文の概要: Approximately Optimal Search on a Higher-dimensional Sliding Puzzle
- arxiv url: http://arxiv.org/abs/2412.01937v1
- Date: Mon, 02 Dec 2024 19:59:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-04 15:51:49.166506
- Title: Approximately Optimal Search on a Higher-dimensional Sliding Puzzle
- Title（参考訳）: 高次元スライディングノズルのほぼ最適探索
- Authors: Nono SC Merleau, Miguel O'Malley, Érika Roldán, Sayan Mukherjee,
- Abstract要約: 本稿では,高次元パズルの様々なシナリオを包括的に研究する。
正確なアルゴリズム(A*探索)と2つのほぼ最適な探索手法(EA)と強化学習(RL)を示す。
- 参考スコア（独自算出の注目度）: 0.9537146822132906
- License:
- Abstract: Higher-dimensional sliding puzzles are constructed on the vertices of a $d$-dimensional hypercube, where $2^d-l$ vertices are distinctly coloured. Rings with the same colours are initially set randomly on the vertices of the hypercube. The goal of the puzzle is to move each of the $2^d-l$ rings to pre-defined target vertices on the cube. In this setting, the $k$-rule constraint represents a generalisation of edge collision for the movement of colours between vertices, allowing movement only when a hypercube face of dimension $k$ containing a ring is completely free of other rings. Starting from an initial configuration, what is the minimum number of moves needed to make ring colours match the vertex colours? An algorithm that provides us with such a number is called God's algorithm. When such an algorithm exists, it does not have a polynomial time complexity, at least in the case of the 15-puzzle corresponding to $k=1$ in the cubical puzzle. This paper presents a comprehensive computational study of different scenarios of the higher-dimensional puzzle. A benchmark of three computational techniques, an exact algorithm (the A* search) and two approximately optimal search techniques (an evolutionary algorithm (EA) and reinforcement learning (RL)) is presented in this work. The experiments show that all three methods can successfully solve the puzzle of dimension three for different face dimensions and across various difficulty levels. When the dimension increases, the A* search fails, and RL and EA methods can still provide a generally acceptable solution, i.e. a distribution of a number of moves with a median value of less than $30$. Overall, the EA method consistently requires less computational time, while failing in most cases to minimise the number of moves for the puzzle dimensions $d=4$ and $d=5$.
- Abstract（参考訳）: 高次元スライディングパズルは、$d$次元ハイパーキューブの頂点上に構築され、2^d-l$頂点が明確に色付けされている。
同じ色のリングは、最初はハイパーキューブの頂点にランダムにセットされる。
パズルの目標は、それぞれの2^d-l$環を立方体上の予め定義された対象頂点に移すことである。
この設定では、$k$-ruleの制約は、頂点間の色の動きに対するエッジ衝突の一般化を表し、環を含む次元$k$のハイパーキューブ面が他の環から完全に自由である場合にのみ運動を可能にする。
最初の設定から始めて、環の色を頂点色に合わせるのに必要な最小の移動数は何ですか?
そのような数を与えるアルゴリズムは、神のアルゴリズムと呼ばれる。
そのようなアルゴリズムが存在する場合、多項式時間の複雑さはなく、少なくとも立方体パズルにおいて$k=1$に対応する15ノズルの場合である。
本稿では,高次元パズルの様々なシナリオを包括的に計算した。
本稿では, 3つの計算手法, 正確なアルゴリズム (A* 探索) と, ほぼ最適な探索手法 (進化的アルゴリズム (EA) と強化学習 (RL) ) のベンチマークを示す。
実験の結果,3つの手法が顔の次元や難易度に応じて3次元のパズルを解くことができた。
次元が大きくなると A* 探索は失敗し、RL と EA の手法は依然として一般に受け入れられる解、すなわち中央値が 30$ 未満の複数の動きの分布を提供することができる。
全体として、EA法は計算時間が少なく、ほとんどの場合、パズルの次元が$d=4$と$d=5$の移動数を最小化できない。
関連論文リスト
- SIC-POVMs from Stark Units: Dimensions n^2+3=4p, p prime [1.7188280334580197]
実二次体における線量体拡大からのスターク単位が、SICが構築されるシードとして機能することを示す。
この形式の17の異なる次元に対して解を与え、$d = 39604$に達する。
論文 参考訳（メタデータ） (2024-03-05T11:36:33Z) - A Novel Normalized-Cut Solver with Nearest Neighbor Hierarchical
Initialization [107.07093621337084]
正規化カット(N-Cut)は、スペクトルクラスタリングの有名なモデルである。
1)正規化ラプラシア行列の連続スペクトル埋め込みを計算する; 2)$K$-meansまたはスペクトル回転による離散化。
有名な座標降下法に基づく新しいN-Cut解法を提案する。
論文 参考訳（メタデータ） (2023-11-26T07:11:58Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - Quantum Speedup for the Maximum Cut Problem [6.588073742048931]
古典的なグラフに対して2次スピードアップを施した任意のグラフ$G$に対する最大カット問題を解く量子アルゴリズムを提案する。
NP完全問題に対するオラクル関連量子アルゴリズムについて,本アルゴリズムを最適とみなす。
論文 参考訳（メタデータ） (2023-05-26T05:31:25Z) - Dr. KID: Direct Remeshing and K-set Isometric Decomposition for Scalable
Physicalization of Organic Shapes [5.385289130801911]
KID(Dr. KID)は、ジャガイモ形有機モデルの物理化に等尺分解を用いるアルゴリズムである。
クラスタリングには、距離関数として定義される三角形間の類似性が必要である。
よりスムーズな結果を得るために、三角形の分割と曲率を意識したクラスタリングを用い、3Dプリンティングのために曲面の三角形パッチを生成する。
論文 参考訳（メタデータ） (2023-04-06T08:56:18Z) - CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes [62.45415756883437]
多重非剛性な3次元形状の整合性は困難で、$mathcalNP$-hard問題である。
既存の量子形状マッチング法は複数の形状をサポートしておらず、サイクルの整合性も低い。
本稿では,3次元形状のマルチマッチングのための最初の量子ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2023-03-28T17:59:55Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。
エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。
提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
論文 参考訳（メタデータ） (2022-05-30T14:28:02Z) - A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D
Shape Matching [69.14632473279651]
本稿では,3次元形状間の幾何学的一貫したマッピング空間をグローバルに最適化するスケーラブルなアルゴリズムを提案する。
従来の解法よりも数桁高速なラグランジュ双対問題と結合した新しい原始問題を提案する。
論文 参考訳（メタデータ） (2022-04-27T09:47:47Z) - Quasi-polynomial time approximation of output probabilities of
geometrically-local, shallow quantum circuits [0.0]
本稿では,任意の3次元局所多元数量子回路に対する古典的アルゴリズムを提案する。
準多項式時間における任意の逆多項式加法誤差に$| x |C|0otimes n>|2$を演算する。
論文 参考訳（メタデータ） (2020-12-10T05:19:29Z) - Lazy Online Gradient Descent is Universal on Polytopes [1.2691047660244335]
ポリトープドメイン上では、よく知られたLazy Online Gradient Descentアルゴリズムが普遍的であることを証明している。
つまり、i.i.d の相手に対して$O(1)$の擬似レグレットを得ると同時に、よく知られた$O(sqrt N)$最悪の後悔境界を達成できる。
論文 参考訳（メタデータ） (2020-04-03T19:00:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。