場の理論と統計力学の方法の計算量的に困難な問題の解析への応用

场论和统计力学方法在计算难题分析中的应用

• 批准号: 15740159
• 负责人: 樋口 三郎
• 金额: $ 1.09万
• 依托单位: Ryukoku University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 2005
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-15740159/
• 关键词: 最適化; さめがめ; 統計力学; アルゴリズム; ナンバープレイス; 数独; 格子モデル; 組み合せ論; 計算の複雑さ; ナンバープレース; 15パズル; 分枝限定法; デザイン; 計算量; NP完全性; 相転移; 密度行列くりこみ群; SAT; マッチング; 組み合わせ論; O(n)ループ模型

共同研究者とともに,ナンバープレース(数独)と呼ばれる組み合わせパズルを統計力学的に解析した.ナンバープレースは,定義域である有限集合とその部分集合族が与えられたとき,別の有限集合を値域とするある条件をみたす写像を見いだす問題である.標準的な9×9のナンバープレイスを一般化したものを考えたとき,すでに知られている標準的なものに対する解探索アルゴリズムがどのように一般化されるかを考察した.標準的な場合には,空でない共通部分を持つ部分集合は最大3個だが,この上限を増やす一般化をした場合にも,アルゴリズムは最大3個の場合の自然な拡張が最良であることを示唆する結果を得た.ナンバープレースの解の個数を,マルチカノニカルモンテカルロシミュレーションによって数値的に評価することをめざし,予備的な解析を行った.共同研究者とともに,さめがめと呼ばれる組み合わせパズルを統計力学的に解析した.これは,格子の各点が,n色のうちのひとつの状態をとるようなモデルで,プレイヤーがひとつのクラスターを選択すると,特定のルールに基づいてアップデートがかかるようなものである.有限サイズにおいてランダムに定めた様々な初期状態から分枝限定法でゴールとされる状態に達する手順を探索し,達することができる確率を数値的に評価した.この結果は,ゲームにおける最適な戦略を推定するのに有益な情報である.また,補外によって,無限サイズ極限における性質を推定した.

我和我的合作者一起统计分析了一个称为数位 (Sudoku) 的组合难题。数位是一个称为数位 (Sudoku) 的组合难题。给定一个有限集作为域及其子集族，数位是一种方法将另一个有限集划分为一系列值的问题是找到满足某些条件的映射。当我们考虑标准 9x9 数字位置的广义版本时，我们考虑了解搜索算法如何推广到标准情况。在标准情况下，最多有 3 个具有非空公共部分的子集，但即使当解数为 时，我们也可以增加此上限。我们进行了初步分析，目的是使用 Cal Monte Carlo 模拟对其进行数值评估，当玩家在模型中选择一个处于以下状态之一的集群时，我们使用统计力学分析了一个名为 Samegame 的组合谜题。 ，玩家根据特定规则选择一个簇。我们使用分支定界法从有限大小的各种随机确定的初始状态中搜索达到目标状态的过程，并数值评估达到目标状态的概率。该结果对于估计最优策略是有用的信息。在游戏中。此外，通过外推，我们估计了无限大小极限下的属性。