« ■郵便配達夫は、N!度ベルを鳴らす | トップページ | ■コマネチ大学数学科34講:素数 »

2007年1月15日 (月)

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

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

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

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

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

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

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

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

|

« ■郵便配達夫は、N!度ベルを鳴らす | トップページ | ■コマネチ大学数学科34講:素数 »

コメント

初めまして、シャブリです。
TBありがとうございました。
私の偏狭ブログを見つけてくださり、
こんな形で紹介されて、いやはや、とても嬉しい限りです。
早速、ゲームをやりました。よく出来てますね。
答えを知っているので、いろんな道順で試してみて楽しみましたよ!(resetはre-loadで...)

コマネチ大学は初回から見ていたのですが、きちんと書き留めるようになったのは最近なのです。
ブログにUPできるのは今年の分だけかと思いますが、どうぞ贔屓にして下さい。

これからも宜しくお願いいたします。
(こちらからもTBさせていただきますね)
I appreciate in your usual cooperation.
Best Regards,Chablis

投稿: シャブリ | 2007年1月15日 (月) 19時38分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/4935839

この記事へのトラックバック一覧です: ■コマネチ大学数学科33講:中国人郵便配達問題:

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

受信: 2007年1月15日 (月) 19時56分

« ■郵便配達夫は、N!度ベルを鳴らす | トップページ | ■コマネチ大学数学科34講:素数 »