

グラフ理論に関する質問です。  
頂点（ノード）間の位置関係をinvariantに保持する方法・表現を考えたいです。

具体的な例として、ある化合物の分子を考えます。  
ここで、その分子内の原子（グラフにおける頂点）たちと、  
各原子の三次元座標（3次元ベクトル）が与えられています。  
この三次元座標を用いて、頂点間の距離（グラフにおける辺の長さ）などが計算できます。

ここで、化合物内のある原子（i番目の原子とします）a_iから見た時に、  
他の原子たちa_j, a_k, a_m...の三次元空間における位置関係を  
回転などの操作に対してinvariantに保つ方法・表現を考えたいです。

例えば、与えられた三次元座標を使って原子間の距離を計算すれば、  
a_iから見た他の原子たちの距離関係は表現できますが、  
それでは三次元空間における位置関係の情報は失われてしまいます。

私は、a_iと他の任意の2つの原子a_jとa_kを用いて作られるすべての三角形から成る集合が、  
a_iから見た時の他の原子たちの三次元空間における位置関係を、invariantに保つと考えました。  
つまり、2つの原子間の距離d_ijではなく、  
3つの原子間の距離(d_ij, d_ik, d_jk)=三角形ならば、  
三次元空間における位置関係を保てるのではないかということです。  
（もちろんここでは、三角形の頂点である原子の種類も考慮して三角形を区別・定義します）

そしてこの三角形を、すべての原子 a_i について計算します。

しかし、これが合っているかどうかわかりません。  
特に、プログラムで実装する際には、  
鏡像異性体を区別する必要がある（回転に対してinvariantな必要がある）ので、  
ちょっと自信がありません。

どなたがご教授お願いします。

### 追記

このようなことをしたい目的として、何かしらの性質を保存するようなデータ構造で原子たちの位置関係を表したあと、機械学習を用いて‌​化合物の毒性などを予測したいと考えていま‌​す。機械学習は結局のところ関数近似なので‌​、本質的に同じ意味を持つデータには同じ入‌​力を与える必要があります。ただし、座標を‌​そのまま入力すると、本質的に同じ意味（原‌​子の位置関係）を持つデータが異なったデー‌​タとして入力されてしまうので、そこに問題‌​意識があります。


CC BY-SA 3.0
2017-10-05T03:29:16.313
38450
2017-10-07T05:46:41.890
2017-10-06T12:23:09.120
754
25649
question
アルゴリズム データ構造 数学 グラフ理論
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい


質問者様が、今考えているロジックを実装したとしても、「どの座標がどの座標にそれぞれ対応するか」の n!
通りある組み合わせの問題は解決しないのではないかと思っています。（もしかしたら、自分の理解が足りていないだけかもしれませんが、、）

そして、うまい一般的解法が思いつかなかったので、自分だったらこうする、という方針を記述いたします。

今やりたいことは、３次元座標の集合が与えられたときに、それが回転して一致するか否かであると理解しています。

### まず: 重心からの相対座標で考える

基準点がほしいので、それぞれの座標集合の平均(重心)を求め、各座標の相対位置を計算します。これで、この相対座標のセットに対して、回転の座標変換を行った際に一致するかどうかを判定すればよくなります。

### 座標の回転を決定する

そのままだと難しいので、何かしら対象の特徴的な値から決めることを試みます。たぶん、質問者様の回転に対しての invariant
というのはこのことを言っているのだと思います。

例えば、対象の座標セット (化合物) が、直鎖的であって、重心から最も離れた座標 (原子)
の位置は一意に定まったりしないでしょうか。そういった特徴的な点があるのであれば、それを利用できます。

また、原子の種類を考慮する、とのことですが、その化合物にとっての特徴的な原子たちはわかったりしないでしょうか。（たとえば:
特定の原子がただ一つだけ使われている）

ないし、座標セット全体でみると特徴点は導けないけれども、特定の原子の種類だけの座標セットを考えれば、特徴点がわかりやすくなったりしないでしょうか。

判定したい化合物の条件がわかっていれば、上記のような点を考慮して特徴点を２つ計算します。特徴点が２つあれば、重心と合わせて、３次元上の座標回転を決定できます。

### 回転後の同一性を判定する

座標は浮動小数な、実データなので厳密一致することはなく、必ず誤差が発生すると思います。なので、以下のロジックで対応する座標を見つけながら、距離を比較します。

許容誤差 e に対して、化合物の座標を e の格子で区切り、 `{３次元座標 -> 対応座標候補配列}` の連想配列(以下、 Hash)を用意します。

比較する化合物の片一方に対して、以下を行います。

[code]

    各座標 a_i に対応する格子に対して:
      格子自身と、それに隣接する格子 3*3*3 = 27 個それぞれに対して、
      Hash[格子] << a_i # Hash に a_i を追加する
    
[/code]

次に、もう一方の化合物に対して:

[code]

    各座標 a_j に対応する格子に対して:
      格子自身と、それに隣接する格子 3*3*3 = 27 個に対して、
      Hash の中の a_i 座標からから、
      a_j と一番近い座標 a_i を見つけ出す。
    
[/code]

そして、 a_i と a_j の距離を求めて、それが誤差 e
以下ならば、その座標は一致していたとみなします。すべての対応座標の距離の総和をとれば、それをもってどの程度座標セットが一致しているかの目安とできると思います。

### 実際には

特に、回転の精度を試行錯誤する必要があるかもしれません。その場合には、何回が微調整して上記一致アルゴリズムを走らせ、距離総和が小さくなるような回転を見つけます。距離総和がある一定以下であれば、一致しているとみなしてよいはずですが、この値が何であるかは試行錯誤して見つけ出すしかないと思っています。


CC BY-SA 3.0
2017-10-07T05:46:41.890
38506
2017-10-07T05:46:41.890
754
38450
answer