に配置されたノードのネットワークがあります2D Grid。ノードのペアを接続で接続し、2D グリッド上の物理スペースを占有したいと考えています。接続自体が障害物になり、将来の接続はそれらの交差を回避するパスを使用する必要があります。
私は現在 を使用しておりA* algorithm、徐々に接続を確立しています。開始ノードから終了ノードまでの最短パスを見つけますが、作成する必要がある他の接続を考慮しないため、すべてのペアを接続した後の合計パス コストは最適ではありません。
これを解決できるアルゴリズムがあるかどうか、またはこれが NP 完全問題かどうかを知っている人はいますか? 関連資料に関する指示もいただければ幸いです。