時期も時期なので自由研究的なネタをご紹介します。
今朝目覚めると雷がゴロゴロとなっていました。
そこでふと思いつきました。
「雷は抵抗が最小になる経路を通るはずなので、
最短経路問題を解けば雷みたいな軌跡を描くことができるはず。」
と言うことで最短経路問題を解いて雷の軌跡を作ってみましょう。
最短経路問題
最短経路問題とはある地点から別の地点に行くまでの
最短の経路を求める問題です。
例えばカーナビのルート検索で、
自宅からスーパーまでの最も短いルートを検索するような場合です。
最短経路問題を解く方法として代表的なものは
ダイクストラのアルゴリズムと呼ばれるものです。
ダイクストラのアルゴリズムでは、
出発点からスタートして近い中間地点から順に距離を確定させていきます。
手順をざっくり書くと下のようになります。
- スタート地点までの距離を0とする
- 既に距離が確定している地点に隣接している距離が確定していない地点のうち最も距離が短い点ピックアップする
- その地点の距離を確定して、その地点経由で隣接地点への距離を計算する
- 目標地点の距離が得られるまで2,3を繰り返す
このように比較的簡単な手順で最短経路が計算できます。
雷の軌跡と最短経路
雷は上空の雲と地面とのあいだで電流が流れることで生じます。
雲と地面の間には空気がありますが、
空気は電気抵抗が高く電気を通しにくいことで知られています。
雷はこの空気の電気抵抗をかいくぐって流れることで生じます。
空気の電気抵抗は場所によって異なっていて、
電気抵抗の小さいところを通るように雷は流れます。
自然は楽をするのが好きです。
このため、雷の軌跡は、
空気の電気抵抗が最小となるような
「最短経路」を描きます。
プログラムで書いてみる
では実際に最短経路問題を解いて雷の軌跡を作ってみましょう。
空気中の電気抵抗の場所による違いを表すために、
格子状に一様分布でランダムな抵抗値を与えました。
後は格子状の上辺の一点をスタート地点として、
ダイクストラのアルゴリズムで下辺までの最短経路を計算します。
下の図はそのプログラムの動作の様子を表しています。
最初に現れる白黒はそれぞれの地点の抵抗値の大きさを表していて、
じわじわ広がる赤の領域は最短経路が計算された地点を表しています。
全ての地点の最短経路が計算されると、
スタート地点から下辺までの最短経路が
白い線で表示されます。
再計算するたびに様々な軌跡が見られますが、
ジグザグの雷が最短経路として現れるのは面白いですよね。
まとめ
最短経路問題を解いて雷の軌跡を描いてみました。
50x50の格子でも結構時間がかかりますが、
雷は一瞬で道を見つけるのも面白いところですよね。
