algorithm - 最小数の新しいノードを追加して、グラフ内の最短経路を見つけるにはどうすればよいですか?

Question

追加されたノードの数が最も少ないグラフで最短経路を見つける必要があります。開始ノードと終了ノードは重要ではありません。指定された n ノード間のグラフにパスがない場合、いくつかのノードを追加して最短のツリーを完成させることができますが、新しいノードはできるだけ少なくしたいと考えています。

この問題を解決するには、どのアルゴリズムを使用できますか?

score 1 · Accepted Answer

開始ノードから開始します。

それがターゲットノードである場合は、完了です。

対象ノードである場合は、接続されているすべてのノードを確認します。本当なら終わり

接続されているノードのいずれかがターゲットノードに接続されているかどうかを確認します。true の場合は完了です。

それ以外の場合は、開始ノードと終了ノードに接続されているノードを追加します。終わり。

score 0 · Accepted Answer

パス内のノードの数を最小限に抑えたい (一般的なアルゴリズムのように重みの合計ではなく)。

その場合は、すべてのエッジに等しい重みを割り当て、最短経路を見つけます (汎用アルゴリズムを使用)。必要なものが手に入ります。

パスがない場合は、そのエッジをグラフに追加します。

サンズ。

PS: 各エッジに 1 の値を指定すると、パス内のノードの数は重み-1 になります (ソースノードと宛先ノードを除く)。

score 0 · Accepted Answer

遺伝的アルゴリズムを使用することをお勧めします。詳細については、こちらとこちらをご覧ください。簡単に説明すると、GA は、最適化および検索の問題に対する正確な解または近似解を見つけるためのアルゴリズムです。

可能なソリューションの初期集団を作成します。それらのどれが最も適しているかを見つけるために、フィットネス関数でそれらを評価します。その後、継承、突然変異、選択、交差などの進化生物学に触発された手法を使用する進化的アルゴリズムを使用します。

何世代にもわたって、問題に対する最も適切な (最短で読める) 解決策を見つけることができます。

3 に答える 3