福西です。
この日は、「巡回セールスマン問題」を考えました。
問い：A～Fまでの地点をすべて通り、スタート地点に戻ってくる道で、合計点が最小となる道を見つけよ。
（ただし道の横に添えられた数字が、その道の点数）
こちらのクラスでも取り上げましたが、５年生たちも変わらずに熱心に考えてくれて、「まだ（いい答は）ないか？ まだないか？」と、ひたすらパターンを追ってくれました。生徒たちが見つけてくれた答の中で、最小は13点で（私もそうなったのですが）、みなさんなら、どんな答になるでしょうか。
さて、「最小とせよ」という問題設定では、なかなかイメージがピンとこないと思うので、授業では、ある値を「最大にせよ」という問題に置き変えて考えました。（ちなみに以下のストーリーは私が勝手にこしらえました^^;）。
「あなたにはこのたび、莫大な財産が入ることになった。ただしその遺言には、こう書かれていた。
『上の問題でお前が出した答をAとせよ。そして、（20－A）×3億円が、お前の取り分となる』
と。さて、あなたは何億円手にすることができるだろうか？」
まあ、こんな風にイメージを膨らませてみたのですけれど、要は、Aを最小にすることは、－Aを最大にするのと同値ということです。そこで、（20－A）×3を設定して（こういう式を評価汎関数とか目的関数とか言います）考えました。×3とあるのは、１点の違いが大きいということを認識してもらう都合でそうしました。
20点なら、（20－20）×3で0円。（とんとん）
19点なら、（20－19）×3で3億円。
18点なら、（20－18）×3で、6億円。
1点の違いが3億円（！）
もし本当にそんなことがあったら、これは血眼になってでも考えないと損ですよね（笑）。
授業では、生徒たちには発見的に解いてもらいましたが、私は以前こちらで説明した「動的計画法」というものを単純に当てはめて考えてみました。（ただし、もしスタート地点がゴール地点と別々なら、以下のようにして出した答が最小だと言えるのですが、今回はそうではないので、とりあえず偶然「そうじゃないかなあ・・・」（？）という程度でしかない考えです）。
出発点をAとする。
Aに向かう道で、点数が最小なのは、E→A。
f（E→A）＝1
Eに向かう道で、点数が最小なのは、C→Eと、D→E。
f(C→E）＝f(D→E)＝2
Cに向かう道は、最小のものでも3点。一方Dに向かう道には、B→Dの2点のものがある。
f(B→D→E)＜f(任意→C→E)
なので、道は、f(B→D→E)を取るのが必然。
ここまでで、f(B→D→E→A)＝2＋2＋1＝5と決まる。
さて、Bに向かう道で、点数が最小なのは、C→Bと、C→A。
しかしAはスタート地点だったのでここでは除外すると、C→Bのみ。
f(C→B)＝3
ここまでで、f(C→B→D→E→A)＝3＋2＋2＋1＝8と決まる。
さて、Cに向かう道で、点数が最小なのは・・・と同様に考えるところ、実はまだ通っていない地点は、FとAしか残ってない。そしてAはスタート地点。つまりFを通るのが必然。
f(F→C)＝3
ここまでで、f(F→C→B→D→E→A)＝3＋3＋2＋2＋1＝11と決まる。
最後は、A地点に帰ってくるので、（これが何点でも甘受しなければならない）
f(A→F)＝2
よって、f(A→F→C→B→D→E→A)＝2＋3＋3＋2＋2＋1＝13と決まる。
これが最小（？）かと思ったのですが、どうでしょうか。（たぶん証明にはなっていないので、もしそれで最小だとしても、単なる偶然かと思います・・・）。
ちなみに、もし上の答が最小で、唯一のものだとしたら、どの地点から出発しても同じ結果になります。
というのは、たとえばEから出発して考えたとしても、結局上の道順を1個ずらして考えているだけだからです。
f(E→A→F→C→B→D→E)＝1＋2＋3＋3＋2＋2＝13
まあ、出てきた答が「一筆書き」なので、そもそもどこから出発しても同じと言うわけです。
こんなふうな問題を授業ではいつもさらっと出して考えてもらっているわけですが、直感的にでも問題の奥深さをつかんでもらえると嬉しいです。