322 名前： 名無し名人 [sage] 投稿日： 2013/04/20(土) 07:28:41.18 id:PL9LsIG/
>>321
オーダリングの完成度が高いということは、
探索の根の子ノードのうち、どれが最良ノードか非常に高い確率で言い当てられるのと同義である
このことから、最良ノードと目される子と、そうでない子とを相違するCPUに割り当てて並列探索させた場合、
一切無駄が生じないことが導かれる
なぜなら、最良の子ノードと最良でない子ノードとで、葉が一致するとしたら最良 v.s. 最良以外という仮定に矛盾するので
ハイ論破
ちなみに、√Nというのは(0, 1)ランダムウォークN歩で達成しえる出発地点からの距離の期待値でもあり、
ということは、N個のCPUそれぞれについて、有効な仕事をしたとき+1、そうでないとき（他のCPUと重複する仕事をしたとき)を
0と得点づけたときのトータルの得点の期待値に等しい
323 名前： 名無し名人 [sage] 投稿日： 2013/04/20(土) 07:38:22.44 id:PL9LsIG/
んで、以上はN CPUの並列探索でN倍を達成しえることを述べたが、
探索木の部分木の葉の数にばらつきがある場合、ある部分木の探索を終えたCPUを
すかさず他の部分木の探索に投入することでN倍以上の効率を達成できることがある
なぜなら、他のCPUが部分木1個の探索をしている間にそのCPUは1個超の探索木を探索することになるので
（簡単のため、割り当てる探索木の深さを一定とした議論だが
