4

私が書いた検索アルゴリズムと比較するための最適な検索ケースを決定しようとしています。

「必須」とマークされたノードと「開始」とマークされたノードのセットがあり、残りは「オプション」とマークされています。最初の拡張が「開始」ノードである場合、必要なすべてのノードを検出するために拡張する必要があるノードの最適な数を見つけたいと思います。

  • 私が探しているのは最小スパニングツリーだと思いますが、「必須」ノードで終わらないすべてのブランチを剪定します。これはシュタイナー木問題ですか？
  • グラフが重み付けされていない場合、シュタイナーツリーと最小スパニングツリーのサイズは同じですか？
  • 木の大きさについて何か言えることはありますか？つまり、（最小スパニングツリーサイズのサイズ=平均最短パス*＃必要なノード...これは真実ではないと思いますが、接続性などに基づいて平均を計算できると便利です）のようなものです。

いくつかの注意：

  1. 必要な各ノード間にパスが存在する必要がないため、これは巡回セールスマン問題ではありません。必要な各ノードを検出するだけです。
  2. 私のグラフは無向で重み付けされていません（またはそのことについては均等に重み付けされています）
  3. 私のグラフには、平均して約100の必須ノードがあり、場合によっては数千のオプションノードがあります。
4

1 に答える 1

3

「必須」とマークされたノードのセットと「開始」とマークされたノードがあり、残りは「オプション」とマークされています。最初の拡張が「開始」ノードであることを考慮して、必要なすべてのノードを検出するために拡張する必要があるノードの最適な数を見つけたいと考えています。

ノードを拡張するコストが任意である場合、これはノード重み付きシュタイナー木の問題であり、妥当な複雑性理論の仮定の下では、比率が o(log n) の多項式時間近似アルゴリズムはありません。

私が探しているのは最小のスパニング ツリーだと思いますが、「必須」ノードで終わらないすべてのブランチが削除されます。

いいえ、これは一般的に最適ではありません。たとえば、グラフで

       s
      /|\
     / | \
    *  |  *
   /   |   \
  /    |    \
 r1----*----r2,

考えられる 1 つの MST は、剪定すると/|\またはのよう/\に見えますが、最適解は のようになり_|_ます。

木の大きさについて何か言えることがあれば教えてください。

理論的に言えば、シュタイナー ツリーの整数プログラムの LP 緩和の双対を解くことで下限を得ることができます (実際には、考えているサイズのグラフを使用して、ソルバーが決定できたとしても驚かないでしょう)。最適なシュタイナー木をまっすぐ上に）。

しかし、実際には、これは人々が検索アルゴリズムを評価する方法ではありません。

于 2012-04-07T17:06:14.167 に答える