無向グラフに相当するDelaunay三角形分割

Question

私は旅行セールスマンの問題に相当するパス計画アルゴリズムで作業しています。どれくらいのノードがあるのか​​分かりませんので、速度の精度を犠牲にしていきたいと思います。私の問題は、完全に接続されたグラフとしてモデル化することができます。ノード間の遷移のコストは、ノード間の距離以上に関連しています。私は、デラウネイ三角測量の上にある接続に私の検索スペースを制限したいと思っています（私が読んだことは、TSPのソリューションの接続の95〜100％がデラウネイ三角測量上にあるということです）。しかし、私のグラフは表現できない2Dまたは3Dのジオメトリとして、私は自分の表現に直接使用することはできません。幾何学的表現に従わないグラフに適用されるデラウネイ三角測量と同等の三角測量をもたらすアルゴリズムがあるか（接続コストは、過剰制約のために幾何学的距離として表現できない）

Answer 1

n次元の場合、グレイコードを試すことができます。