論文の概要: Solving N-Queen Problem using Las Vegas Algorithm with State Pruning

• arxiv url: http://arxiv.org/abs/2512.04139v1
• Date: Wed, 03 Dec 2025 16:36:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-05 21:11:45.811856
• Title: Solving N-Queen Problem using Las Vegas Algorithm with State Pruning
• Title（参考訳）: State Pruning を用いた Las Vegas アルゴリズムによるN-Queen 問題の解法
• Authors: Susmita Sharma, Aayush Shrestha, Sitasma Thapa, Prashant Timalsina, Prakash Poudyal,
• Abstract要約: N-クイーン問題(N-Queens problem)は、NxNのチェスボードにNのクイーンを配置する問題であり、制約満足度アルゴリズムの古典的な問題である。 本研究では,ラスベガスの標準フレームワーク上に,反復刈り込みによるハイブリッドアルゴリズムを導入する。
• 参考スコア（独自算出の注目度）: 2.011708578491462
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The N-Queens problem, placing all N queens in a N x N chessboard where none attack the other, is a classic problem for constraint satisfaction algorithms. While complete methods like backtracking guarantee a solution, their exponential time complexity makes them impractical for large-scale instances thus, stochastic approaches, such as Las Vegas algorithm, are preferred. While it offers faster approximate solutions, it suffers from significant performance variance due to random placement of queens on the board. This research introduces a hybrid algorithm built on top of the standard Las Vegas framework through iterative pruning, dynamically eliminating invalid placements during the random assignment phase, thus this method effectively reduces the search space. The analysis results that traditional backtracking scales poorly with increasing N. In contrast, the proposed technique consistently generates valid solutions more rapidly, establishing it as a superior alternative to use where a single, timely solution is preferred over completeness. Although large N causes some performance variability, the algorithm demonstrates a highly effective trade-off between computational cost and solution fidelity, making it particularly suited for resource-constrained computing environments.
• Abstract（参考訳）: N-クイーン問題(N-Queens problem)は、NxNのチェスボードにNのクイーンを配置する問題であり、制約満足度アルゴリズムの古典的な問題である。 バックトラックのような完全な手法では解が保証されるが、その指数時間的複雑性は大規模なインスタンスでは非現実的であるため、ラスベガスのアルゴリズムのような確率的アプローチが好まれる。 より高速な近似解を提供するが、ボード上にクイーンがランダムに配置されているため、大きなパフォーマンスのばらつきに悩まされる。 本研究は, ラスベガスの標準フレームワーク上に, 反復刈り込みによるハイブリッドアルゴリズムを導入し, ランダム割り当てフェーズにおける不正配置を動的に排除し, 探索空間を効果的に削減する手法である。 対照的に、提案手法は有効解をより高速に生成し、単一でタイムリーな解が完全性よりも好まれる場合に、より優れた代替手段として確立する。 大きなNはいくつかの性能変動を引き起こすが、このアルゴリズムは計算コストと解の忠実度の間に非常に効果的なトレードオフを示し、特に資源制約のある計算環境に適している。

関連論文リスト

• A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
  短期的ハードウェア制限を軽減するために設計されたQAOAの変種であるIterative-QAOAを紹介する。 我々は,Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) のインスタンスをIonQ Forte Generation QPU上でベンチマークする。 反復-QAOAは、評価された全ての問題インスタンスに対して、最適解と高品質でほぼ最適解を見つけるために、しっかりと収束していることがわかった。
  論文  参考訳（メタデータ） (2025-10-30T16:14:13Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Mining Large Independent Sets on Massive Graphs [47.21699378695116]
  ARCISは、巨大なグラフ上の大きな独立した集合をマイニングするための効率的なアルゴリズムである。 ARCISは、ほとんどのインスタンスで最高の、または最も結びついたソリューション品質が得られることを示す。
  論文  参考訳（メタデータ） (2022-08-16T14:39:38Z)
• Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization [13.170519806372075]
  2組の制約を持つ凸最適化の問題は、半定値プログラミングの文脈で頻繁に発生する。 最初の制約セットへのプロジェクションは困難であるため、プロジェクションフリーなアルゴリズムを探索する必要がある。 提案アルゴリズムの有効性は, スパース行列推定, 半定緩和によるクラスタリング, および一様スペースカット問題の適用性について検証した。
  論文  参考訳（メタデータ） (2021-07-14T08:01:30Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Quasi-Newton Solver for Robust Non-Rigid Registration [35.66014845211251]
  データフィッティングと正規化のための大域的スムーズなロバスト推定器に基づくロバストな非剛性登録のための定式化を提案する。 本稿では,L-BFGS を用いた最小二乗問題の解法に,各繰り返しを減らし,最大化最小化アルゴリズムを適用した。
  論文  参考訳（メタデータ） (2020-04-09T01:45:05Z)

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

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