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

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

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

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

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

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

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

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

“■コマネチ大学数学科33講:中国人郵便配達問題” への2件の返信

  1. 初めまして、シャブリです。
    TBありがとうございました。
    私の偏狭ブログを見つけてくださり、
    こんな形で紹介されて、いやはや、とても嬉しい限りです。
    早速、ゲームをやりました。よく出来てますね。
    答えを知っているので、いろんな道順で試してみて楽しみましたよ!(resetはre-loadで…)
    コマネチ大学は初回から見ていたのですが、きちんと書き留めるようになったのは最近なのです。
    ブログにUPできるのは今年の分だけかと思いますが、どうぞ贔屓にして下さい。
    これからも宜しくお願いいたします。
    (こちらからもTBさせていただきますね)
    I appreciate in your usual cooperation.
    Best Regards,Chablis

  2. コマネチ大学 #33

    たけしのコマネチ大学 2007/01/11OA
    今回のテーマは、
    「中国人 郵便配達問題」
    文化大革命の最中、郵便局に配属された中国人クワン・メイ・コウ(間違ってるかも..)が中国の数学雑誌に記事を書いた問題。
    アメリカ人、アラン・ゴールドマンがこのような名前を付けたとされて…

コメントは受け付けていません。