すべてのノードが座標平面上で相互に接続されているn個のノードのグラフが与えられている場合、m個のノードを含む最小距離のサブツリーを見つける最良の方法は何ですか？最小のサブツリーを見つける
私が見つけた唯一の解決策は、接続するすべてのノードの組み合わせを生成し、残りを無視してこれらのノードをKruskalまたはPrimのアルゴリズム経由で接続しようとした後、作成されたすべてのツリーを比較し、 1つですが、これは大きな木になると正確には効率的ではありません。
より高速で効率的なアルゴリズム/方法はありますか？
K-minimum spanning tree (k-MST)問題はNP完全であることが知られています。だからあなたは現在のアルゴリズムよりもはるかにうまく行かないでしょう。
しかし、コメントでは、グラフが座標平面から生成されていると言います。グラフ内のノードに関する幾何学的な情報があると仮定できます。 WWW compendium entryには、Euclidean k-MSTに多項式時間近似スキームを使用できることが記載されています。このペーパーは、1つを説明します：
Arora、Sanjeev （1996）、Polynomial time approximation scheme for Euclidean TSP and other geometric problems、In Proceedings of the 37th Ann。 IEEE Symp。コンピュータの基礎について 科学、ページ2-11。
彼らはk-MSTを直接そこに書いています。実際にもっと速くしたい場合は、そのアルゴリズムを試してみてください。
私はあなたがこの質問で使用する用語を取得していません。ノードには、最小の合計値を設定するか、値を持つエッジを設定しますか？そして、mは与えられた量ですか、あるいは固定されたノードの集合ですか？ –
エッジには値があり、その重みは座標平面上での距離です。 mは、m <= nのような任意の数です。 – kevmo314
エッジウェイトを負にすることはできますか？負の重みサイクルがありますか？ – JSmyth