okkyの日記： 【緩募】Travelling Santa Problem を解く方法 1
同名の問題に関しては末尾を参照の事。
サンタクロースは今年も子供たちにプレゼントを届けたに違いない。
https://srad.jp/~okky/journal/521678/によれば、サンタクロースは光速の 1/3 までは出せるようなので、おそらくまださほど難しい問題ではなかったのではないかと思われる。とはいえ、あまりにも無駄だらけなコース選定と言うわけにはいかないだろう。彼はこのコースをどのように算出したのだろうか…
----
サンタクロースが従わなくてはいけない制約条件はいくつもある。
- サンタの移動速度は光速の 1/3 までとする
これは多分本当はもっと出せるんだろうが、とりあえずそういう制約を付ける事にしよう。
- 北極基地を出発点とし、北極基地を終点としなくてはいけない。
これは言わずもがなだろう。流石に最後の一軒にプレゼントを届けたらそのまま溶けて消えても構わない、と言うわけにはいくまい。
その意味ではこれは Travelling Salesman Problem の一種である。
- 2020年の段階でも 13.4億人の子供たちに配る必要がある。
世界の人口ピラミッドと言うページがある:
https://www.populationpyramid.net/ja/%E4%B8%96%E7%95%8C/2020/
ここから得られるデータによると、2020年の10歳未満の子供の総数は大雑把に13.4億人いる。
サンタクロースはこれらの子供全てにプレゼントを届けなくてはいけない、としよう。
(10歳以上の子供を含めてはいけない、と言う意味ではない。単に上記のページのデータが5歳刻みで、流石に14歳におもちゃを届けるのはサンタクロース的にどうかな、と言うだけの話だ)。
さらに言えば、人口は全体的にまだ増え続けているので、子供の総数はもうしばらくの間増え続けると思われる。
- 子供たちが寝ている間にプレゼントを配らなくてはいけない。
これはこのままでは制約条件として曖昧過ぎるので、こう言い換えよう。
「各子供がいる現地時間の 12月24日21:00 以降、 12月24日06:00 までにプレゼントを届ける必要がある」
Wikipediaによるとhttps://ja.wikipedia.org/wiki/%E5%B9%B4%E8%B6%8A%E3%81%97:
『キリバスとサモアが最も早く新年を迎える国であり、ハワイ州ホノルルが最後の地域である[2]。』
とある。
キリバスのライン諸島は UTC+14
ハワイ州ホノルルはUTC-10
だそうなので、サンタクロースは
「Timezone による24時間」 + 「21:00 - 翌06:00までの 9時間」
の合計33時間が与えられている。この間に(制約条件を満たしつつ)すべての子供たちにプレゼントを配布する必要がある。
- 子供たちは移動中ではない、としよう。
計算が大変だから。ただし、12月24日午前09:00までは全ての子供たちの位置は確定しないものとする。それまでは12月23日はどこで就寝したのか、と言う情報を「翌日の就寝場所に関する不確定なヒントとしてのみ」与えられるものとする。
タイムゾーンを考えると、全ての子供たちの位置が一斉に確定するわけではない、と言う点は考慮に入れる必要がある。
これらの制約条件をすべて満たしつつ、可能な限り最短の移動距離でサンタはプレゼントを配ったに違いあるまい。
では、サンタはどのようにしてこの経路を算出したのだろう?
- 事前計算として何か計算しておくと都合がよいものはあるだろうか?
記憶容量は無制限だとしよう。
- 並列処理できる何かはあるだろうか?
- 当然、サンタはプレゼントを配りながら後半の移動経路を計算し続けていたに違いない。と言うか「サンタは」ではなく、「サンタ支援協会は」なのかもしれない。
はて。Googleが持っている全計算機を投入すれば間に合うように経路算出できるだろうか…。
【同名の問題】
多分その条件に淡々と従うと計算不能 (スコア:1)
また、期限切れ時間のε時間前 (εは任意）に生まれる子の位置情報が事前に提供されないなら、そもそも配ることも多分不可能。