グラフと言葉、つまりドミノについて少し。パート1。

パート 2 パート 3 パート 4 私がこの記事を書くように促されたのは、Java マルチスレッド クエストからの有害なタスクでした。開発者からからかいがあったわけではありませんが、このタスクは開発者によって「StringBuilder タスク」と呼ばれていました。彼女の状態の本質は、一連の単語（都市の名前が与えられた状態で、子供の言葉遊びを彷彿とさせる）をドミノの原理に従って配置する必要があり、n' 単語の最後の文字が配置される必要があるということでした。は単語 (n+1) go の最初の文字に等しく、与えられたすべての (個別の) 単語がそのような連鎖で加算されることが知られていました。目的の単語の連鎖に対して複数の選択肢を構成できる場合は、いずれも解決策として受け入れられます。状況は一見単純かつ明確であるにもかかわらず、問題の解決は決して簡単ではなく、StringBuilder を巧みに使用しても状況を救うことはできませんでした。この問題の開発者は、JavaRush 士官候補生を何度も恐怖させた惑星 Linear Chaos から注文された同形体であることが判明しました。予想通り、単純なアルゴリズムに単語のスキップを強制するチェーンが常に存在するため、表面的な解決策はバリデーターには適していませんでした。追加の「松葉杖」を積み上げる必要があり、問題が複雑になる一方で、一般的なケースでは解決策は近づきませんでした。また、単純な条件には同様に単純な解決策があるはずだという感覚がますます強まりました。戦術を変更して、より基本的な領域に少し飛び込む必要がありました。すぐにお断りしておきますが、私は決して自分がグラフ理論の専門家であるとは思っていません。これから触れようとするトピックは、おそらく唯一の例外を除いて、ドミノ単語問題を解く範囲を超えるものではありません。理論的な性質の脱線がいくつかあります。 ということで、グラフです。 グラフとは何ですか: グラフは、互いに接続された頂点のコレクション (セット、セット、リストなど) です。接続は通常エッジと呼ばれ、頂点はノードまたはノードとも呼ばれます。これはグラフです: これもグラフです: エッジについて方向があると言える場合、そのグラフは方向性があると呼ばれます: 最初の 2 つの図のグラフは方向性がありません。それらについて、エッジ (u, v) はエッジ (v, u) と同一であると言えます。つまり、たとえば、エッジ (0, 4) と (4, 0) は同じエッジです。有向グラフのエッジ上の矢印は、エッジ (u, v) が頂点 u から頂点 v へのパスであり、エッジ (v, u) が存在しないことを意味します。3 番目の写真にはエッジ (E、A) があります。エッジはありません (A、E)。最後の図を詳しく見てみましょう。頂点 F にはエッジがまったくないことがわかりますが、これは十分にあり得ます。また、頂点 A の近くにエッジ (ループ) が出現し、頂点 B と D の間に 2 つの異なる方向を向いたエッジがあることにも注目します。有向グラフでは、このようなアーティファクトが可能になります。このグラフが、お互いに贈り物をし合う知人のグループを表しているとします。貪欲な F は誰にも何もあげず、B と D はプレゼントを交換し (それぞれが他の誰かにプレゼントを贈ったという事実を除いて)、A はおそらく問題をうまく解決した際に自分自身にプレゼントを贈ったことがわかります。惑星リニアカオスからの問題。ところで、グラフの頂点は数値である必要も、数値を含む必要もなく、むしろコンテナーであることに注意してください。あらゆるオブジェクトを保存できます。グラフは接続を説明したものです。後で役立つ重要な用語 - 頂点に接続されたエッジの数 (または、頂点に付随するエッジの数) は、特定の頂点の次数と呼ばれます。たとえば、最初の図では、頂点 0 の次数は 2、1 の次数は 4、3 の次数は 3、2 番目の図の頂点 0 の次数は 1 です。この記事では、さまざまな種類のグラフについては詳しく説明しません。加重グラフも存在することだけを述べておきます。それぞれの端に特定の数字が付けられており、通過の「価格」を示します。接続グラフには、そのプロパティによって区別される多数のサブタイプがあります。たとえば、エッジがどこにもサイクルを形成していないグラフはツリーと呼ばれ (たとえば、「赤黒ツリー」などの素晴らしい名前を持つ興味深いファミリーがあります)、さまざまな重要なアルゴリズムやデータ構造で広く使用されています。 問題を解決するためにグラフを使用する これはすべて非常に興味深いとあなたは言いますが、これらすべては単語の連鎖を構築することとどのような関係があるのでしょうか? 最も直接的なことが判明しました。条件 { アムステルダム メルボルン ニューヨーク キエフ ウィーン } からのテスト例を見てみましょう。単語がくっついている「節点」の文字 {A、M、N、K、B} を任意の順序で書き留めて単語で 結び付けてみましょう。 ご覧のとおり、節点が文字である有向グラフができました。そしてエッジはそれらを接続する単語です。すべてのエッジを頂点から頂点へと横断し、各エッジを 1 回だけ訪問する方法を見つければ、問題は解決されます。図内のノードを少し異なる方法で分散してみましょう。 これで、グラフが閉ループであることがよくわかりました。シーケンスは任意の単語で始めることができ、それが正しい決定となります。ただし、問題の状況から、いずれか 1 つの解決策で十分であることがわかります。Vena を Vladimir に置き換えてみましょう。 結果は 2 つあります。1 つ目は、新しい頂点である文字 P を追加する必要があり、2 つ目は、グラフをループすることができなくなっていることがわかります。上記すべてを要約し、2 つの新しい用語を導入しましょう。 1. 各エッジを 1 回だけ訪問することでエッジを横断できる接続されたグラフは、「オイラー パス」を含むグラフと呼ばれます。このようなグラフの特徴 (エッジのない頂点がないことを除く) は、 2 つを除くすべての頂点(そして 2 つだけ)の次数が均等であることです。2. 元のノードに戻ることが可能であることが判明した場合、グラフに「オイラー サイクル」が存在すると言います。このようなグラフの特徴は (エッジのない頂点がないことを除く)、すべての頂点の次数が等しいことです。 次のような都市のリストを想像してみましょう: {モスクワ アナパ アドラー ロストフ ナ ドン 武漢}。グラフを作成しましょう。 図では、このグラフにオイラー パスがあることがわかります。奇数の次数を持つ頂点は 2 つだけあります。これらは M と L で、残りは偶数です。A の次数は 4 です。ループは 2 回カウントされ、P と Y は次数 2 になります。このスキームに基づいてオイラー ルートを構築できるアルゴリズムを思いついたとします。たとえば、リスト {M, A, A, P, Y の形式で, L} であれば、問題を解決します。指定された順序で単語を出力するのは単なるテクニックの問題です。したがって、ドミノ単語問題の解決策は、有向グラフでオイラー パス(サイクルが「フリー」)を見つけるアルゴリズムを実装することになります。次へ ->