之前我想說清楚的是它是一個大學作業，我正在尋求幫助理解算法，以便能夠實現它。 所以我這項任務的是凸輪在這裏找到： 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種顏色，或者你看到其中一個節點有一個你已經看到的顏色，你會這樣做。在最後一個例子中，你放棄了這個任務，回到了一切都還好的地方。
重要提示：我們爲節點着色。長度爲i的路徑具有i + 1個節點和i個邊。 （v）：= {S是（[k]選擇i + 1）的元素）（0,1,2）存在一條路徑，用S中的顏色着色，以v結尾P不是路徑。 P包含一些我們稱之爲S的顏色集合。 在這種情況下，S不是一個數字。它是不同顏色的基數i + 1的子集。 例如： P 3（v）可能看起來像這樣= {{green，red，black，yellow}，{pink，orange，gray，yellow}，{...}}。注意「黃色」兩次？如果我會繼續使用更多的子集，那麼每個集合中都會出現「黃色」。爲什麼？因爲它是我們的最終節點v的顏色！ 因此，P i（v）至少保存一組長度爲i的所有不同顏色的集合S，該長度爲i的一條路徑被着色。
這是什麼意思？ 如果我們可以計算P k-1（v），並且該集合不是空的。存在長度爲k的路徑。真棒。
但是我們該如何計算P k-1（v）？ 這並不難： 如果我們想計算P i（v）。我們需要什麼？ 我們需要P i-1（x）。 X？爲什麼？ x是v的鄰居！假設{綠色，黃色，橙色，x的顏色}是P的一個子集I-1（x）的。我們稱之爲R. 還記得嗎？ P i-1（x）可以有許多不同的集合。它可能如下所示：{{綠色，紅色，黑色，黃色}，{粉紅色，橙色，灰色，黃色}，{...}}！
好吧，R與x和v的關係究竟是什麼？ R是一組顏色，表示長度爲i-1的彩色路徑，該路徑導致x。如果與x相鄰的頂點v的顏色還沒有出現在R中，那麼我們可以將它添加到R.但是現在R已經獲得了一種顏色。它的大小，| R |，現在是i + 2。似乎這一定是P i（v）的新子集之一！爲什麼現在呢？ 那麼，我們已經擴展了一種顏色的路徑，所以最好保存在相應的集合中！ 那麼到目前爲止我們看到了什麼： - 你有一個集合P i（v），其中包含子集S，它本身包含i + 1多種顏色（不要忘記v） - 如果你有一個集合P k -1（v），你有一條長度爲k的路徑，你可以喝一杯啤酒。 P i（v）可以通過P i-1（x）來計算，其中x是v的鄰居。最好的部分是你唯一要檢查的是v的顏色是否出現在P i-1（x）的一個子集中，我們稱之爲R.
你如何計算它從一開始就？ 你從P 0（v）開始，這只是v的顏色 然後對於v的每個鄰居x，計算P 1（v）。如果你記得i-1的話，P 1（v）就是P 1-1（x）。 P 0（x）再次只是x的顏色。如果x和v的顏色不一樣，它們就形成了P 1（v）的第一個子集！ 然後通過計算P 1（x）來計算P 2（v），其再次由P 0（y）計算，其中y是x的鄰居。 只要我們還沒有達到P k-1（v），就會繼續。
至於複雜度：這運行在O（2^k公里）。其中m是邊的數量，k是路徑的長度。 因此，現在我們能夠在多項式時間內使用此算法來搜索k = log n long的路徑。如果它比這更大，不幸的是它不再是多項式。
因此，現在我們有一個算法可以在多項式時間內找到「長」路徑。可是等等。它只能這樣做，如果路徑是彩色的！ 我不知道你住在哪裏，但在我的世界裏，圖表並沒有默認着色，特別是沒有不同顏色的路徑。
我們必須這樣做。 我們用k種不同顏色給k長度的路徑着色的概率是多少？
有k！許多方法使用k種不同的顏色對圖進行着色。但是有不同的方法可以用k種不同的顏色對路徑進行着色，並且可以多次出現。例如：對於黃色= y和綠色= g，您有2！= 2選項，其中顏色必須不同：（y，g）或（g，y）。當顏色不必不同時，您有k^k = 2^2 = 4個選項。 （y，y），（g，g）和你已經看到的。 So Pr [路徑是用差異着色的。顏色] = k！/ k^k，它大於e^-k，這與1/e^k相同。 所以你同意這個概率很小，對吧？ 獲得第一次成功的嘗試次數是多少？ 這是一個期望值= 1/p = e^k的幾何分佈。因此，我們認爲在嘗試之後，我們可以第一次希望我們有一條彩色的道路。有時候更少，有時更多。 概率。一次嘗試的失敗是1-e^-k，非常大。但如果我們說執行這Te^k次，概率。的碲^ k個連續失敗變得非常小：（1-E^-k）^碲-1K-< =（E^-e^-k）^碲-1K-< = E^-T 所以概率。我們將在Te^k嘗試後成功，大於1-e^-T。這是非常小的。
怎樣的算法現在看？ 1）用k種不同的顏色隨機着色。 2）執行檢查是否有彩色路徑的算法 如果有一個返回它。如果不只是繼續。 3）重複步驟1和2 Te^k次。 （這很有趣，相信我）。 其實並非如此。讓電腦做到這一點。
這種類型的算法的被稱爲蒙特卡羅型隨機算法。 其運行時是O（特^ K * 2^K *公里）和概率的假「沒有沒有一個路徑（但實際上有一個）」大於E^-T（小一遍，非常小）。而且，對於k = log n，這個隨機算法實現了多項式運行時間！