私はランダムな無向ソーシャルグラフを持っています。
できればハミルトン路を見つけたいです。または、不可能な場合（または多項式時間で可能かどうかを知ることができない場合）、一連のパス。この「一連のパス」（N個のノードすべてが1回だけ使用される）では、パスの数を最小限に抑え、パスの平均の長さを最大限に増やしたいと思います。（したがって、単一ノードのNパスの自明な解決策はありません）。
すでにノードとエッジの隣接行列を生成しました。
助言がありますか？正しい方向へのポインタ？問題のNP完全（？）の性質のため、これにはヒューリスティックが必要になることを認識しており、「十分に良い」答えで大丈夫です。また、Javaでこれを実行したいと思います。
ありがとう！
私があなたの質問を正しく解釈している場合、「複数のパス」の問題に対する最良の解決策はハミルトンパスであり、存在するかどうかを判断することは NP 困難であることが知られているため、あなたが求めているのは依然として NP 困難です。 . さらに、ハミルトニアン パスが存在しないことが保証されている場合でも、この問題を解決することは依然として NP 困難である可能性があります。そのノードを含む自明なパスと、残りのグラフのハミルトニアン パス。その結果、P = NP でない限り、問題に対する多項式時間アルゴリズムは存在しません。
これがお役に立てば幸いです。否定的な結果で申し訳ありません。
Angluin と Valiant は、十分に密な Erdos-Renyi ランダム グラフでほぼ常に機能するほぼ線形時間のヒューリスティックを提供しました。これは、 Wilf の 121 ページに記載されています。おそらく、ランダム グラフはErdos-Renyi ではありませんが、ヒューリスティックはとにかく機能する可能性があります (「失敗」した場合でも、(うまくいけば) 長いパスが得られます。貪欲にこのパスを使用して、AV を再度実行します)。
お気づきのように、多項式時間には正確な解はありません。ただし、いくつかのランダム検索方法を試すことができます。私のお勧めは、遺伝的アルゴリズムから始めて、タブー検索を試してみることです。
各個体がノードの順列である遺伝的アルゴリズム (交差なし) を使用します。これにより、各世代で「一連のパス」が得られ、パスの最小数 (1) と最大の平均に進化します。長さ (N)。