平面グラフ内の任意の2点間の最適な経路

Question

フロアプラン（平面グラフ）内の任意の2点の間の最適なルートを見つけるアルゴリズムの後です。私は達成したいことを説明するためにイメージを添付しました。画像では、中空点を他の任意の点に接続し、同時に交差点を最小限にすることが目的です（この場合交差点はありません）。上記画像における

、のは私も灰色に青と緑と紫接続したいとしましょう、これは交差点を導入すると、その私は避けたいもの。

私は、平面グラフの任意の2点の間に最適な経路を見つけるアルゴリズムを、最適なものとして、最小交点を持つ最短経路を意味します。もし誰かが私を正しい方向に向けることができれば、本当に感謝しています。

Answer 1

あなたが探しているのは、VLSI回路設計のかなりの研究を見ており、ルーティング（その文脈で）と呼ばれています。

これは、設計要件に基づいて多数の考慮事項があるため、小さな答えはありません。いくつかの出発点はhereです。