■コマネチ大学数学科33講：中国人郵便配達問題

シャブリの気になったもの：コマネチ大学#33

酔いつぶれて録画予約を失敗してしまった「コマネチ大学数学科」だが、上記のブログに問題と、非常に丁寧な解説が載っていた。詳細は上記ブログを参照してもらうとして、酔っ払い爺としては、実践あるのみ。ホントにそうなのかを検証してみよう。

「スタート」ボタンを押してから、キーボードの方向キーで郵便配達夫を操作してほしい。

問題は「郵便局から出発して、すべての家に郵便物を配達し、再び、郵便局に戻る、この間の移動距離が最小となるような経路を見つけよ！というもの。小さいひとマスの辺を「1」としたとき、最短経路の移動距離を求めることになる。

で、経路を最短にするには、できるだけ、同じ道を通らないこと。一筆書きができれば（無駄な移動を省くという意味で）それに越したことはないのだが、どうやら、この図形は一筆書きができない。ならば、どうすればよいのか、というのが、この問題のポイントだ。

重複して通る経路をどこにするか。「ケーニヒスベルクの橋」問題で、オイラーは、一筆書きができる必要十分条件として、「すべての頂点の次数が偶数」または「次数が奇数の頂点の数が２で、残りの頂点の次数はすべて偶数」のいずれかとした。つまり、奇数点を偶数にすれば、いいんだよね。そう考えると、自ずとバイパスを設置するポイントが見えてくる。

そんなわけで、パターンを知ってしまうと、意外と簡単な問題。このバイパスを設置する(二度通る経路を決める)と、スタート地点がどこにあろうが、最短距離ですべての家に郵便物を配達できる。この問題の答え（1マスの辺を1とすると)、最短距離「28」で、すべての家に郵便物を届け、出発点の郵便局に戻ってほしい。