1

重み付き無向グラフがあり、辺の数 |E| があるとします。はノード数 |V| の約 k 倍、つまり |E| です。~= k * |V|。

ここで、1 つのノード、たとえば v が選択され、最小の平均コストで v を含むサイクルを見つけたいと考えています。(つまり、平均コストは、サイクルに沿ったエッジの平均重みを意味します。)

効率的なアルゴリズムはありますか？

申し訳ありませんが、1 つのポイントを見逃していました。このグラフのすべてのノードをサイクルに含める必要はありません。これはハミルトンサイクル問題とは異なります。

4

3 に答える 3

1

動的計画法に基づく O(|V||E|) アルゴリズムが実際に存在し、1978 年に Karp によって最初に記述されました ( http://www.sciencedirect.com/science/article/pii/0012365X78900110、または " Network Flows" (Ahuja、Magnant、Orlin 共著)。

Jan によって与えられた削減は、残念ながら正しくありません。なぜなら、コスト (v+2)/v のサイクルは一般に最小平均コスト サイクルではないからです。特に、開始点を含まないサイクルの平均コストは、任意の n に対して 1 < (n+2)/n になります。

于 2014-10-12T21:04:50.233 に答える
0

ドヴォルザークの答えは正しいです。元の質問では、サイクルが指定された頂点 v を通過する必要があります。平均コスト (v+2)/v のサイクルは、「頂点 v を通過しなければならない平均コストが最小の単純なサイクルを見つける」という問題に対する最適な答えになります。 .

Karp の論文では、「グラフで最小平均コスト サイクルを見つける」という問題が O(|V||E|) で解かれています。サイクルは特定の頂点を通過する必要はありません。

于 2015-06-05T18:20:59.260 に答える