1つのグラフG = (V, E)が与えられたとき、バックトラック法を用いてHamiltonian Circuitを見つけなければなりません。 任意の頂点’a’から探索を開始します。 この頂点’a’が暗黙の木のルートになります。 我々の部分解の最初の要素は、構築されるべきハミルトニアンサイクルの最初の中間頂点です。 次の隣接する頂点は、アルファベット順に選択される。 いずれかの段階で、任意の頂点が頂点a以外の頂点とサイクルを作った場合、行き止まりになったとします。 この場合、1ステップ後退し、再び別の頂点を選択して探索を開始し、部分解から要素を削除する必要があることをバックトラックします。 バックトラックによる探索は、ハミルトニアンサイクルが得られれば成功です。
解答。
次に、aに隣接する頂点bを選択します。
次に、’b’に隣接する’c’を選択します。
次に、’c’に隣接する’d’を選択します。
次に、’d’に隣接する’e’を選択します。
次に、’e’に隣接する頂点’f’を選択します。 f’に隣接する頂点はdとeですが、彼らはすでに訪れています。 そのため、行き止まりとなり、1ステップ戻って、部分解から頂点’f’を削除します。
バックトラックの結果、’e’に隣接する頂点はb、c、d、fであり、このうち頂点’f’は既にチェック済みであり、b、c、dは既に訪れています。 そこで、再び1ステップバックトラックします。 ここで、dに隣接する頂点はe、eがすでにチェックされているfであり、fの隣接はdとeである。もし、eの頂点が再訪されたら、死んだ状態になる。
ここで、cに隣接するのが「e」、「e」に隣接するのが「f」、「f」に隣接するのが「d」、「d」に隣接するのが「a」となります。 ここでは、開始点の頂点’a’以外のすべての頂点が一度だけ訪れるので、ハミルトニアンサイクルが得られます。 (a – b – c – e – f – d – a)となります。
再びバックトラック
ここでは、1つのハミルトニアン回路を生成しました。
ここでは1つのハミルトニアン回路を生成しましたが、別の頂点を考えることで別のハミルトニアン回路を得ることもできます。