正しい方向へのアドバイス/ガイダンスを探しています。
私の要件は、ソリューションを解決するのではなく、グラフを生成することです。
ハミルトニアン サイクルが 1 つだけのグラフ (NxN グリッド) を生成するアルゴリズムを実装しようとしています。1 つの固有のソリューションだけが重要であることに注意してください。グラフはノードの NxN グリッドになり、各ノードは上、右、下、左の 4 つの隣接ノードのみを持ちます。ノードにアクセスできるのは 1 回だけです。これとは別に、いくつかの特別なノードが存在する場合があります。
- デッドノード、つまりエッジ接続がない
- 入口ノードと出口ノードが固定されています。つまり、入口ノードと出口ノードはすでに定義されており、他のノードは指定されたノードに接続できません。それはすることができます。隣接ノード ｂ．ストレートノード
いくつかの例：
@ - means that nodes can be connected with adjacent nodes (top,right,bottom,left)
$ - indicated dead end (no connections with adjacent nodes)
Graph 1 =>
@-@-@
@-$-@
@-@-@
Solution 1 =>
1-2-3
8-$-4
7-6-5
here the solution of the graph is 1->2->3->4->5->6->7->8->1. Notice how the $ node was not included in the final solution.
私のアプローチ:
*n グリッドを使用して、グラフ上にランダムなデッド ノードを配置することから始めます。この後、ランダムな特殊ノードを配置します。次に、グリッド全体を横断する dfs 検索を実行して、特別なノード基準を満たし、すべてのノード (開始ノードを除く) を 1 回だけ訪問し、開始ノードで終了する有効なサイクルが存在することを確認します。これにより、完全なループになります。
私の質問:
ここで私が求めているのは、グラフに有効なサイクルが 1 つしかないことを確認するにはどうすればよいかということです。有効なハミルトニアン サイクルの数が 1 に減少するまで、サイクルごとにデッド ノードと特別なノードを追加することで、レベルを再帰的に反復することができます。これは私が実装しようと計画しているものです。
この問題にどのようにアプローチするのが理想的ですか?