論文の概要: Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches

• arxiv url: http://arxiv.org/abs/2610.31100v1
• Date: Thu, 22 Oct 2026 11:13:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-24 02:08:44.33269
• Title: Solving Flood-It Puzzles: A Comparison of Tailored A* Search with Declarative Solver Approaches
• Title（参考訳）: フラッドイットパズルの解法: テーラー付きA*探索と宣言的解法の比較
• Abstract要約: そこで我々はFlood-Itパズルを解くために最小の移動列を求める最適化手法を提案する。 SAT、プログラミング、制約プログラミングを用いたアプローチと比較する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We present an optimized approach for finding minimal move sequences to solve Flood-It puzzles using A* search and compare it with approaches using SAT, Integer Programming, and Constraint Programming solvers. The performance of A* search is considerably improved by using an appropriate heuristic and sophisticated equivalences of game states to limit the search space. Each aspect is systematically evaluated, providing insights that generalize to other problems. By comparing the best variant of each approach, the A* search is the fastest in finding a minimal solution in about 75 % of the Flood-It instances tested. This result is in line with our expectation since A* specifically looks for a minimum solution. In contrast, the SAT-based approach is designed to solve the decision problem of whether a solution with a given length exists. An iterative search is required to determine a minimum solution length using a SAT-based approach. However, with increasing complexity, quantified by the minimum solution length, the SAT-based approach outperforms A*. We also compared the different approaches to the decision problem, where A* again performed best for the largest number of puzzles. Here, again, SAT supersedes A* for higher complexities, albeit with a lower crossing point.
• Abstract（参考訳）: 本稿では,A*探索を用いてFlood-Itパズルを解くための最小の移動列を見つけるための最適化手法を提案する。 A*探索の性能は、ゲーム状態の適切なヒューリスティックで洗練された等価性を用いて大幅に改善され、探索空間が制限される。 各側面は体系的に評価され、他の問題に一般化する洞察を提供する。 各アプローチの最良のバリエーションを比較することで、A*検索はテストされたFlood-Itインスタンスの約75%で最小限のソリューションを見つけるのに最速である。 A* は最小解を特に求めているので、この結果は我々の期待と一致している。 対照的に、SATベースのアプローチは、与えられた長さの解が存在するかどうかという決定問題を解くために設計されている。 SATベースのアプローチを用いて最小解長を決定するためには反復探索が必要である。 しかし、最小解長で定量化される複雑さが増大すると、SATベースのアプローチはA*よりも優れる。 また、A* が最大数のパズルに対して最善を尽くした決定問題に対して、異なるアプローチを比較した。 ここでも、SAT は A* を高い複素数に対して置き換えるが、交差点は低い。

関連論文リスト

• Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers [52.23061619664667]
  大規模言語モデル(LLM)は直接推論によって複雑な問題を解くのに苦慮しているため、近年のニューロシンボリックシステムは、それを実行可能な解法を合成するためにますます利用している。 我々は,100の問題をベンチマークしたCP-SynC-XL(4,577インスタンス)を導入し,ネイティブアルゴリズム検索(Python),PythonソルバAPI(Python + OR-Tools)による制約モデリング,宣言的制約モデリングという3つのコンストラクションパラダイムを評価した。
  論文  参考訳（メタデータ） (2026-05-12T17:15:45Z)
• Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints [0.0]
  NP完全満足度問題 3-SAT の局所探索を導入,ベンチマークする。 私たちの建設は、WalkSATのような確立した従来のアプローチが、地元のミニマで立ち往生する傾向にあるという決定的な観察に基づいています。 我々は,N=15000までの様々な問題サイズを持つ3SATインスタンスをランダムに生成したサンプルを用いて,アルゴリズムを解析・ベンチマークする。
  論文  参考訳（メタデータ） (2025-06-18T18:00:01Z)
• Resource-Constrained Heuristic for Max-SAT [0.848762374187855]
  より大規模な問題をより小さなサブコンポーネントに繰り返し分解する,Max-SATのインスタンスに対するリソース制約を提案する。 本研究では,所定のSATインスタンスの構造を利用するグラフベースの新しい手法を含む,変数選択手法の集合を分析する。 我々は,Max-SAT評価ベンチマークを用いて,ランダムに生成されたMax-SATインスタンスと実世界の実例について実験を行った。
  論文  参考訳（メタデータ） (2024-10-11T18:20:08Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Rethinking the Soft Conflict Pseudo Boolean Constraint on MaxSAT Local Search Solvers [20.866863965121013]
  MaxSATは、有名なNP完全満足度問題(SAT)の最適化版である。 そこで我々は,SPB-MaxSATと呼ばれる局所探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-19T09:59:02Z)
• General Method for Solving Four Types of SAT Problems [12.28597116379225]
  既存の方法は、様々なタイプのブール適合性問題(SAT)に対して様々なアルゴリズムを提供する。 本研究では,整数計画法と強化学習法(RL)に基づく統合フレームワークDCSATを提案する。
  論文  参考訳（メタデータ） (2023-12-27T06:09:48Z)
• Decomposing Hard SAT Instances with Metaheuristic Optimization [52.03315747221343]
  分解硬度(d硬度)の概念を導入する。 d-硬度が$C$ w.r.tの硬度の推定値を示すことを示す。
  論文  参考訳（メタデータ） (2023-12-16T12:44:36Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Incomplete MaxSAT Approaches for Combinatorial Testing [0.0]
  本稿では,最小長の制約付き混合被覆アレイを構築するためのSAT(Satifiability)に基づくアプローチを提案する。 この問題はシステム障害検出のためのコンビネータテストの中心である。
  論文  参考訳（メタデータ） (2021-05-26T14:00:56Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。 我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
  論文  参考訳（メタデータ） (2020-01-29T09:40:58Z)

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

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