経路の演算
@sada1110 先生からのご下問に答えてみるシリーズ第二回。
いくつかの用語の定義
a:[P,P]で、「P点に留まる」を表現できる。
このとき、aをどのように分割しても b:[P,P]しか得られない場合(本当に動いていない場合)と、分割の仕方によっては c:[P,Q]が得られる場合(動き回って元の所に戻ってくる場合)の2通りが考えられる。
aが b+c+d に分割可能である時、cのみで動作を指示させることもできる。a:[P.Q]に対して、b:[P,S;null],c:[S,S;λ],d:[S,Q;null] が接続されたものと仮定すれば、このエッジaでは、途中の点Sのみにおいて動作λを行わせることになる。「車で移動するが、途中1回だけトイレ休憩が挟まれる」などの記述に向いている。
エッジ集合族に課せられる制約条件
以下の条件を課すかどうかは、クライアントである @sada1110 先生のお考えによる。- 同値関係 ≡(本当は、3本線の一番上は波線にしたかった)
- 始点と終点が同じ場合に同値であるとみなすか、始点と終点が同じであって途中の移動経路も全て同じである場合に同値であると見なすか、2通りの考え方がある。
- 数学的には、第一の場合はホモトープに近い。第二の場合は合同である。厳密な議論においては合同であることを求めると予想されるが、経路探索においてはホモトープな図形であれば良いとする場合もあるだろう。
- たとえば、a:[P,Q],b:[Q,P]において、(a+b)は「動かない」のか、「動き回るが元の位置に戻ってくる」のか、という区別ができる。
- エッジ集合における接続可能性
- どんなエッジ集合でも考慮対象とする、という立場が考えられる
- エッジを上手に並び替えれば、全てのエッジが接続可能となる、という立場が考えられる。
- エッジを並び替えなくても、登場順に全てのエッジが接続可能となる、という立場が考えられる。
- 後になるほど条件は厳しくなる。おそらく2番目の条件が現実的である可能性が高い気がする。
(当然)続く・・・・
脳内計算尺
以前、計算尺相当の有効数字での計算ならば指数関数を除いて暗算可能だ、という話をしたことがある。
捜し物をしていて、偶然、そのことを記したメモを見つけたので、忘れないうちに転載しておく。
手順:
Use R4, R5, R6, R7 4番から7番までのレジスタをアキュムレータとして使用する
Mov R1, degree 1番レジスタに角度値(まだ度分秒)をロード
Mov R2, C_PI 2番レジスタに円周率の値をロード
Mul R1, R2 1番レジスタに2番レジスタの値を乗算
Mov R2, 180 2番レジスタに180(定数)をロード
Div R1, R2 1番レジスタを2番レジスタで除算(これで角度が弧度法に)
角度を弧度法に変換している。円周率を乗ずる際には、筆算だと3桁×3桁で、乗算記号の下に4段の数字が並ぶので、4つのレジスタを計算途中の一時記憶用として使用する。
言い換えると、3桁×1桁の乗算は、脳内レジスタを消費せずに計算できなければならない。また、小数の位取りは、自分で調節しなければならない。
258 1番レジスタに格納済(実際には様々な値)
x 314 2番レジスタに格納済(円周率の最初の3桁)
−−−−−−−−−
1032 4番レジスタを使用
258 5番レジスタを使用
774 6番レジスタを使用
−−−−−−−−−
81012 7番レジスタを使用 → 1番レジスタに再格納、
このとき、有効数字4桁目以降の四捨五入と、小数位置の確認を同時に行っている。
Mov R2, R1
Mul R2, R1 2番レジスタには角度xの2乗が格納される
Mov R3, R2
Mul R3, R1 3番レジスタには角度xの3乗が格納される
このとき、いすれも4番〜7番レジスタが、第一段の場合と同様に、計算途中結果の格納用として使用されていることに注意。
Free R4, R5 4番及び5番レジスタをアキュムレータとしての役割から解放する
Mov R4, R3
Mov R5, 6
Div R4, R5 4番レジスタには x3/6 が格納される
Sub R1, R4 1番レジスタに、x−x3/6 が格納される
Use R4, R5 4番、5番レジスタを再度アキュムレータとして使用する
Mul R2, R3 2番レジスタには角度xの5乗が格納される
Mov R3, 120
Div R2, R3 それを120で割って、2番レジスタの値が x5/120 となる
Add R1, R2 1番レジスタに2番レジスタを加える。これは殆ど不要であることが多い。
Free R4, R5, R6, R7 アキュムレータを解放して
return R1 終わり。1番レジスタに、有効数字3桁で、sin X が格納されている。
これらの手法、特に最後の Exp は、計算量が膨大なため、脳内レジスタの疲労によるメモリ揮発が心配である。Geo80k のように中高年になってしまうと、特にメモリリフレッシュで苦労する。
アルゴリズムもエレガントの対極である。(4)〜(7) までのループがひどい。
ボロノイ図に関する小さな考察
先日、@sada1110 先生から「ボロノイ図において、点が重複している場合はどうなるか」というご下問を頂いた。
考えてみたのだが、結構奥が深い。そこで、まずは問題を簡素化して考えてみることとした。
基礎的な事項と仮定
N個の点群P(p1,p2,・・・,pN)が与えられている時、任意の点Qに対して、Qから最も近いPの点がどの点であるかに応じて平面を塗り分けたものがボロノイ図である。
ボロノイ図は、有限個の線分又は半直線で平面を区切った図になる。半直線の数は、Pを含む最小の凸多角形の辺数に等しい。線分の数はちょっと簡単な計算方法が思いつかない。
点群Pが1点だけからなる時は意味がないので、Pは2点以上からなるものと(以下常に)仮定する。
点群Pが2点(p1,p2)だけからなる時は、ボロノイ図は、p1,p2の垂直二等分線になる。
点群Pが3点(p1,p2,p3)からなる時は、ボロノイ図は点群Pを三角形と見て、この三角形の外心(外接円の中心)を端点として各辺の中点を通るような3本の半直線となる。
点群Pが4点以上の点で構成される場合は、一挙に記述が複雑になる。(一旦、この場合は脇に置いておく)
当面、簡単にするために、点群Pは3点(A,B,C)から構成されているものとし、点B,Cが極めて接近した場合におけるボロノイ図の挙動を考える。
「極めて接近」の意味は、計測解像度δを下回る距離まで点B,Cが接近すること、と定義しておく。このとき、点B,Cの位置は必ずしも同一になる必要はないことに注意する。
座標の導入
点群Pの座標として、A(0,a),B(x、ε),C(-x、-ε)とする。ただし、x もεも正負いずれの値も取り得るものとし、a は x,ε,δ のいずれよりも十分に大きな値であるものと仮定しておく。
このとき、となれば、点B,Cは「極めて接近している」ことになる。
考えるべきことは、εの値をδより小さい任意の値に固定しておいて、xを0に近づけた時のボロノイ図の挙動である。
εが0の場合
まずは、最も簡単なケースから考える。
xが0でなければ、△ABCは二等辺三角形である。外接円の中心は、のすぐ近く(僅かに下方)にあり、ボロノイ図はほぼT字形になる。実際には、Tの字の横棒は僅かに折れ曲がっていて、V字を左右に引っ張ったような形をしている。
この状態で x を 0 に近づけると、外接円の中心はに収束し、ボロノイ図はT字に収束する。
ただし、x が 0 になった瞬間に△ABCは2点ABに縮退するので、ボロノイ図も直線 で分割される2枚の半平面に縮退する。
εが正の値(<δ)の場合
xがδよりも十分大きな値の場合は、△ABCは鋭角三角形であり、外接円の中心は△ABCの内部にある。しかし、xがある程度小さくなると、△ABCは鈍角三角形になり、外接円の中心は△ABCの外部に出てしまう。具体的には、外接円の中心はどんどん左に移動してしまう。
この状態で x を 0 に近づけると、外接円の中心はに近づく。
(計算は省略しているが、それほど難しくはない。ここでは幾何学的直感を重視して書いている)
ただし、x が 0 になった瞬間に3点ABCは一直線上に並ぶので、外接円は定義されなくなり、ボロノイ図は2本の直線 , で区切られる3つのエリアに分けられる。これは、幅が の帯と、その上下の2枚の半平面である。
εが負の値(>-δ)の場合
εが負の値の場合は、εが正の値の場合の鏡像と考えて差し支えない。
従って、x を 0 に近づけると、外接円の中心はに近づく。
ただし、x が 0 になった瞬間に3点ABCは一直線上に並ぶので、外接円は定義されなくなり、ボロノイ図は2本の直線 , で区切られる3つのエリアに分けられる。これは、幅が の帯と、その上下の2枚の半平面である。
ということは?
2点が計測限界よりも接近してしまった場合に、2点の相互位置は分からなくなるが、これを顕微鏡で拡大してみたばあいの2点の位置関係によって、ボロノイ図の挙動が大きく3通りに別れることが分かった。つまり、ボロノイ図の挙動は安定的ではない。
実際には、点Aを含むエリアは安定していて、点Bと点Cを含むエリアが不定になるだけである。点Bと点Cの位置は(検出限界を下回って接近しているので)不明となるので、点Bと点Cを含むエリアが不定になるのはおかしくない。
結局どういうこと?
ボロノイ図は、2点がどれだけ接近しても、数学的に同一の座標を持たない限り計算できてしまう。
ここで、座標の検出限界(下限)を設けることは、座標系を離散化するに等しい。離散空間において2点が検出限界を下回って接近している場合は、それら2点の座標を同一視することになるが、2点がどのような経路で接近するかによってボロノイ図の挙動が大きく変わりうることが分かった。
もともと、ボロノイ図とは、「任意の点から見て、一番近い指定点はどれか、を返す図」である。指定点が縮合してしまえば、一番近い指定点が一意に決まらなくなるのは当然である。
この場合、考察に意味を持たせるためには、追加の仮定が必要になるものと思われる。すなわち、
- 縮合している複数の点は1点として扱い、属性値が複数あるものと見なす
- 縮合している複数の点は全て返すように、ボロノイ図を多価関数ベースで考える
のいずれかである。(両者は本質的には同じことであるが)
多価ボロノイ図
多価ボロノイ図においては、ボロノイ分割を行う前に、与えられた点群のうち限界距離以下に接近しているものを縮合しているものと見なして1点にまとめるような前処理が必要になる。
たとえば、4点(A,B,C,D)が与えられ、このうち点B、Cの距離が限界よりも近い場合は、点集合(B,C)を一点と見なして、改めて3点(A,E,D)でボロノイ分割を行うべきなのである。
このとき、点Eの位置は、(B、C)の近傍の1点(接近限界で規定されるような分解能で得られる代表点)としておく他はない。
実際には、接近限界としては「同一の筆にある地点であるかどうか」が代表的であろう。集合住宅のように、単一の底地の上に複数の世帯が存在している場合、地番は同一で、住居表示で区別される。一般的には、住居表示が示す位置は、底地(敷地)である土地の代表点(筆の幾何学的中心とか、敷地の正門の位置とか)になるので、
ボロノイ分割を行った場合に多価関数として返す以外に方法はないと思われる。
より直感的な多価ボロノイ分割(1)
私「Bさん、いま何処にいるの?」
B「Aくんと同じ所にいるのよ!」
C「geo80k から見て一番近いのは誰だ?」
私「(A,B)の二人だね!」
(A,B)「私たち、ずーっと一緒!!」
どちらも区別できない(実生活では距離を区別しない)のは明らかである。
より直感的な多価ボロノイ分割(2)
私「Bさん、いま何しているの?」
B「Aくんとワルツを踊っているのよ!」
C「geo80k から見て一番近いのは誰だ?」
私「(A,B)がくるくる回っているから決められないよ!」
無理に一価関数にしようとすると、こうなる。彼らは所詮二人で一つなのであって、「 a couple of 」を前置するのに適しているというわけだ!
ちょっと直感的ではない多価ボロノイ分割(笑)
原子核の周囲を数個の電子が回っている。
たとえば、ヘリウム原子の周囲には2個の電子が回っている。
この2個の電子は、完全に同一の地点に来ることはないから、古典的な原子核モデルにおいては、電子の位置に基づく幾何学的なボロノイ分割が可能で、ほぼヘリウム原子核の位置を通るような平面で空間が分割される。
しかし、高速に動き回る電子でボロノイ分割することの意義はほぼ皆無であろう(ヘリウムを絶対零度ちかくまで冷やして、原子核の位置をほぼ固定したとしても)。
さらに、電子の位置を確率分布にしたら(いわゆる電子雲だ)? ボロノイ図も確率分布になるのか?(ちょっと書きすぎ)
標準的な一次関数
一次関数をどう説明すれば理解しやすいか、トライ。
中学校で習う一次関数は、
y=ax+b ・・・(1)
の形をしている。しかし、これはカノニカルな表現ではない。カノニカルな表現は、
y−c=a(x−d) ・・・(2)
である。このとき、もちろん、
b=c−ad ・・・(3)
という関係が成立しているものとする。ここで、(2)式において次のような変数変換
Y=y−c、X=x−d ・・・(4)
を施してみる。すると、最初の式(1)は、
Y=aX ・・・(5)
と表現できる。変数変換しただけなので、見た目は違っていても本質的には同じ式である。
YはXの関数なので、
Y=f(X) ・・・(6)
と書くこともある。
-
-
- -
-
さて。一次関数の性質だが、
f(X1+X2)=f(X1)+f(X2) ・・・(7)
これに尽きる。
足したものの関数値が、関数値を足したものになる、である。
この関係(7)は、中学校の一次方程式に限らず一次関数に広く共通して成立する性質である。逆に、この性質が成立するような集合に共通して成立するような条件を調べるのが、線形代数学なのであった。
本質は、関数を施すことと、足し算をすることの順序が交換可能であること、なのでありました。
-
-
- -
-
ところで、この関係(7)は、カノニカルな表記でないとうまくいかない。カノニカルに書くことの意義もここにある。
数学科の学生ならほぼ自明な話だとは思うが、それ以外の方には難しい話らしいので、あえて項を起こしてみた。
煙突効果
はじめに、今回の水害で被害に遭われた方々に心よりお悔やみとお見舞いを申しあげます。
今回の台風は、中心が日本海に抜けた4日朝以降も大雨が降り続いた点で特異だったと思う。専門家ではない私が、あまり憶測でモノを言うのは良くないと思うが、どうしても解せない点が一つある。
それは、偏西風の効果について殆ど誰も言及しないということだ。
先週後半から今週にかけて、偏西風の位置は殆ど変わっていない。朝鮮半島から日本海北部を通って北海道を横断し、千島に沿って吹いている。台湾の北西方で熱帯低気圧に変化して消滅した台風11号も、この偏西風に乗って暖かい湿った空気の塊がカムチャッカ半島に東まで運ばれ、そこで温帯低気圧になっている。
台風12号は北太平洋と沿海州の2つの高気圧に行く手を阻まれたことになっているが、実際には偏西風にどんどん暖かく湿った空気の塊をはぎ取られて勢力を落としていたはずだった。実際に、台風の西側では積乱雲の密度が圧倒的に低かった。
では、なぜ、紀伊半島にあれだけ雨が降ったのか。その答が天気図にあるように思う。
これらの天気図は、9月4日(日曜日)の早朝から午後までのものである。一番上の午前3時の天気図で、既に台風の中心は日本海に抜けている。しかし、1000hPa の等圧線は、四国沖にべったり広がっている。1006hPa の等圧線に至っては、後に台風13号になる熱帯低気圧も含み、日本の遥か南の海上まで広がっている。
恐ろしいのは、一番下の天気図(9月4日午後3時のもの)で、1004hPa の等圧線が最も南に延びている。
これらのことは何を意味するか。
台風は反時計回りに風が吹く。これらの天気図からは、紀伊半島上空を北に向かう空気の流れが読み取れる。偏西風がなければ、これらの風は反時計回りに台風の周りを回って、一周して戻ってくるだけである。
ところが、台風の北がわまで来ると、強い偏西風が吹いている。その結果、台風の東側を北上した空気は、そのまま北東方へと流れ去ってしまう。台風の西側を南下してくる空気の量が足りず、台風の南側は低圧帯になってしまっているわけだ。
しかも、台風の東側は、偏西風に吸い取られるように、どんどん北向きの空気の流れができる。日本の南にある暖かく湿った空気が、偏西風のせいで、どんどん北上し、紀伊半島に大雨を継続的に降らせつつ、偏西風に乗って流れ去っていく。
まるで、風の強い日に煙突が勢いよく排煙するかのように、紀伊半島は「暖かく湿った空気の継続的な通り道」になったとしか考えられない。
その結果、日曜日の昼間には、日本の南に広範囲に低圧帯ができてしまった。空気が紀伊半島上空の「煙突」を通ってどんどん日本海へでてしまった。
こうして、台風が弱まっても気圧配置に大きな変化がなかったために、この煙突効果は長時間継続し 1800mm もの大雨になったのではないか。
SNSの友情
Facebook や twitter でも書いているように、私は友達とか相互フォロワーとかを余り増やさない方向で進めている。
人付き合いが嫌いなわけではない。相互フォロワーさんの中には、私が匿名アカウントだった頃から実名で深い交際をさせて頂いていた人も少なくない。約100名ほどいると思われる相互フォロワーさんのうち、7割くらいの人とはそういう関係だと思っている。
実は、気にし過ぎなのかも知れないが、相互フォロワーの書き込みを、長い間全て追いかけていた。友人達の反応は概ね「考えすぎだ」「暇人だな」といったものであって、自分でもそれは分かっていた。まあ、それでもそういう気持ちになる人と相互フォロワーになってきたつもりだった。
知人を大切に思う気持ちに変わりはないのだが、体力的には深夜のフォローが困難になりつつある上に、アカウントを実名ベースとしたので流石に昼間もフォローできない。つまりは人並みになろうとしているだけなのである。
SNS疲れ、という言葉があるようだが、私のようなことを続けていると疲れるのかもしれない。
本来、どの人とどの程度仲良くするかは、相手によって千差万別のはずである。しかし、SNSは、友達と異邦人と敵(ブロックした相手)の3通りしかいない。これって、まるでO型の人間関係の模式図のようである。A型が多い日本人には合わないのではないか。
そもそも、人間関係の濃さは連続的な値をとるものであるのに、SNSは友情を離散的な値に分けてしまう。それは、API を設計する上で仕方のないことかも知れないけど、離散化の陰で「ほどよいつきあい方」とするための工夫とか気持ちの持ちようとかが欠落してしまって、API に型押しされた友情になってしまっている人もいるのかな、とか思ったりした。
幸い、私自身はSNS疲れとは無縁である。それは、相互フォロワーを少なめにした結果、周囲が皆尊敬できる良い人になっているからなのかもしれない。
−−−
追加:フォローしていない人が悪い人、と言うわけではない。いちいちこういうことを断らなければならないところは、SNS疲れの要素ではある(笑)。
−−−
追加2:その後、ちょっとしたことで、一時的にSNS疲れを起こしてしまった。現在はほぼ直ったが、それでもややアクセスは少なめである。
今後更新頻度が下がります
別にこれまでの更新頻度も十分低かったところですが。
少しずつ、書く場所が増えてきています。twitter は既に盛んに書き込んでいますし、仕事場にも CMS があるので、そちらのメンテもしなくてはなりません。mixi は既に放置状態ですが、ここもそれに準ずる扱いになる可能性があります。
twitter で書くに適さない内容と分量の文章を書く場合に、ここともう一カ所から選択することになりますが、もう一カ所に書くこともあり得るので、という理由で更新頻度が下がるのでした。
なお、このサイト(及びはてなダイアリーのアカウント)を削除することはないと思います。何年かすると、主たる書き込み場所が再びここに戻ってくる可能性もありますし、ATND その他の認証システムと連動させる上でもこういうアカウントを維持する価値はあると思いますので。