私はそれが大学の課題であることを明確にしたいと思います。アルゴリズムを理解する上で助けが必要です。 だから私はここで見つけることがカムこの割り当てました： https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf最長経路の色分けアルゴリズム
を基本的に我々はカードと番号のための別の色を表す2 int型のいずれかで表される「カード」のセットを持っています。行われる作業は、UNOゲームのように、次のカードが同じ色か同じ番号のような最長の一連のカードを見つけることです。 呪い中に一連のアルゴリズムが実装されていますが、私たちが実装しなければならない最後のアルゴリズムは「カラーコード」ですが、今は時間がなくなっています。 私はここにテキストのイメージを置いてフォーマットを保持します。 
上の任意のヘルプ
ありがとうございました
私はあなたを助けることができると思います。 問題は、最も長いパスの問題に簡単に変換できます。長さkのパスを見つけることは、長い間解決することが本当に難しかったです。 kが比較的小さくても、log（n）と言っても、人々は多項式時間ではそれができないと考えていました。
基本的な考え方：グラフに多くの時間を塗り、誤って長さkのパスに色を付けることを願っています。まあ、それの確率は非常に小さいですが、あなたがそれを何度も繰り返すと、確率は実際には非常に大きくなります。
まず、グラフに色付きのパスがあるとします。 「色付き」とはどういう意味ですか？色付きとは、k個のノードを有する長さk-1の経路がk個の異なる色で着色されていることを意味する。ノードv（色は1）から始めると、あなたは何をしますか？ あなたはあなたの隣人を見て、彼らの色があなたと違うかどうかを見ます。それらがある場合は、P（1）と呼ばれるセットに追加します。 ネイバーのいずれかを続行し、まだカラーセットに表示されていないカラーがあるかどうかを確認します。まだ見たことのない新しい色を見つけたり、k-1色に達するか、すでに見た色がノードの1つに見える限り、これを行います。最後のケースでは、ミッションを中止して、すべてがまだ良好だった場所に戻ります。
重要：ノードに色を付けます。長さiのパスは、i + 1個のノードとi個のエッジを持つ。
より公式： P i（v）：= {Sは（[k] i + 1を選択する）| vで終わるSの色で塗りつぶされたパスがあります。 Pはパスではありません。 Pには、Sと呼ばれる色のセットが含まれています。 この場合、Sは数字ではありません。これは、異なる色の基数i + 1のサブセットです。 例： P 3（v）は、{緑、赤、黒、黄色}、{ピンク、オレンジ、灰色、黄色}、{...}}のように見えます。 「黄色」が2回あることに注目してください。もし私がいくつかのサブセットを続けていたら、 "黄色"がすべてのセットに現れたでしょう。どうして？それは私たちのエンドノードvの色ですから！ したがって、P i（v）は、長さiの1つのパスが着色されているすべての異なる色の少なくとも1つの集合Sを保持します。このパスはv！
これはどういう意味ですか？ P k-1（v）を計算することができ、セットが空でない場合。長さkの経路が存在する。驚くばかり。
しかし、P k-1（v）はどのように計算されますか？ 難しいことではありません： P i（v）を計算したい場合。私たちは何が必要なのか？ P i-1（x）が必要です。バツ？どうして？ xはvの隣人です！ ---> g ----> y ---> o ----- x ------> v {緑、黄、オレンジ、xの色}はPの1つのサブセットですi-1（x）である。 Rと呼ぼう。 覚えていますか？ P i-1（x）は多くの異なるセットを有することができる。 {{緑、赤、黒、黄色}、{ピンク、オレンジ、灰色、黄色}、{...}}のように見えます。
これで、Rとxとvとの関係は正確には何ですか？ Rはxまでの長さi-1の色付きパスを示す色のセットです。 xの隣である頂点vがまだRに現れていない色を持っていれば、それをRに加えることができます。しかし、Rは1つの色を得ました。サイズ| R |は、現在i + 2です。 P i（v）の新しいサブセットの1つである必要があります。なぜ今はvですか？ さて、私たちは1つの色でパスを拡張したので、それに合わせて保存する方が良いでしょう！ これまで見てきたこと： - あなたは、それ自身i + 1個の多くの色を含んでいるサブセットSを含むセットP i（v）を持っています（vを忘れないでください） - セットP k -1（v）、あなたは長さkの経路を持ち、ビールを飲むことができます。- P i（v）は、P i-1（x）によって計算することができる。ここで、xはv！良いことは、vの色がP i-1（x）のサブセットの1つに現れたかどうかということだけです。これはRと呼んでいます。
どのように計算しますか最初から？ あなたはv 0の色であるP 0（v）から始まります。 次に、vの各隣接xについて、P 1（v）を計算します。 i-1を思い出すとP 1（v）はP 1-1（x）になります。 P 0（x）はやはりxの色にすぎない。 xとvの色が同じでない場合、それらはちょうどP（v）の最初の部分集合を形成しました！次に、P 1（x）を計算することによってP 2（v）が計算され、P 0（y）によって計算され、yはxの近隣である。 P k-1（v）に達していない限り、これは続きます。
複雑度：これはO（2^k km）で実行されます。ここで、mはエッジの数、kはパスの長さです。 これで、このアルゴリズムを多項式時間で使用して、k = log n longのパスを検索することができます。もしそれより大きければ、残念ながら多項式ではありません。
ここで、多項式時間で「長い」パスを見つけるアルゴリズムがあります。ちょっと待って。パスが色分けされている場合にのみ実行できます。 私はどこに住んでいるのかわかりませんが、私の世界ではグラフはデフォルトで色付けされておらず、特に異なる色のパスではありません。
私たちはそれを行う必要があります。 kの長さのパスをk個の異なる色で着色する確率はどれくらいですか？
kがあります。 k個の異なる色でグラフを色付けする多くの方法。しかし、k個の異なる色でパスを色分けするk^kの異なる方法があります。それらの色は複数回発生します。例：黄色= y、緑色= gの場合、色は（y、g）または（g、y）でなければならない2！= 2オプションがあります。色が違う必要がないときは、k^k = 2^2 = 4のオプションがあります。 （y、y）、（g、g）、あなたがすでに見たもの。 したがって、Pr [パスはdiffで色付けされています。色] = k！/ k^kであり、e^-kよりも大きく、1/e^kと同じである。 あなたは確率が非常に小さいことに同意します、そうですか？ 最初に成功する試行の回数はどれくらいですか？ これは期待値= 1/p = e^kの幾何分布です。 私たちはe^kを試した後、私たちが最初に色付きの道を望むと思っています。時々それはより少なく、時にはそれ以上です。 prob。1回の試行で失敗する確率は1-e^-kなので、非常に大きい。しかし、これをTe^k回実行すると言うと、probです。 （1-e^-k）^ Te^kは、非常に小さいものとなる。 Te^kを試行した後に成功することは、1-e^-Tよりも大きい。それは非常に小さいです。
アルゴリズムはどのように見えるのですか？ 1）k個の異なる色でグラフをランダムに色付けします。 2）色付きのパスがあるかどうかをチェックするアルゴリズムを実行します。 1つがあればそれを返します。単に続行しない場合。 3）ステップ1と2をTe^k回繰り返す。 （それは楽しい、私を信じて）。 それは実際にはありません。コンピュータにそれをさせてください。
このタイプのアルゴリズムは、モンテカルロ型ランダム化アルゴリズムと呼ばれます。 ランタイムはにあります。となります。偽の確率はありません（実際にはパスはありません）がe^-Tより小さい（やはり、非常に小さい。）また、k = log nの場合、このランダム化アルゴリズムは多項式ランタイムを達成する！