3 に答える
ハミルトニアン サイクル (つまり、開始 = 開始) ではなく、NP 完全問題でもあるハミルトニアン パスに注目しています。ただし、26文字しかないため、グラフは一般的なものではありません. 26 文字よりも多くの記号を許可する場合、実際にはハミルトニアン パス検索と同等です。
ここに解決策があります: 逆の方法で考える必要があります:
- グラフの頂点は 26 文字です。
- x で始まり y で終わる各単語の文字 x と y の間にエッジがあります。
したがって、複数の単語が同じ文字で開始および終了する可能性があるため、実際にはマルチグラフが得られます。次に、あなたが見ているものは、オイラーパスと呼ばれます。これは、各エッジを正確に 1 回取るパスです。オイラー パスを見つけることは、多項式の問題です ( https://en.wikipedia.org/wiki/Eulerian_path )。これは、おそらく歴史上最初のグラフの問題の 1 つです。
ウィキペディアを引用すると：
有向グラフにオイラー トレイルがあるのは、最大で 1 つの頂点が (出次数) − (入次数) = 1 であり、最大で 1 つの頂点が (入次数) − (出次数) = 1 である場合に限られます。他の頂点の入次数と出次数は等しく、次数がゼロでない頂点はすべて、基になる無向グラフの単一の連結要素に属します。
これは、ハミルトニアン パスを検索するよりも、パスがあるかどうかを判断するためのはるかに優れた方法です。
サイズが 26 のアルファベットがあると仮定しましょう。
あなたの言葉を、すべての文字 {a, b, ..., z} に対応する 26 個の頂点を持つ有向グラフと考えてみましょう。
あなたが持っている単語ごとに、グラフに有向エッジを追加します - 単語を開始する文字から単語を終了する文字まで。
次に、このグラフのオイラー パスを探します。これは、すべてのエッジを 1 回だけ通過する (すべての単語を通過する)パスです。
次の有名な定理があります。
n 個の頂点上の有向グラフ G には、オイラー パス iff があります。少なくとも n-1 個の頂点の次数が次数と等しい。
さらに、Fleury のアルゴリズムなど、多項式時間で巡回を構築するためのアルゴリズムがあります。
ここで回答された同様の質問:マトリックス乗算が可能な場合の検出
ハミルトニアン経路よりもはるかに単純なオイラー経路問題として解くことができます。
各文字列をグラフのノードにする代わりに、各文字をグラフのノードにします。文字列が最初の文字で始まり、他の文字で終わる場合は、2 つの文字の間に有向辺を追加します。このグラフでオイラー経路を見つけると、必要な解が得られます。