最长路径的颜色编码算法
color-coding algorithm for the longest path
在任何事情之前，我想澄清一下，是的，这是一项大学作业，我正在寻求帮助以理解能够实现它的算法。
所以我有这个任务可以在这里找到：
https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf
基本上我们有一组 "cards" 由 2 int 表示，一个代表卡片的颜色，另一个代表数字。要做的工作是找到最长的卡片序列，例如 UNO 游戏，其中下一张卡片是相同颜色或相同数字。
为此，在诅咒期间已经实施了一系列算法，但我们必须实施的最后一个算法是 "color-coding"，现在我 运行 没时间了，但仍然不太清楚它是如何工作的.
为了保持格式，我会把文字的图片放在这里。
任何帮助理解它的人将不胜感激。
谢谢
我想我也许能帮到你。
您的问题可以很容易地转化为最长路径问题。找到一条长度为 k 的路径确实很难解决很长时间。即使k比较小，比如log(n)，人们仍然认为在多项式时间内是不可能的。
基本思路：您多次为图表着色，并希望您不小心为长度为 k 的路径着色。嗯，那个概率很小，但是如果你重复很多次，这个概率其实会变得很大
但首先，我们假设图中有一条彩色路径。 “有色”到底是什么意思？着色是指长度为 k-1 的路径，有 k 个节点，用 k 种不同的颜色着色。如果你从一个颜色为 1 的节点 v 开始，你会怎么做？
你会看看你的邻居，看看他们的颜色是否与你不同。如果是，则将它们添加到一个集合中，称为 P(1)。
您将继续使用其中一个邻居，看看他们是否有一种颜色，该颜色尚未出现在颜色集中。只要您找到您尚未见过的新颜色，或者您达到 k-1 种颜色，或者您看到其中一个节点具有您已经见过的颜色，您就会这样做。在最后一种情况下，你中止了任务并回到一切都还不错的地方。
重要提示：我们为节点着色。长度为 i 的路径有 i+1 个节点和 i 条边。
更正式：
让P i(v):= {S is element of ([k] choose i+1)| there exists a path, colored with the colors in S, which ends in v}
P 不是路径。 P 包含一些我们称为 S 的颜色集。
在这种情况下，S 不是数字。它是不同颜色的基数 i+1 的子集。
例如：
P 3(v) 可能看起来像这样 = {{green, red, black, yellow}, {pink, orange, grey, yellow},{...}}。注意到两次“黄色”了吗？如果我继续使用更多的子集，“黄色”就会出现在每组中。为什么？因为是我们结束节点的颜色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 的邻居
假设 {green, yellow, orange, color of x} 是 P i-1(x) 的一个子集。我们称它为R。
记住？ P i-1(x) 可以有很多不同的集合。它可能看起来像这样：{{green, red, black, yellow}, {pink, orange, gray, yellow},{...}}!
好的，那么与 R 和 x 和 v 的关系到底是什么？
R 是一组颜色，表示通向 x 的长度为 i-1 的彩色路径。如果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)。 P 1(v) 就是 P 1-1(x) 如果你还记得 i-1 的事情。 P 0(x) 又只是 x 的颜色。如果 x 和 v 的颜色不一样，它们就构成了 P 1(v) 的第一个子集！
然后通过计算 P 1(x) 计算 P 2(v)，P 1(x) 再次由 P 0(y) 计算，其中 y 是 x 的邻居。
只要我们还没有达到 P k-1(v)，这种情况就会继续。
至于复杂性：这在 O(2^k km) 中运行。其中 m 是边的数量，k 是路径的长度。
所以现在我们可以在多项式时间内使用这个算法来搜索 k = log n 长的路径。不幸的是，如果它大于那个值，它就不再是多项式了。
所以，现在我们有了一个在多项式时间内找到“长”路径的算法。可是等等。只有路径是彩色的，它才能这样做！
我不知道你住在哪里，但在我的世界里，图表默认没有颜色，尤其是不同颜色的路径。
我们必须这样做。
我们用 k 种不同颜色为 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 着色的。 colors]=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。而且还很小。
算法现在看起来如何？
- 用 k 种不同的颜色随机给图形着色。
- 执行检查是否有彩色路径的算法
如果有一个return它。如果不是就继续。
- 重复第 1 步和第 2 步 Te^k 次。 （这很有趣，相信我）。
实际上不是。让电脑来做。
这种算法称为Monte Carlo型随机算法。
它的运行时间在 O(Te^k2^kkm) 和错误的概率“不，没有路径（但实际上有一个）”小于 e^-T（同样，非常小。）再一次，对于 k = log n，这个随机算法实现了多项式运行时间！
在任何事情之前，我想澄清一下，是的，这是一项大学作业，我正在寻求帮助以理解能够实现它的算法。 所以我有这个任务可以在这里找到： https://www.labri.fr/perso/dorbec/AA/projet-uno.pdf
基本上我们有一组 "cards" 由 2 int 表示，一个代表卡片的颜色，另一个代表数字。要做的工作是找到最长的卡片序列，例如 UNO 游戏，其中下一张卡片是相同颜色或相同数字。 为此，在诅咒期间已经实施了一系列算法，但我们必须实施的最后一个算法是 "color-coding"，现在我 运行 没时间了，但仍然不太清楚它是如何工作的. 为了保持格式，我会把文字的图片放在这里。
任何帮助理解它的人将不胜感激。
谢谢
我想我也许能帮到你。 您的问题可以很容易地转化为最长路径问题。找到一条长度为 k 的路径确实很难解决很长时间。即使k比较小，比如log(n)，人们仍然认为在多项式时间内是不可能的。
基本思路：您多次为图表着色，并希望您不小心为长度为 k 的路径着色。嗯，那个概率很小，但是如果你重复很多次，这个概率其实会变得很大
但首先，我们假设图中有一条彩色路径。 “有色”到底是什么意思？着色是指长度为 k-1 的路径，有 k 个节点，用 k 种不同的颜色着色。如果你从一个颜色为 1 的节点 v 开始，你会怎么做？ 你会看看你的邻居，看看他们的颜色是否与你不同。如果是，则将它们添加到一个集合中，称为 P(1)。 您将继续使用其中一个邻居，看看他们是否有一种颜色，该颜色尚未出现在颜色集中。只要您找到您尚未见过的新颜色，或者您达到 k-1 种颜色，或者您看到其中一个节点具有您已经见过的颜色，您就会这样做。在最后一种情况下，你中止了任务并回到一切都还不错的地方。
重要提示：我们为节点着色。长度为 i 的路径有 i+1 个节点和 i 条边。
更正式：
让P i(v):= {S is element of ([k] choose i+1)| there exists a path, colored with the colors in S, which ends in v}
P 不是路径。 P 包含一些我们称为 S 的颜色集。
在这种情况下，S 不是数字。它是不同颜色的基数 i+1 的子集。
例如：
P 3(v) 可能看起来像这样 = {{green, red, black, yellow}, {pink, orange, grey, yellow},{...}}。注意到两次“黄色”了吗？如果我继续使用更多的子集，“黄色”就会出现在每组中。为什么？因为是我们结束节点的颜色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 的邻居
假设 {green, yellow, orange, color of x} 是 P i-1(x) 的一个子集。我们称它为R。
记住？ P i-1(x) 可以有很多不同的集合。它可能看起来像这样：{{green, red, black, yellow}, {pink, orange, gray, yellow},{...}}!
好的，那么与 R 和 x 和 v 的关系到底是什么？
R 是一组颜色，表示通向 x 的长度为 i-1 的彩色路径。如果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)。 P 1(v) 就是 P 1-1(x) 如果你还记得 i-1 的事情。 P 0(x) 又只是 x 的颜色。如果 x 和 v 的颜色不一样，它们就构成了 P 1(v) 的第一个子集！ 然后通过计算 P 1(x) 计算 P 2(v)，P 1(x) 再次由 P 0(y) 计算，其中 y 是 x 的邻居。 只要我们还没有达到 P k-1(v)，这种情况就会继续。
至于复杂性：这在 O(2^k km) 中运行。其中 m 是边的数量，k 是路径的长度。 所以现在我们可以在多项式时间内使用这个算法来搜索 k = log n 长的路径。不幸的是，如果它大于那个值，它就不再是多项式了。
所以，现在我们有了一个在多项式时间内找到“长”路径的算法。可是等等。只有路径是彩色的，它才能这样做！ 我不知道你住在哪里，但在我的世界里，图表默认没有颜色，尤其是不同颜色的路径。
我们必须这样做。 我们用 k 种不同颜色为 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 着色的。 colors]=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。而且还很小。
算法现在看起来如何？
- 用 k 种不同的颜色随机给图形着色。
- 执行检查是否有彩色路径的算法 如果有一个return它。如果不是就继续。
- 重复第 1 步和第 2 步 Te^k 次。 （这很有趣，相信我）。 实际上不是。让电脑来做。
这种算法称为Monte Carlo型随机算法。 它的运行时间在 O(Te^k2^kkm) 和错误的概率“不，没有路径（但实际上有一个）”小于 e^-T（同样，非常小。）再一次，对于 k = log n，这个随机算法实现了多项式运行时间！