私が書いた検索アルゴリズムと比較するための最適な検索ケースを決定しようとしています。
「必須」とマークされたノードと「開始」とマークされたノードのセットがあり、残りは「オプション」とマークされています。最初の拡張が「開始」ノードである場合、必要なすべてのノードを検出するために拡張する必要があるノードの最適な数を見つけたいと思います。
- 私が探しているのは最小スパニングツリーだと思いますが、「必須」ノードで終わらないすべてのブランチを剪定します。これはシュタイナー木問題ですか?
- グラフが重み付けされていない場合、シュタイナーツリーと最小スパニングツリーのサイズは同じですか?
- 木の大きさについて何か言えることはありますか?つまり、(最小スパニングツリーサイズのサイズ=平均最短パス*#必要なノード...これは真実ではないと思いますが、接続性などに基づいて平均を計算できると便利です)のようなものです。
いくつかの注意:
- 必要な各ノード間にパスが存在する必要がないため、これは巡回セールスマン問題ではありません。必要な各ノードを検出するだけです。
- 私のグラフは無向で重み付けされていません(またはそのことについては均等に重み付けされています)
- 私のグラフには、平均して約100の必須ノードがあり、場合によっては数千のオプションノードがあります。