クリスマスイブに夜空を飛んでいるサンタクレジット：Wave—Getty Images / iStockphotoサンタクロースは1年に1日しか働かないかもしれませんが、サンタを追いかけようが下に示すように、それは仕事の面倒です。クリスマスの真夜中から、彼は目を覚ます前に何百万人もの行儀の良い子供たちに手を差し伸べなければなりません。ある見積もりでは、 世界には5億2600万人のキリスト教徒の子供たちがいます サンタさんの顧客リストはもっと多いかもしれませんが、12月25日にクリスマスを祝う14歳未満の人。 2013年のピュー研究所の調査によると、少なくともアメリカでは、 非キリスト教徒の81％もこの機会を観察しています 。
サンタさんのトナカイは速いかもしれませんが、すべての家を時間内に攻撃したい場合は、効率的でなければなりません。 （おそらく、博士号を持つエルフが一年中シミュレートされたルートを実行する北極にR＆Dラボがあります。）彼らを助けるために、私たちはサンタ追跡を構築し、サンタが最小化するために取ることができる米国本土を通る最適なルートを計算しました空中での彼の合計時間。どちらも NORADとGoogle また、サンタのルートを追跡し、彼が世界中を旅していることを示していますが、その方法論はあまり明確ではありません。 グーグルは説明します サンタを追いかけようが「サンタの旅をグラフ化するための新しいルートアルゴリズム」のみを使用していることだけです。
では、サンタは今どこにいますか？サンタを追いかけようで、3,108の郡を通るサンタの全経路を表示し、サンタがいつあなたの郡に到着するかを正確に知ることができます。
サンタの理想的な道をたどるのは特に難しい問題ではないように思われるかもしれませんが、100年近く数学者を悩ませてきた問題です。難問は 'として知られています 巡回セールスマン問題 、 '巡回セールスマンは、地域のさまざまな都市を訪問する必要があり、外出中の時間を最小限に抑えたいと考えています。それらの都市が円状にきちんと配置されていないと仮定すると、彼が各場所に移動する順序を計算することは、完全な解決策がない問題のままです。ほんの数都市の場合、考えられるすべての組み合わせ間の合計距離を簡単に計算できます。 3,108の郡になると、 可能なルートの数 1,568の後に9,500個のゼロが続きます。
サンタ追跡のトラベリングサンタ問題を解決するために、理想的なルートを見つけるために4つの異なるアルゴリズムを使用して何百ものシミュレーションを実行しました。 （ そうするためのコード はオープンソースであり、十分に文書化されています。）各シミュレーションで、サンタは メイン州アルーストック郡 、米国で最も北東にある郡—おそらく彼は北極から来てカナダを最初に襲った可能性があります—そして最後は南西部の郡であるサンディエゴで終わり、そこで彼はメキシコに向かうか、次に進むように配置されます。ハワイへ。上に表示されている最適なパスは、各郡を訪問するためにわずか88,639マイルになりました。
次に、各郡内のすべてのプレゼントを配達するためにサンタがどれだけ移動する必要があるかを把握する必要がありました。最新の国勢調査データを使用して、9歳以下の子供たちの数を検討しました。 サンタへの信念は劇的に低下します —各郡に住んでいて、 90％がクリスマスを祝った 、ピュー研究所が発見したように。それは3600万人の子供たちにもたらされました。それから私達は サンタが移動しなければならない距離を推定 人口が全土地面積に均一に分布していると仮定すると、郡内でそれらすべてに到達します。プレゼントを届けるためにすべての移動時間を追加すると、サンタを追いかけようのサンタの最適な合計ルートは6,880,123マイルになります。
それで、それは彼にどれくらい時間がかかりますか？それは、サンタがターボチャージャー付きのそりでどれだけ速く進むことができるかに依存します。毎秒930マイルの任意の速度で—それは 光の速度 、それは合理的なようです—彼は2時間3分で国を縦横無尽に横断することができます。
この計算は厳密にチェックされ、このレポーターのMacbookをほとんど食い尽くしました（ Githubでコードを見つけます ）、いくつかの方法で見積もりをさらに絞り込むことができます。 国勢調査区データ サンタが各郡内を移動する必要がある距離の見積もりを改善する可能性があります。 少年犯罪率 そもそも訪問を受ける資格のある子供の数を減らす可能性があります。誰かがまだ石炭を降ろさなければならないけれども。旅行にご期待ください クランプス 問題。
この物語はもともと登場しました 時間