近道の技術【第92号】

「乗り換え案内」や「グーグルマップ」を支える「グラフ」という考え方
金谷一朗(いち) 2022.08.26
誰でも

🎙️このレターには音声版があります (🍎Apple | 🎷Spotify | 🌏Web)

【140字まとめ】普段お世話になっている「乗り換え案内」や「グーグル(Google)マップ」の背後には,スイスの数学者オイラーが考え出した「グラフ」というアイディアがあります.本号では基本的なグラフの考え方と,科学者や技術者を捉えて放さない「目的論」についてお話ししてみます.

***

STEAM NEWS はメールで毎週届くニュースレターです.国内外のSTEAM分野(科学・技術・工学・アート・数学)に関するニュースを面白く解説するほか,今週の書籍,TEDトークもお届けします.芸術系や人文系の学生さんや教育関係者の方,古代エジプト好きな方にとくにおススメです.

***

いちです,おはようございます.

9月23日から「西九州新幹線」が開通します.1か月前にあたる8月23日の午前10時からこの「新」新幹線の切符が販売されたのですが,なんと10秒で完売したそうです.

僕はまだ乗車する予定がないのですが,長崎(出島)在住の僕は「乗り換え案内」でわざと西九州新幹線を通るルートを検索してにやにやしています.

西九州新幹線は長崎から博多を目指して伸びて行っているものの,途中というよりはかなり長崎寄りの「武雄温泉」で止まっており,武雄温泉から博多までは在来線特急に乗り換える必要があります.従来は長崎〜博多間に直通特急があったため,時刻表上はかえって不便になります.

ただ,長崎〜博多間の特急ヘビーユーザーとして感想を述べると,長崎はとうてい特急を走らせるような地形ではないため,長崎圏内だけでも新幹線が通ったことは画期的な出来事です.そうですね,本州島で例えると松本〜名古屋間のイメージでしょうか.

全然関係ないですが,昔松本から「特急しなの」に乗ったとき,途中で鹿に衝突するという事故がありまして,名古屋駅で新幹線の最終を逃したことがありました.駅のアナウンスで「お客様には宿泊をご用意致します」とのことだったので,まあ名古屋で一泊もいいかと思っていたところ,別の特急車両がごろごろとホームに入ってきまして「お客様,どうぞ中でお休みください」と言われました.いや,なんで名古屋まで来て職場と同じ寝方せなあかんねん.

話を戻しましょう.

嬉野温泉(画像:じゃらん)
嬉野温泉(画像:じゃらん)

是非皆様も旅行先に長崎を組み入れては如何でしょうか? 東京や大阪からでしたら,いったん飛行機で長崎に入り,そこから新幹線を使って武雄温泉,嬉野温泉といった温泉地に足を伸ばすのがおススメです.泉質が最高ですし「呉豆腐」という,とても珍しい豆腐もありますよ.

さて,今週はそんな「乗り換え案内」にも使われるテクノロジー,グラフ理論についてお話ししてみたいと思います.

【お知らせ】ツイッターで「STEAMコミュニティ」を運営しています.ときどき裏話をつぶやいています.ツイッターアカウントをお持ちの方は是非ご参加ください.

《目次》

  • ケーニヒスベルクのななつの橋

  • 乗り換え案内と最短経路を探す問題

  • 近代物理学に残る亡霊

  • 今週の書籍

  • 今週のTEDトーク

  • Q&A

  • リーゼ・マイトナーのフォローアップ

  • 一伍一什のはなし

ケーニヒスベルクのななつの橋

18世紀のプロイセン王国(現ドイツ)の東部にケーニヒスベルク(現カリーニングラード)という町がありました.本誌【第69号】でお話しした,琥珀で有名な街ですね.この町にはプレーゲル川という大きな川が流れていて,7本の橋が架けられていました.

Image courtesy of Bogdan Giuşcă, Pbulic Domain
Image courtesy of Bogdan Giuşcă, Pbulic Domain

あるとき町の人が,次のように言いました.

「このプレーゲル川に架かっている7本の橋を2度通らずに,すべて渡って,元の所に帰ってくることができるか.ただし,どこから出発してもよい」

スイスの数学者レオンハルト・オイラー (Leonhard Euler) が,1736年,この問題を解くことに成功しました.まず彼は地図から街並みを取り払い,地面と水面と橋だけの図にしました.

Chris Martin, CC BY-SA 3.0 (一部改変)
Chris Martin, CC BY-SA 3.0 (一部改変)

次に彼は地図を「グラフ」に置き換えました.グラフというのは数学用語で,点と点を線で繋いだもののことです.そして,このグラフが一筆書き可能であれば,ケーニヒスベルクの橋をすべて1度ずつ通って戻ってくるルートが存在することになります.グラフの例を次に示します.

Chris Martin, CC BY-SA 3.0 (一部改変)
Chris Martin, CC BY-SA 3.0 (一部改変)

オイラーはこのグラフが一筆書きできないことを証明しました.つまり,件(くだん)の町人の質問に「出来ない」と間違いなく答えることができたのです.

オイラーは,グラフのすべての「頂点」(オレンジ色の丸)から出て行く「辺」(橋)が奇数であることから,一筆書きでは出発点に戻れないことを証明しました.

ただし,オイラーの証明よりも,オイラーが「地図」を「グラフ」に置き換えたことの方がより重要です.この置き換えによって,我々は地図が持つ「距離」という情報を無視して「どことどこが繋がっているか」だけを考えれば良くなるからです.

このようにある情報を無視することを,我々はしばしば「抽象化」と呼びます.

そう言えば,天才スポーツ選手も瞬時に状況を抽象化できるそうですね.一流サッカー選手は,上空からフィールドに立つ自分が見えているのだとか.これなんかも「視覚」という情報を無視して,イラスト化されたサッカーフィールドが見えているのでしょうね.

画家のパブロ・ピカソもまた,対象物を抽象化して見ることが得意だったようです.彼の作品を見てみると納得できますね.

乗り換え案内と最短経路を探す問題

地図をいったん抽象化してしまえば,我々のような計算幾科学者の出番です.

地図のような情報から,距離のことを忘れて「こことここは繋がっている」「こことここは繋がっていない」という情報だけを残したものを「グラフ」と呼ぶのでした.

このようなグラフを調べていくと,ある地点からある地点への「経路」が何通りあるのかも数え上げることができるようになります.もし到達できなければ,経路は0本ということになりますね.

我々がお世話になっている「乗り換え案内」も,内部では鉄道網をグラフとして持っています.このグラフを使って,まずは出発駅から到着駅へ到達できるのかがチェックされます.

続けて,グラフの頂点(駅)間の移動時間が考慮されます.グラフ上の1本1本の辺(路線)には所要時間も書き込まれています.鉄道の乗り換え時間や待ち時間を無視した場合,1959年に発明された「ダイクストラ法」という方法が使えます.

ダイクストラ法は,1959年にオランダ人計算機科学者エドガー・ダイクストラ (Edsger Dijkstra) によって発明されたアルゴリズムで,所要時間が書き込まれたグラフから最短経路を求めるために使われます.

1959年という,計算機科学の世界では「石器時代」のアルゴリズムですが「もうこの方法しかない」と言うぐらい本質を突いたもので,現在に至るまで使われています.

ところで皆さんはグーグル(Google)マップを使われているでしょうか? 僕自身は熱心なアップル(Apple)ユーザですが,地図だけはグーグル派です.ほんと,アップルの「マップ」アプリにはどれだけ変な場所に連れて行かれたことか…

いえ,それはどうでも良いことです.

グーグルマップを使うと徒歩の経路や自動車での経路も見つけてくれますよね.実はグーグルマップでも,経路はすべてオイラーの方法にしたがってグラフ化されています.つまるところ,本質的にはグーグルマップと乗り換え案内は同じものなのです.すべての交差点,すべての建物や公園が駅になっているようなものです.

こう考えると,地図をグラフに置き換えたオイラーの先見性にはただただ驚くばかりですね.

鉄道ファンの間では有名な「大回り乗車」も一種の一筆書きなので「ケーニヒスベルクの橋」の応用問題とも言えます.コロナ禍がまだ続いているので強く推奨するわけではありませんが,首都圏や関西の方はオイラーに思いを馳せながらお試しになっては如何でしょうか.

大回り乗車とは違いますが,西九州新幹線ができたことで,長崎では「新大村駅→新大村駅」の「片道切符」が誕生しています.地理的にはおかしな事になっていますが,オイラーの考え方によればこれはこれで正しいのです.おもしろいですね.

近代物理学に残る亡霊

最後に余談です.

古代ギリシアの哲学者たちは「目的論」というアイディアに魅力を感じていました.一言で言うと,目的が先にあって,そのためにプロセスが生じたという考え方ですね.(専門家のかた,間違っていたらごめんなさい!是非メール返信でも,ツイッターコミュニティでもご指摘ください.)

科学者たち,とりわけガリレオ・ガリレイたちはこの「目的論」を捨て去ることから,近代科学を発展させて行きました.「原因が積み重なって結果が生じる」と考えたわけですね.

しかし「目的論」の魅惑は現代の科学者たちにさえ根強く残っています.たとえば「光は最短の経路を通る」とする「フェルマーの原理」という物理法則は,いまだに人気のある考え方です.フェルマーの原理から光の反射や屈折の説明がすべてつくので,物理法則として間違っているわけではありません.

しかし「乗り換え案内」を持っていない光の粒つぶが,どうやって最短の経路,つまりは「近道」を見つけているのでしょうか.フェルマーは光が「神の視点」を持っていて,自ら最短の経路を選ぶと考えたようです.一流サッカー選手のようですが,この仮定には無理がありすぎます.

アメリカのノーベル賞物理学者リチャード・ファインマン (Richard Feynman) は,別の考え方をしました.光は目的地に到達する「ありとあらゆる」経路を同時に取ると考えたのです.そして,もし我々が「光がどこを通ったのか」を計測すると,結果として最短の経路を通ったことを知るというのです.

ごめんなさい,あまり上手に説明できていません.英語になりますがリチャード・ファインマン自身が「QED」という書籍で一般向けに分かりやすく解説していますので,英語が苦にならない方は是非こちらでお試しください.

いったんは「目的論」を追い出した物理学でしたが「フェルマーの原理」を始め,いくつもの目的論ぽい考え方を再導入しています.大学で物理学を勉強された方なら「ラグランジアン」「ハミルトニアン」がそれにあたります.

最短経路てなぜか,科学者や技術者のロマンなんですよね.

今週の書籍

1973年,アポロ18号の打ち上げを間近に控え,カズ・ゼメキスはヒューストンのNASA有人宇宙船センターに軍の連絡将校として着任する.宇宙飛行士候補だった彼には,特別な思いのある任務だ.最後の月着陸となる今回のミッションは,ソ連の軌道上偵察ステーションと月面探査車を対象とした軍事目的となる.だがその直前,事故が起きた――架空のアポロ18号を題材にして宇宙飛行士の著者が描いた,もう一つの宇宙開発史

本文とはほぼ関係ないのですが,今週読んだ書籍をご紹介させて頂きます.

本当の宇宙飛行士クリス・ハドフィールド (Chris Hadfield) が書いたSF犯罪小説です.

読者として好き勝手言うとするならば,アンディ・ウィアーのような歯切れの良さが無く,かといってアイザック・アシモフのような重厚感もありませんでした.

しかし,続きが気になって結構ノンストップで読んでしまいましたし,もちろん「じゃあお前書けるのかよ」と問われれば超絶に落ち込むので,悪口はこの程度にしておきます.

面白かったですよ.

今週のTEDトーク

地図アプリは目的地への最短経路を見つけてくれる便利なものですが,少し遠回りしたい気分の時はどうでしょう? 研究者のダニエレ・クエルチャ が,単に早いだけでなく,その道のりでどう感じられるかまで考慮に入れた「ハッピーマップ」をご覧に入れます.
TED

本文でご紹介した「ダイクストラ法」が使えるのは最短経路の探索だけではありません.ダイクストラ法は辺の「重み」の合計を最小にするような経路を見つけるアルゴリズムでした.まったく同じ方法で,辺の重みの合計を最大にするような経路を見つけることもできます.つまり,最大経路も見つけられるのですね.

そして「重み」は移動時間に限りません.

このTEDトークにあるように,楽しさが最大になるような経路もダイクストラ法で見つけることができます.

オイラーとダイクストラに乾杯ですね.

Q&A

匿名質問サイト「マシュマロ」および質問サイト「Quora」で質問を受け付けています.普段はツイッターでお返事を書いていますが「ニュースレター読んでます」と入れていただければ,こちらのニュースレターでより長めの回答を書かせていただきます.

今週はこちらの質問から.

長崎ちゃんぽんは本場よりリンガーハットの方が美味しいと言われるのは何故ですか?

本場よりリンガーハットのほうが美味しいのではないのです.

本場のリンガーハットは美味しいのです.

もちろん長崎にはちゃんぽんの発案者である「四海樓」をはじめとした美味い店はたくさんあるのですが,車で行きやすくて,お昼時でもそれほど混まなくて,並み居る名店と肩を並べる美味しさのリンガーハットは,地元民に大変愛されているお店でもあるのです.

このレターの最後に匿名質問サイトへのリンクを貼っています.質問をお待ちしております.

リーゼ・マイトナーのフォローアップ

以下はSTEAMボート乗組員(有料購読者様)向けの【第91号別冊】に掲載した内容ですが,本誌のフォローアップになりますので転載させて頂きます.

本誌【第91号】でお届けしたリーゼ・マイトナーと同時代の女性化学者・物理学者に,ドイツのイーダ・ノダック(旧姓タッケ)がいます.彼女もまたノーベル化学賞候補と目されていましたが,受賞はなりませんでした.

STEAM NEWS読者のおひとりから,本誌【第91号】ではこのイーダ・ノダックを無視しているのではないかというご指摘を頂きました.まったくその通りでしたので,少しご紹介したいと思います.

彼女はヨーロッパで学問の扉が女性に開かれた最初の世代の人で,物理学に興味を持っていたものの,当時はまだ物理学者の需要が少なかったため,化学の道を選びました.1934年,エンリコ・フェルミがウランに中性子を衝突させる実験の結果を報告すると,フェルミが主張する「超ウラン元素が生成された可能性」の難点をイーダは指摘しました.彼女はこの時点でウランが「核分裂」した可能性を検討していました.

ウランに中性子をぶつける実験が繰り返され,生成物を同定する研究が進められるなか,1938年にオットー・ハーンとフリッツ・シュトラスマンがついにバリウムの同位体であることを突き止めます.この結果を知らされたリーゼ・マイトナーが「核分裂」モデルを構築し,オットー・ロベルト・フリッシュ(リーゼの甥)が実証実験を行い,ウランが核分裂することを確かめました.

イーダ・ノダックの仮説は正しかったのです.

残念ながら,イーダ・ノダックは核分裂モデルの提唱者として広く知られているわけではありませんが,実は75番元素「レニウム(Re)」の発見者として歴史に名前を残しています.レニウムの名称はイーダの生地が「ライン川」左岸だったことに因んでいます.発表は1925年でした.

この75番元素は自然界に存在する元素ですが,日本人にとって苦い歴史のある元素でもあります.

レニウムは化学的性質が43番元素「テクネチウム」に大変よく似ています.そして,日本の小川正孝が1908年に「43番元素」を発見したと発表したことがあるのです.小川はこの元素に「ニッポニウム(Np)」と名付けることを提唱しました.しかし後に,この発見は否定されています.43番元素が自然界にはほぼ存在しないこともわかり,人類がはじめて合成した元素になりました.43番元素はテクノロジーによって合成された元素なので,テクネチウムと名付けられました.(ウラン238の自発核分裂でテクネチウムが生じるため,自然界でもゼロではありません.)

実は1925年にイーダ・ノダックも43番元素を見つけたと発表しています.しかしその後確認はされませんでした.小川の発見も,イーダの発見も,おそらくはレニウムだったと考えられています.

当時の分析技術では難しかったのでしょうが,もし小川が43番元素ではなく75番元素を見つけたと発表していたら,いまごろ「レニウム」は「ニッポニウム」と呼ばれていたことでしょう.

なお,現在では天然のレニウムよりも原子炉の中で生成されるテクネチウムのほうが,入手性が良いようです.

一伍一什のはなし

先週は喉が痛かったり,COCOAから接触通知が来たりと,コロナ感染を疑わせる状況が続いていたのですが,PCR検査を受けまして無事コロナ陰性を確認しました.ご心配を頂いた皆様に,この場を借りまして御礼申し上げます.

少しずつ海外活動を増やす予定でして,先週から今週にかけては頻繁に海外とのオンラインミーティングが続いています.また現地からの報告などもこのニュースレターでお伝えしますね.

ところで「月刊ウィーン」という情報誌を僕も読ませて頂いているのですが,そのバックナンバーにリーゼ・マイトナーを取り上げた記事がありました.執筆された杉本純先生は,リーゼの記録が消された時代をリアルタイムに体験されていたようです.大変参考になりました.

🍓

今週も最後までお読みいただきありがとうございます.メールでお読み頂いた皆様は,よろしければボタンを押して行ってくださいませ.(ボタンは匿名化されています.集計したデータはこのニュースレターの内容改善以外には用いません.)

ここに配置されたボタンは、ニュースレター上でのみ押すことができます。

このニュースレターは下のボタンからSNSで共有できます.もし気に入っていただけたら,共有ボタンも押していってくださいませ.

では,また来週,お目にかかりましょう.

***

ニュースレター「STEAM NEWS」

金谷一朗(いち)

TEDxSaikaiファウンダー・パイナップルコンピューター代表・長崎大学情報データ科学部教授

バックナンバーはこちらから👉 https://steam.theletter.jp

匿名質問はこちらから👉 https://marshmallow-qa.com/kanaya

(ご意見,ご感想はこのメールに直接ご返信頂けます)

Cover Photo by Michał Parzuchowski on Unsplash

「STEAM NEWS」をメールで読みませんか?

無料で「STEAM NEWS」をメールでお届けします。
コンテンツを見逃さず、購読者限定記事も受け取れます。
議論・討論・談論を使い分けていますか?【第98号】
誰でも
★ 「例のもの」のノート【第97号別冊】
有料限定
アポロ12号が月へ運んだ「例のもの」【第97号】
読者限定
★ 緑色のひみつのノート【第96号別冊】
有料限定
緑色のひみつ【第96号】
読者限定
★ かけ算の順序のノート【第95号別冊】
有料限定
かけ算に順序はあるの?【第95号】
読者限定
★ 死を招くファッションのノート【第94号別冊】
有料限定