algorithm - 最长路径的颜色编码算法

Question

首先，我想说的是，这是给大学分配的，我正在寻求帮助，以了解能够实现该算法的算法。
因此，我已经在这里找到了这个作业：
https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf

基本上，我们有一组由2个int表示的“卡片”，一个代表卡片的颜色，另一个代表数字。要完成的工作是找到最长的纸牌序列，例如UNO游戏，其中下一张纸牌是相同颜色或相同编号。
为此，在诅咒过程中已经实现了一系列算法，但是我们必须实现的最后一个算法是“颜色编码”，而现在我已经没时间了，仍然还不清楚它是如何工作的。
我将在此处放置文本图像以保持格式。




任何了解它的帮助将不胜感激。

谢谢

Answer 1

我想我可以为您提供帮助。
您的问题可以轻松转换为最长路径问题。长期以来，要找到长度为k的路径确实很难解决。即使当k相对较小（例如log（n）），人们仍然认为在多项式时间内是不可能的。

基本思想：您为图形多次着色，并希望您意外地为长度为k的路径着色。好吧，这种可能性很小，但是如果重复很多次，实际上的可能性就会很大。

但首先，让我们假设图中有一条彩色的路径。 “有色”甚至是什么意思？有色表示具有k个节点的长度为k-1的路径以k种不同的颜色着色。如果从颜色为1的节点v开始，该怎么办？
您将查看您的邻居，看看他们的颜色是否与您不同。如果这样做，则将它们添加到名为P（1）的集合中。
您将继续与某个邻居相邻，看看他们是否有一种颜色，该颜色尚未出现在颜色集中。只要找到尚未看到的新颜色，或者达到k-1种颜色，或者您看到其中一个节点具有已经看到的颜色，就可以这样做。在最后一种情况下，您中止任务，然后返回一切仍然良好的地方。

重要：我们为节点着色。长度为i的路径具有i + 1个节点和i条边。

更正式：
令P i（v）：= {S是（[[k]选择i + 1）|存在一条路径，该路径以S中的颜色着色，并以v结尾
P不是路径。 P包含一些我们称为S的颜色。
在这种情况下，S不是数字。它是不同颜色基数i + 1的子集。
例如：
P 3（v）可能看起来像= {{绿色，红色，黑色，黄色}，{粉红色，橙色，灰色，黄色}，{...}}。注意两次“黄色”吗？如果我继续添加更多的子集，则“黄色”将出现在每个集合中。为什么？因为这是我们末端节点v的颜色！
因此，P i（v）至少拥有一组所有不同颜色的S，长度为i的一条路径被着色。该路径以v结尾！

那是什么意思？
如果我们可以计算P k-1（v），并且集合不为空。存在长度为k的路径。太棒了

但是我们如何计算P k-1（v）？
这并不难：
如果我们要计算P i（v）。我们需要什么？
我们需要P i-1（x）。 X？为什么？ x是v的邻居！
---> g ----> y ---> o -----> 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）的新子集之一！为什么现在是v？
好吧，我们将路径扩展了一种颜色，因此最好将其保存在相应的颜色集中！
所以到目前为止我们看到了什么：
-您有一个集合P i（v），其中包含子集S，子集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 km）为单位。其中，m是边数，k是路径长度。
因此，现在我们可以在多项式时间内使用此算法来搜索k = log n长的路径。如果大于此值，那么不幸的是它不再是多项式了。

因此，现在我们有了一种算法，可以在多项式时间内找到一条“长”路径。可是等等。如果路径是彩色的，则只能这样做！
我不知道您的住所，但在我的世界中，图表默认情况下不会着色，尤其是不同颜色的路径也不会着色。

我们必须这样做。
我们用k种不同的颜色为k长度的路径着色的概率是多少？

有k！使用k种不同颜色为图形着色的许多方法。但是，有k种不同的方法可以用k种不同的颜色为路径着色，在这种情况下，它们可以多次出现。示例：黄色= y和绿色= g时，您有2！= 2个选项，其中颜色必须不同：（y，g）或（g，y）。当颜色不必不同时，您可以选择k ^ k = 2 ^ 2 = 4个选项。 （y，y），（g，g）和您已经看到的。
因此Pr [Path用diff着色。颜色] = k！/ k ^ k，大于e ^ -k，与1 / e ^ k相同。
所以您同意概率很小，对吧？
获得首次成功的预期尝试次数是多少？
这是期望值= 1 / p = e ^ k的几何分布。
因此，我们认为在尝试e ^ k之后，我们可以希望我们第一次有了一条彩色的道路。有时更少，有时更多。
概率。一次尝试失败的次数是1-e ^ -k，非常大。但是，如果我们说执行此Te ^ k次，则概率。 Te ^ k连续故障的数量变得非常小：（1-e ^ -k）^ Te ^ k <=（e ^ -e ^ -k）^ Te ^ k <= e ^ -T
这样的概率。 Te ^ k尝试后我们将成功的结果大于1-e ^ -T。那很小。

该算法现在看起来如何？
1）用k种不同的颜色随机给图形着色。
2）执行检查是否存在彩色路径的算法
如果有一个返回。如果不是，那就继续。
3）重复步骤1和2进行Te ^ k次。 （这很有趣，相信我）。
实际上不是。让计算机来做。

这种类型的算法称为蒙特卡洛类型随机算法。
它的运行时间以O（Te ^ k * 2 ^ k * km）为单位，并且错误“没有路径（但实际上有一个）”的概率小于e ^ -T（再次非常小）。 ）再次，对于k = log n，该随机算法实现多项式运行时间！