論文の概要: Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds

• arxiv url: http://arxiv.org/abs/2410.14947v1
• Date: Sat, 19 Oct 2024 02:34:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:16:31.545915
• Title: Optimally Solving Colored Generalized Sliding-Tile Puzzles: Complexity and Bounds
• Title（参考訳）: 色付き一般化スライディングタイルノズルの最適解法:複雑さと境界
• Authors: Marcus Gozon, Jingjin Yu,
• Abstract要約: GSTP (Generalized Sliding-Tile Puzzle) は、ボード上の多くの正方形タイルを平行に移動させ、隣接するタイルの運動に自然な幾何学的衝突制約を課す。 この研究は、CGSP (Colored Generalized Sliding-Tile Puzzle) と呼ばれるGSTPのさらなる一般化を検証し、タイルは様々な区別可能性を持つようになった。 本研究は、CGSPとその鍵となるサブプロブレムの計算複雑性を、可能条件の幅広いスペクトルの下で確立し、ほとんどの対数係数によって異なる解が下限と上限を特徴づけるものである。
• 参考スコア（独自算出の注目度）: 17.720810091374776
• License:
• Abstract: The Generalized Sliding-Tile Puzzle (GSTP), allowing many square tiles on a board to move in parallel while enforcing natural geometric collision constraints on the movement of neighboring tiles, provide a high-fidelity mathematical model for many high-utility existing and future multi-robot applications, e.g., at mobile robot-based warehouses or autonomous garages. Motivated by practical relevance, this work examines a further generalization of GSTP called the Colored Generalized Sliding-Tile Puzzle (CGSP), where tiles can now assume varying degrees of distinguishability, a common occurrence in the aforementioned applications. Our study establishes the computational complexity of CGSP and its key sub-problems under a broad spectrum of possible conditions and characterizes solution makespan lower and upper bounds that differ by at most a logarithmic factor. These results are further extended to higher-dimensional versions of the puzzle game.
• Abstract（参考訳）: Generalized Sliding-Tile Puzzle (GSTP)は、ボード上の多くの正方形タイルを平行に移動させ、隣接するタイルの動きに自然な幾何学的衝突制約を課し、移動ロボットベースの倉庫や自律型ガレージなど、多くの高実用性と将来のマルチロボットアプリケーションに対して高忠実な数学的モデルを提供する。 実用的関連性によって動機づけられたこの研究は、CGSP (Colored Generalized Sliding-Tile Puzzle) と呼ばれるGSTPのさらなる一般化を検証し、タイルは上記のアプリケーションでよく見られる、様々な区別可能性を持つようになった。 本研究は、CGSPとその鍵となるサブプロブレムの計算複雑性を、可能条件の幅広いスペクトルの下で確立し、少なくとも対数係数によって異なる解の配向と上界を特徴づけるものである。 これらの結果はより高次元のパズルゲームに拡張される。

関連論文リスト

• Transolver: A Fast Transformer Solver for PDEs on General Geometries [66.82060415622871]
  本稿では, 離散化された測地の背後に隠れた本質的な物理状態を学習するTransolverについて述べる。 スライスから符号化された物理認識トークンに注意を向けることで、Transovlerは複雑な物理的相関を効果的に捉えることができる。 Transolverは6つの標準ベンチマークで22%の相対的な利得で一貫した最先端を実現し、大規模産業シミュレーションでも優れている。
  論文  参考訳（メタデータ） (2024-02-04T06:37:38Z)
• 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)
• Higher-order Graph Convolutional Network with Flower-Petals Laplacians on Simplicial Complexes [5.838832985156104]
  FPラプラシアンをsimplicial Complex(SC)に組み込んだ高次フラワー・ペタールス(FP)モデルを提案する。 また、FPラプラシアンを基盤とした高階グラフ畳み込みネットワーク(HiGCN)を導入し、様々な位相スケールで固有の特徴を識別する。 HiGCNは、様々なグラフタスクにおける最先端のパフォーマンスを達成し、グラフにおける高次相互作用を探索するためのスケーラブルで柔軟なソリューションを提供する。
  論文  参考訳（メタデータ） (2023-09-22T16:11:17Z)
• Explainable Equivariant Neural Networks for Particle Physics: PELICAN [51.02649432050852]
  PELICANは、新しい置換同変であり、ローレンツ不変アグリゲーターネットワークである。 本稿では,タグ付け(分類)とローレンツ発泡トップクォークの再構成(回帰)の両文脈におけるPELICANアルゴリズムアーキテクチャについて述べる。 PELICANの適用範囲を、クォーク開始時とグルーオン開始時とを識別するタスクに拡張し、5種類のジェットを対象とするマルチクラス同定を行う。
  論文  参考訳（メタデータ） (2023-07-31T09:08:40Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  3つの代表的構成課題にまたがる変圧器大言語モデルの限界について検討する。 これらのタスクは、問題をサブステップに分割し、これらのステップを正確な答えに合成する必要があります。 実験結果から,多段階合成推論を線形化部分グラフマッチングに還元することにより,トランスフォーマーLLMが構成課題を解くことが示唆された。
  論文  参考訳（メタデータ） (2023-05-29T23:24:14Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。 この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
  論文  参考訳（メタデータ） (2023-03-26T18:53:51Z)
• Solving High-Dimensional PDEs with Latent Spectral Models [74.1011309005488]
  我々は,高次元PDEの効率的かつ高精度な解法に向けて,Latent Spectral Models (LSM) を提案する。 数値解析において古典スペクトル法に着想を得て,潜時空間におけるPDEを解くために,ニューラルスペクトルブロックを設計する。 LSMは、一貫した最先端を実現し、7つのベンチマークで平均11.5%の相対的な利益を得る。
  論文  参考訳（メタデータ） (2023-01-30T04:58:40Z)
• Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw Puzzles [67.39567701983357]
  ビデオ異常検出(VAD)はコンピュータビジョンにおいて重要なトピックである。 近年の自己教師型学習の進歩に触発された本論文は,直感的かつ難解なプレテキストタスクを解くことによって,VADに対処する。 提案手法は3つの公開ベンチマークにおいて最先端のベンチマークよりも優れている。
  論文  参考訳（メタデータ） (2022-07-20T19:49:32Z)
• TEN: Twin Embedding Networks for the Jigsaw Puzzle Problem with Eroded Boundaries [0.0]
  ジグソーパズル問題(JPP)は、長年研究されてきたよく知られた研究問題である。 片端情報のみに基づく簡易距離測定を応用した実効CMが多数提案されている。 しかし、これらの古典的手法の実用性は、純粋な合成画像よりも難しい問題に対してかなり疑わしい。 この重要な欠陥を克服するために、いくつかの深層畳み込みニューラルネットワーク(CNN)ベースのCMが最近導入されている。 この論文は、(古典的手法の)比較的低い精度と集中的な計算複雑性の間のギャップを埋めるための重要な最初の試みである。
  論文  参考訳（メタデータ） (2022-03-12T17:18:47Z)

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

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