TIM Labs

2018年1月アーカイブ

 数理最適化の実践ガイド-600.jpg
数理最適化の実践ガイド

著者  穴井 宏和

発行  2013年3月1日

サイズ  A5, 150頁  

ISBN  978-4-06-156510-4

価格  2,800(本体)  

本書は、以前紹介した『今日から使える!組合せ最適化』(以下前書と書く)の姉妹書である。
内容的には、前書が最適化の入門の入門書で、本書がその続きのような内容になっている。
しかし、発行日を見ると、本書が先に出され、後からよりわかりやすい入門の入門が出されたようである。

本書も前書同様にかなり薄い本である。

内容的には、最適化について離散最適化を除き、連続最適化に限っている。
内容は2部にわかれていて、前半は最適化全般の話である。
ただし、このページ数であるので、証明とか、詳しい説明については、巻末に参考書のリストがあり、より詳しく知りたい場合に読むと良い本が紹介されている。
要するに、きちんと知りたければ、別の本を読むべきである。

後半は、個々のアルゴリズムの紹介である。
多目的最適化の章があり、いくつかの具体的なアルゴリズムの概略が示されているのは、これだけ薄い本では珍しいことではないかと思う。
具体的なアルゴリズムの紹介に入ってから、手順の紹介だけに終わることが多くなり、最適化がうまく行く根拠の説明などがどんどん省略され、参考文献の紹介に終わることが多い。

ということで、本書を読むと、実際にどんなアルゴリズムが使われるかの概要が分かるようになる。
でも、実際に使おうと思ったら、相当情報が足りないので、巻末に紹介されている本を読み、しっかりと理解する必要がある。

なので、まさに「実践のガイド」であった。
今まで、2点間の距離は整数としてきたが、2点間の距離を有理数でも良いことにしよう。
全ての2点間の距離が有理数であれば、全ての距離の分母の最小公倍数を掛けてしまえば、全ての2点間の距離を整数にできる。
ということで、「任意の2点間の距離が整数」でも「任意の2点間の距離が有理数」でも同じことである。
intpolygon8.png
そこで、円をどんどん大きくしていくことを中止しよう。
つまり、円の大きさを一度決めたら、固定しても良いのだ。

まず、右図のように、3:4:5 の直角三角形が2つ、長さ3の辺でつながったものを考えてみよう。

すると、辺の長さが 5:5:8 の二等辺三角形ができ、この三角形に外接する円を考える。
また、各頂点を図のように P1、P2、P3 とする。
つまり、P1ーP2 、P2ーP3 の距離は5である。
今回は、この距離5に注目する。


intpolygon9.png

今までは、2点間の距離が整数にこだわっていたのだが、円の大きさをこのままにして、P3から距離5の頂点をP4とする。

すると、P1 P2 P3 P4 で決まる四角形(台形)ができる。
このとき、 d4 = P1ーP4の距離はいくらになるであろうか。

トレミーの定理.jpg ここで突然だが、「トレミーの定理」を使う。 円周に内接する四角形に関する定理で、辺と対角線の長さに関する等式
 
  AC・BD = AD・BC + AB・DC

が成り立つ。(トレミーの定理/Wikipedia)

これを使うと、

 8*8 = 5*5 + 5*d4
 d4 = 39 / 5

となり、d4は有理数である。
まだ3点が円周上にある場合しか求まっていなかった。intpolygon5.png
まず、3点から4点に1点だけ増やすことを考えよう。

右図のように、y軸を中心に反転した3:4:5の三角形を考えてみよう。
つまり、(-7, 24)を追加してみよう。

この点から既存の3点への距離は、30、40と14になる。
30、40の2つの距離は、図形がy軸で反転しただけであるので、以前から存在する距離でしかない。
新しく発生したのは、(-7,24)と(7,24)の距離であるが、y座標値は同じで14であることがすぐに分かる。

これで4点の場合が済んだ。
5点と6点の場合を考えよう。
intpolygon6.png3点から4点にしたとき、y軸に対称な位置に点を取った。

今度は、x軸に対象な位置に点をとってみよう。
すると、6点の場合が右図のようになる。

中央に幅14、高さ48の長方形が見えている。
この4頂点は円周上の点であり、対角線は円の直径になっているので、計算するまでもなく50である。

上下反転した位置にコピーすると頂点は2点増えた。
任意の2点間の距離で、新たな距離は上下の2頂点を結ぶものだけなので、48が増えただけである。

したがって、6頂点の場合は、右図に記入されている6つの座標値が求めるものである。

さあ、もっと頂点を増やしていこう。

まだまだ正月気分だと思うので、コンピュータやAI、高尚な数学はじっくり取り組むこととして、簡単な小中学生向けの問題に取り組んでみよう。
intpolygon3.png
【問題】

円周上に5点を取り、任意の2点間の距離が整数になる場合の5点の座標を求めよ。
ただし、1点は、半径をrとしたとき、 (r,0) とする。

5点が簡単と思った場合は、点数を増やそう。
たとえば、10点の場合を考えてみよう。

それもさっさとできたら、もっとたくさんの点の場合を考えよう。
そして、一般化してみよう。


ヒントは、「ピタゴラスの定理」である。intpolygon1.png
もし、5点ではなく、3点の場合には、3辺の長さが3, 4, 5 の正三角形を考えると良い。
長さ5の辺の端点の1つを(r,0)、つまり(2.5,0)とし、もう一方の端点を(-2.5)とすると、長さ5の辺は、半径2.5の円の直径となる。
そして、もう1つの頂点は、正三角形なのだから、当然円周上になる。
だから、このもう1点の座標を求めれば、3点の場合は決まる。

右の図は、5点の場合を求めるとても良いヒントになっている。
この図をいじっていると、それだけで5点、さらには6点の場合が自然に分かるだろう。

ということで、ぜひ手作業で、あるいはプログラムで解いてみよう。

さらに、もう少しヒントを追加しておこう。
新年明けましておめでとうございます。
今年は、さらにAIなどで大きな変化がありそうな年になるでしょう。
そのために、ますます新しい技術の習得が必要になるでしょう。
でも、色々なシステムを作るためのツール類が充実するだろうし、さらにハードウェアの性能も向上するので、より高度なこと、より複雑なことができるようになるでしょう。

AIに関しては、全脳シミュレーションがどうなるでしょうか?
ポスト京では、全脳シミュレーションを目標の1つに挙げているようですが、昨年末からいろいろあって、開発が順調に進むか微妙なところがあるようです。

さて、正月ですから、あまり社会のことを考えるのは休止し、年賀のために作成したナンプレを解いてください。

nenga2018-hard-np.png

ナンプレのルール

  1. 縦と横の各列9マスには、1?9の数字が1つずつ入ります。
  2. 3×3の太枠の中の9マスにも、1?9の数字が1つずつ入ります。
  3. したがって、縦、横、太枠内のいずれにも同じ数字は入りません。

本問題の難易度は、まあまあです。


この問題が難しいと思った場合には、次へ。


このアーカイブについて

このページには、2018年1月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2017年12月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。