エンドレスな座標における距離の求め方

1. 前提

2次元座標xyを考える。

x成分もy成分も0以上a未満とする。

点が、座標の各成分がaを超えるように微小距離だけ移動すると、その成分はaだけ減算される。

点が、座標の各成分が0を下回るように微小距離だけ移動すると、その成分はaだけ加算される。

(上2つはつまり、右端と左端、上端と下端がそれぞれ繋がっているということです。)

2. 難しさ

この時、右上の頂点(a,a)に限りなく近い点と、左下の頂点(0,0)の点の距離はいかほどでしょうか。

通常であればa√2ですね、(a,a)から左下へ向かって(0,0)まで行くのにa√2だけ移動する必要があるからです。

ですが、今回のエンドレス座標では、(a,a)から右上に向かうと、全く移動せずに(0,0)に到着します。よって、距離0です。

このようにエンドレス座標では、2点の間に複数通りの距離があって、どれが最も近いのかを考えなければいけないのです。

例えるなら山手線ですね。秋葉原から神田まで外回りだと一駅ですが、内回りだと30-1=29駅です。

3. 問題

b,c,d,eは全て0以上a以下であるとします。

エンドレス座標において、(b,c)と(d,e)の距離はいくらほどでしょうか。

4. 解説

エンドレス座標は、同じ座標が8方向に永遠と繰り返されていたものであると考えることができる。すなわち、次のように考えてよい。

今、青い点が9つ描画されている中で、(b,c)に最近のものとの距離を求めれば、それがエンドレス座標における(b,c)と(d,e)の最短距離となる。

青い点9つの座標を示すと次の通り、パターン「\(d(?:[+\-]a)?, e(?:[+\-]a)?\)」にマッチする座標で表される。

これら9通りの距離

((b-d±{a or 0})^2+(c-e±{a or 0})^2)^0.5

を全て求め、その最小値を求めれば最短距離が求められる。

5. 余談: 

5-1. 次元の呪い

ニューラルネットワークモデルでは、パラメータが増えると解の探索難易度が指数関数的に増大することが知られている。この現象は「次元の呪い」と呼ばれる。

エンドレス座標でも同様のことが発生する。

エンドレスn次元座標において、求めなければいけない距離は3^n通り存在する。

例えばもしも我々の住む宇宙がエンドレス3次元空間とみなせる構造をしているのだとしたら、任意の2点間の最短距離を求めるには27通りの距離を検証しないといけなくなる。

またエンドレス1次元空間でも3通りの距離を検証することになる。

5-2.  山手線の最短距離を求めるには3通りの検証が必要

例えば2章で例示した山手線の路線はエンドレス1次元座標とみることができる。東京から秋葉原までの駅数は、内回りの場合と外回りの場合で2通り存在するが、4章の方法では求めるべき距離は3通り存在することになる。

図に書いて説明しよう。図5-1は神田-秋葉原間を切り開いてエンドレス座標にした山手線路線図である。

図5-1

図5-1のように濃い赤で示した東京から、青で示した上野まで2通りの距離を求める分には問題ない。

しかし、図5-2のような2通りの距離を求めた場合はどうだろうか。

図5-2

濃い赤から青までの距離を2通り求めても、東京上野間の最短距離は求められない。

このような事態を避けるため、図5-1と図5-2を連結して、3通りの距離を求める必要があるのである。(図5-3)

図5-3