graph - 有向巡回グラフでハミルトニアン パスを見つける

Question

有向加重グラフで最長の巡回パスを見つけるアルゴリズムがあるかどうかを知りたいです (これは、最大のハミルトニアン サブグラフを見つける問題だと思います)。

1 つの頂点から開始し、同じ頂点に戻る必要があります。最も可能性の高いノードが横断されます。

ありがとう

Answer 1

この問題は、すべての辺の重みが 1 である最適オイラー回路問題の特殊なケースです。元の問題は NP 完全です。さらに、この問題はハミルトニアン グラフ問題 (ハミルトニアン サイクルは、最適な回路がすべてのノードを通過する場合にのみ存在する) を解くために使用できるため、特別な場合の制限があっても NP 完全なままです。正確な解には (P = NP でない限り) 指数時間が必要です。このペーパーは役に立つかもしれません。この問題の多項式時間近似アルゴリズムと、グラフの次数が最大で 4 の場合の多項式時間アルゴリズムについて説明します。

チャオ、ユウ。「最大連続コストの最適オイラー回路」。電子情報通信学会論文誌 ファンダメンタルズ E90-A、いいえ。1 (2007): 274-280。

Answer 2

適切な近似により、ヒルベルト曲線が得られます。