0

したがって、無向無加重グラフがあります。サイクルが含まれています。どのノードにも繰り返しアクセスせずに、最も多くのノードをアクセスするパスを見つけたいと思います。これはグラフ トラバーサルであるため、任意のノードで開始および終了できます。

背景調査: 巡回セールスマン問題 (TSP) を見てきました。この問題は異なり、開始した場所から終了することはできず、ウェイトはありません。他のアルゴリズムをいくつか調べましたが、この問題に適したものは見つかりませんでした。

グラフ サイズ: グラフには 100 個のノードがあります。10 個の切断されたノードを使用します。

更新:これを次の場所に移動しました: https://math.stackexchange.com/questions/243375/what-is-the-maximum-number-of-nodes-i-can-traverse-in-an-undirected-graph-訪問

4

2 に答える 2

1

ハミルトン閉路問題を探す

http://en.wikipedia.org/wiki/Hamiltonian_cycle

于 2012-11-23T22:07:50.383 に答える
0

非巡回グラフのアルゴリズムがあるウィキペディアのエントリをご覧ください。グラフには、問題を NP 困難にするサイクルがあります。

強く接続されたコンポーネントを表すノードで DAG を作成しようとします。次に、少なくとも、最も強く接続されたコンポーネントにアクセスするパスを見つけることができます。次に、個々の (強く接続されたコンポーネント) ノードを各サブグラフの最長パスに置き換えることで、そのパスを拡張できます。

サブグラフで最長パスを見つけることは、元の問題と同じになりましたが、少なくともグラフは小さくなっています。運が良ければ、副問題は簡単で、完了です。一般に、それらはそれほど小さくない可能性があり、高度なヒューリスティックを使用できます。たぶん、この論文またはこの質問を見てください（問題を完全に解決するためにそこにある答えを使用できますが、よくわかりません）

于 2012-11-24T10:28:19.997 に答える