完全な無向グラフのすべてのハミルトニアン サイクルを生成したいと考えています (ループとリバースが重複としてカウントされ、除外されるセットの順列)。
たとえば、{1,2,3} の順列は
標準順列:
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1
プログラム/アルゴリズムに出力してもらいたいもの:
1,2,3
321 はちょうど 123 後ろにあるので、312 はちょうど 123 1 回転した場所などです。
特定の集合に含まれるこれらのサイクルの数と、グラフにハミルトン サイクルがあるかどうかを検出するアルゴリズムについては多くの議論が見られますが、それらを完全な無向グラフ (つまり、数値の集合セット内の他の番号が先行または後続する可能性があります)。
このタスクを達成するためのアルゴリズムまたは C++ コードが本当に必要です。または、このトピックに関する資料がある場所を教えていただければ幸いです。ありがとう！
不要な順列を排除するために、出力にいくつかの制限を設けることができます。数1、...、Nを並べ替えたいとしましょう。いくつかの特別な場合を避けるために、N>2と仮定します。
単純な回転を排除するために、最初の場所が1であることを要求できます。これは、任意の順列を常にこの形式に回転できるためです。
逆をなくすには、2番目の数字が最後の数字よりも小さくなければならないことを要求できます。これは真実です。なぜなら、互いに逆である1で始まる2つの順列から、正確に1つがこのプロパティを持っているからです。
したがって、非常に単純なアルゴリズムですべての順列を列挙し、無効な順列を除外することができます。もちろん、可能な最適化もあります。たとえば、1で始まらない順列は、生成ステップで簡単に回避できます。
パスがサイクルの別のポイントで始まるパスと同じかどうかを確認する非常に怠惰な方法 (つまり、同じループまたは同じループの逆は次のとおりです。
1: 慣例により、すべてのサイクルは頂点番号が最も小さいものから開始し、隣接する 2 つの序数の小さい方の方向に継続することを決定します。
したがって、上記のパスはすべて同じ方法で記述されます。
2番目のその他の有用な情報は次のとおりです。
2 つのパスが同じであることを確認したい場合は、1 つをそれ自身と連結し、2 番目のパスまたは 2 番目のパスの逆が含まれているかどうかを確認できます。
あれは、
1 2 3 1 2 3
上記のすべてのパスまたはその逆が含まれます。すべてのハミルトニアンサイクルを見つけるプロセスは、このアルゴリズムが持つわずかな非効率性よりもはるかに遅いように見えるので、私はそれを投入できると感じました:)