- 追加された行はこのように表示されます。
- 削除された行は
このように表示されます。
!!パズル--点独--
ちょっと息抜き．次のパズルを解いてみよう．
{{div style,float:right;,"{{ref_image sample0128935000-puzzle.jpg}}"}}
右のようにある○と□が線でつながれている絵があって，その中の□を■に変える．ルールは次のとおり．
+○や●の部分は何もしない．
+色を塗っていない□は必ず塗った■や既に塗られている●と線で結ばれている．
**■のとなりを■に塗ってもよい．
+できるだけ色を塗る数は少なくする．
**例えば全ての□を塗りつぶしても上のルールは満たされるがそれはつまらない．できるだけ少なくすることがポイントである．その個数はここでは教えないことにする．
□は■や●に囲まれている，つまり□の__点__は__独__りぼっちにするという意味で点独と名づけた．数独は数字を置くが，それよりも単純で色を塗るかぬらないかのパズル．
□と○は■や●に囲まれている，つまり□や○の__点__は__独__りぼっちにするという意味で点独と名づけた．数独は数字を置くが，それよりも単純で色を塗るかぬらないかのパズル．
*この絵のPDFファイル：{{ref sample0128935000-puzzle.pdf}}
*ちなみにこの絵はGraphvizをつかって書いた．そのdotファイル：{{ref sample0128935000-puzzle.dot}}
少し学問的?な話をすると，これは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というやつだけど，その言い方がよいのかどうかはわからん．