loader gif

petapeta:hirax.net::サンタが街にやってくる::(2001.12.24) 複数サンタがいるときの 子供の家N=…

petapeta:

hirax.net::サンタが街にやってくる::(2001.12.24)

複数サンタがいるときの
子供の家N=100までの場合のサンタが計算しなければならない経路の総数
横軸=N、縦軸=計算しなければならない経路数
黒=サンタが一人
緑=サンタが二人
紫=サンタが十人

このグラフからサンタが複数いる場合と、単独の場合とで巡回経路を考える手間が全然違うのがわかるだろう。サンタが2人いると、計算量は半分になるのではなく、ものすごく少なくなるのである。

 実際の巡回においての仕事量は、サンタがm人いれば1/mになる。しかし、その前準備はサンタがm人いれば((N-1)!/2)/(m*(N/m-1)!/2)分の一になるのだ。簡単に言えば、メチャクチャ楽になるのだ。サンタが一人では事実上サンタがプレゼントを配ることは不可能だけれど、複数犯であれば容易にプレゼントを配ることができるのだ。

 このように「複数サンタクロース巡回問題」を考えることにより、サンタは複数いることが明らかだと私は思うのだ。

コメントを残す

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください