今日の一言/2011-2-16

パズル--点独--

ちょっと息抜き．次のパズルを解いてみよう．

右のようにある○と□が線でつながれている絵があって，その中の□を■に変える．ルールは次のとおり．

1. ○や●の部分は何もしない．
2. 色を塗っていない□は必ず塗った■や既に塗られている●と線で結ばれている．
   • ■のとなりを■に塗ってもよい．
3. できるだけ色を塗る数は少なくする．
   • 例えば全ての□を塗りつぶしても上のルールは満たされるがそれはつまらない．できるだけ少なくすることがポイントである．その個数はここでは教えないことにする．

□と○は■や●に囲まれている，つまり□や○の点は独りぼっちにするという意味で点独と名づけた．数独は数字を置くが，それよりも単純で色を塗るかぬらないかのパズル．

• この絵のPDFファイル：sample0128935000-puzzle.pdf(118)
• ちなみにこの絵はGraphvizをつかって書いた．そのdotファイル：sample0128935000-puzzle.dot(118)

少し学問的?な話をすると，これはVertex coverやIndependent setと呼ばれる制約充足問題である．グラフ構造として，結合数が３のregular random graphの例を示している．多くの制約充足問題は制約可能相では一般にnode数の指数関数ほどの解が存在する．そのために，唯一の答えを探すパズルにはならない．しかし，全てのminimal vertex cover(maximum independet set)解に共通であるバックボーンと呼ばれる部分が有限の割合で存在することがわかっていて，それをパズルとしてみた．あらかじめ○印で示されているところはバックボーンでない部分であり，それをヒントとして示してある．

• この問題はノード数128で，その程度のノード数の場合は厳密に調べる方法を使うことができる．さらにノードの二乗程度の手続きでバックボーンを求めることもできる．ここでは，ざっくりモンテカルロ法で最小coverを作り出して，XORをとってバックボーンを探した．おそらく正しく求まったと思っているが，そうでないとしたら敗北…．

結合数３の問題は58.5%ほど色を塗ったところで，レプリカ対称性の破れる(RSB)相転移を示すことがわかった．この結果はすでに知られていると思うのだが，それに対応する相図(結合数-密度）は見たことがない．ちゃんと論文書いた方がいいかな．

• RSBといってもちゃんとRSBを調べたわけではないことは言っておくべきです．いわゆる，linear不安定化ではないinhomogeneity不安定化条件から出した境界で，確かにそこで解間距離分布が均一ではなくなることがわかる．でも，これだけバックボーンがあって，それでも解空間がぼこぼこできるのか？という疑問がでてくるが，上の○印部分の相関が重要となる．これがZhou氏の言うlong range frustrationというやつだけど，その言い方がよいのかどうかはわからん．