ミンコフスキー距離、マンハッタン距離、ユークリッド距離、チェビシェフ距離、どれ1つ聞いたこともないわ～

ニュートンは、太陽を公転する地球の運動や木星の衛星の運動を統一して説明することを試み、ケプラーの法則に、運動方程式を適用することで、万有引力の法則（逆2乗の法則）が成立することを発見した。これは、『2つの物体の間には、物体の質量に比例し、2物体間の距離の2乗に反比例する引力が作用する』と見なす法則である。力そのものは、瞬時すなわち無限大の速度で伝わると考えた。式で表すと、万有引力の大きさ${\displaystyle F}$は、物体の質量を${\displaystyle M,m}$、物体間の距離を${\displaystyle r}$として、

${\displaystyle F=G{\frac {Mm}{r^{2}}}}$

となる。${\displaystyle G}$は万有引力定数と呼ばれる比例定数で、

${\displaystyle G=6.67259\times 10^{-11}{\mbox{m}}^{3}\cdot {\mbox{s}}^{-2}\cdot {\mbox{kg}}^{-1}}$

である。（因みに「この式が全ての物体の間で成立する」と考えると「木から落ちるリンゴにも適用することができる」と考えることができるのである。）

地球の質量を${\displaystyle M}$、リンゴの質量を${\displaystyle m}$、地球の半径を${\displaystyle R}$とすれば、万有引力の大きさは、${\displaystyle F=G{\frac {Mm}{R^{2}}}}$であり、リンゴの運動方程式は、加速度を${\displaystyle g}$として、${\displaystyle mg=G{\frac {Mm}{R^{2}}}}$となる。すなわち、地球重力による加速度（重力加速度）は

${\displaystyle g={\frac {GM}{R^{2}}}}$

となり、すべての物質について同じ値になる。

地球表面では重力加速度は約9.8m/s²であり、地球の半径は約6400kmであるので、上記の式から地球の質量を

${\displaystyle M={\frac {gR^{2}}{G}}\simeq 6\times 10^{24}}$kg

のように求めることができる。同様に、他の惑星上での重力加速度も求めることができる。

万有引力 - Wikipedia

⇧  皆々様、ご存知、「万有引力」の 説明ですね。

どうもボクです。今回も、のっけから意味のない画像で始まるという。ということで、「距離」について調査していこうって感じです。

距離と空間距離

なんか、Wikipediaさんに聞いたら、

距離（きょり、独: Entfernung）とは、ある2点間に対して測定した長さの量をいう。本項では日常生活および高校数学の範囲内で使われている距離について触れる。大学以上で扱うより専門的・抽象的な距離については距離空間を参照。

距離 - Wikipedia

⇧  「距離空間」なるものが。というか、恐れていたことが...「大学以上で扱う専門的・抽象的な距離」って、サラッと書かれてるけども...

距離空間（きょりくうかん、metric space）とは、距離関数（きょりかんすう）と呼ばれる非負実数値関数が与えられている集合のことである。

古代より、平面や空間、地上の 2 点間の離れ具合を表す尺度である距離は測量や科学、数学において重要な役割を果たしてきた。1906年にモーリス・フレシェは、様々な集合の上で定義された関数の一様連続性の概念を統一的に研究した論文 Fréchet (1906)^{[注釈 1]}において、ユークリッド空間から距離の概念を抽出して用い、距離空間の理論を築いた。

平面 R² の上の 2 点 P₁ = (x₁, y₁), P₂ = (x₂, y₂) の間の距離にもマンハッタン距離

${\displaystyle d_{1}(P_{1},P_{2}):=|x_{1}-x_{2}|+|y_{1}-y_{2}|}$

やユークリッド距離

${\displaystyle d_{2}(P_{1},P_{2}):={\sqrt {(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}}}$

などがあり、同じ集合に対して何種類もの異なる距離関数を考える事も少なくないため、集合 X と距離関数 d を組にして (X,d) と書き、距離空間と呼ぶ。

距離空間 - Wikipedia

⇧ 道理で、『ミンコフスキー距離、マンハッタン距離、ユークリッド距離、チェビシェフ距離』ってどれも聞いたことがないわけですわ...

qiita.com

⇧  上記サイト様が、分かりやすく説明してくれています。

「ミンコフスキー距離」については、英語版 のWikipediaに情報が載ってるらしい、日本語版が無いのが謎なんですけど...

英語版のWikipediaによりますと、

The Minkowski distance is a metric in a normed vector space which can be considered as a generalization of both the Euclidean distance and the Manhattan distance.

Minkowski distance - Wikipedia

⇧ 「ノルム線型空間」における距離で、「ユークリッド距離」、「マンハッタン距離」と一般的に見なされてる、と。

The Minkowski distance of order p between two points

${\displaystyle X=(x_{1},x_{2},\ldots ,x_{n}){\text{ and }}Y=(y_{1},y_{2},\ldots ,y_{n})\in \mathbb {R} ^{n}}$

is defined as:

${\displaystyle D\left(X,Y\right)=\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{1/p}}$

For ${\displaystyle p\geq 1}$, the Minkowski distance is a metric as a result of the Minkowski inequality. When ${\displaystyle p<1}$, the distance between (0,0) and (1,1) is ${\displaystyle 2^{1/p}>2}$, but the point (0,1) is at a distance 1 from both of these points. Since this violates the triangle inequality, for ${\displaystyle p<1}$ it is not a metric.

Minkowski distance - Wikipedia

⇧  の式で、「ミンコフスキー距離」が求まり、

Minkowski distance is typically used with p being 1 or 2, which correspond to the Manhattan distance and the Euclidean distance, respectively. In the limiting case of p reaching infinity, we obtain the Chebyshev distance:

Minkowski distance - Wikipedia

⇧   「p = 1」の時が、「マンハッタン距離」、「p = 2、３、４...」の時が、「ユークリッド距離」、「p = ∞」の時が、「チェビシェフ距離」であると。

「ノルム線型空間」は、日本語のWikipediaにあるけど、割愛で、というか、最早、理工系の大学で学んでない人間にとっては、「未知との遭遇」っすわ...

ミンコフスキー距離を算出してみる

とりあえず、 

The Minkowski distance of order p between two points

${\displaystyle X=(x_{1},x_{2},\ldots ,x_{n}){\text{ and }}Y=(y_{1},y_{2},\ldots ,y_{n})\in \mathbb {R} ^{n}}$

is defined as:

${\displaystyle D\left(X,Y\right)=\left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{1/p}}$

Minkowski distance - Wikipedia

っていう式が存在し、 

• ミンコフスキー距離
  • p = 1
    マンハッタン距離
  • p = 2、3、4...
    ユークリッド距離
  • p = ∞
    チェビシェフ距離

ってことが分かったので、 

judge.u-aizu.ac.jp

⇧  上記の問題にトライしていきますか。

Eclipse を起動し、適当なJavaプロジェクト、クラスを作成。

コーディングはこんな感じ。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Minkowski {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    try {
      int n = Integer.parseInt(br.readLine()); // 何次元か
      String[] x = br.readLine().split("\\s"); // x座標
      String[] y = br.readLine().split("\\s"); // y座標
      double d = 0;  // 距離
      List<Double> mdList = new ArrayList<>(); // 距離のリスト
      
      // マンハッタン距離（p = 1 のとき）
      for (int i = 0; i < n; i++) {
        // 絶対値の合計値
        d += Math.abs(Double.parseDouble(x[i]) -Double.parseDouble(y[i]));
      }
      mdList.add(d);
      d = 0;
      
      // ユークリッド距離（p = 2 のとき）
      for (int i = 0; i < n; i++) {
        // 絶対値を2乗した値の合計値
        d += Math.pow(Math.abs(Double.parseDouble(x[i]) -Double.parseDouble(y[i])), 2);
      }
      // 平方根にして格納
      mdList.add(Math.sqrt(d));
      d = 0;
      
      // ユークリッド距離（p = 3 のとき）
      for (int i = 0; i < n; i++) {
        // 絶対値を3乗した値の合計値
        d += Math.pow(Math.abs(Double.parseDouble(x[i]) -Double.parseDouble(y[i])), 3);
      }
      // 立方根にして格納
      mdList.add(Math.cbrt(d));
      d = 0;
      
      // チェビシェフ距離（p = ∞）
      for (int i = 0; i < n; i++) {
        // 最大値を算出
        d = Math.max(d, Math.abs(Double.parseDouble(x[i]) -Double.parseDouble(y[i])));
      }
      mdList.add(d);
      
      // 結果を出力
      for (Double md: mdList) {
        System.out.printf("%.10f\n", md);
      }
      
    } catch (NumberFormatException | IOException e) {
      // TODO 自動生成された catch ブロック
      e.printStackTrace();
    }
  }
}

そしたらば、実行で。

入力値は、

Input

１行目に整数 nn が与えられます。２行目にベクトル xx の要素 {x1,x2,...xn}{x1,x2,...xn}、３行目にベクトル yy の要素 {y1,y2,...yn}{y1,y2,...yn} が空白区切りで与えられます。入力はすべて整数値です。

ミンコフスキー距離 | プログラミング入門 | Aizu Online Judge

ということで、

できました～。
なんというか、実際の業務で「立方根」とか使う機会なんて、訪れるのかしら？

p = 4、p = 5 とかになってきたら、「平方根」「立方根」の組み合わせとかで表現するんですかね？

まぁ、モヤモヤ感が半端ないですが...

今回はこのへんで。