Tag: 算法

所有对最短路径问题的最快实现？

我有一个加权图表30k节点160k边，没有负权重。 我想计算从所有节点到其他节点的所有最短路径。 我想我不能假设任何特定的启发式来简化问题。 我试图使用这个Dijkstra C实现http://compprog.wordpress.com/2007/12/01/one-source-shortest-path-dijkstras-algorithm/ ，这是针对单个最短路径问题，调用函数dijkstras （）我所有的30个节点。 你可以想象，它需要很长时间。 目前我没有时间自己编写和调试代码，我必须尽快计算这些路径并将它们存储在数据库中，这样我就可以找到另一个更快的解决方案了，你有没有有小费吗？ 我必须在最近的8GB内存的macbook pro上运行它，我想找到一个不超过24小时完成计算的解决方案。 非常感谢提前!! 欧亨尼奥

在给定n个点的平面中找到正方形

给定一个平面中的n个点，可以形成多少个方格…… 我通过计算每个2点之间的距离，然后对它们进行排序，并在validation点和斜率后查找具有四个或更多相等距离的点中的方块来尝试此操作。 但这看起来像是一种复杂性很高的方法。 任何其他想法……？ 我认为用于检查相等距离的线段的动态编程可能会起作用……但是无法将想法弄得恰到好处…… 任何更好的想法？ PS：正方形可以是任何方式。 它们可以重叠，有一个共同的一面，一个正方形在另一个… 任何有助于我更好地理解问题的链接都是可观的……如果可能的话，请提供示例代码来执行上述操作…

第n个Fibonacci数的调用次数

请考虑以下代码段： int fib(int N) { if(N<2) return 1; return (fib(N-1) + fib(N-2)); } 假设从主要调用fib ，N为10,35,67，……（比如说），对fib进行了多少次调用？ 这个问题有什么关系吗？ PS：这是一个理论问题，不应该被执行。 编辑： 我知道其他方法可以更快地计算Fibonacci系列。 我想要一个解决方案来计算fib的调用次数fib（40），fib（50），…没有编译器的帮助，并且在考试条件下你应该回答40个类似于这个规定的问题时间（约30分钟）。 谢谢，

给定一组点，我如何找到彼此最远的两个点？

可能重复： 最大线性尺寸2d点集 我可以计算每个点之间的距离并取最大值，但是当有大（> 1000）点数时，这听起来不是一种非常有效的方法。 注意：这适用于iPhone，因此我没有大量的处理能力。

如何将64位哈希值缩短到48位值？

我已经在库中有64位散列函数（C编码），但我只需要48位。 我需要将64位散列值减少到48位值，但它必须以安全的方式才能最小化冲突。 散列函数是一个非常好的64位散列函数。 它已经通过SMHasher（“DieHarder”哈希测试）进行了测试，并且certificate比Murmur2更好。 据我的同事们说，在lib中实现64位散列的算法是xxHash，用SMHasher测试并得到Q.Score为10！ 对于那些想要查看它的人，xxHash的源代码可以在github.com上找到： github.com/Cyan4973/xxHash/releases/latest 。 基本思想是使64位散列值（或其中一部分）中的所有位对产生的48位散列值产生影响。 有没有办法做到这一点？ [编辑后期]： 所以我实现了自己的48位（准）-UUID生成器。 请在此处查看完整的工作解决方案（包括源代码）： https ： //stackoverflow.com/a/47895889/4731718 。

重复的图像检测算法？

我正在考虑为图像创建一个数据库系统，用紧凑的签名存储这些图像，然后与“查询图像”进行匹配，“查询图像”可以是存储图像的resize，裁剪，增亮，旋转或翻转版本。 请注意，我不是在谈论图像相似度算法，而是严格来说是重复检测。 这会使事情变得简单得多。 系统不关心两个图像是否有大象，只检测这两个图像是否实际上是同一图像。 直方图比较根本不适用于裁剪的查询图像。 我看到唯一可行的方法是形状/边缘检测。 首先，图像将以某种方式离散化，例如，每个像素被转换为8级灰度。 离散化的图像将包含相同颜色的大区域，这有助于指示形状。 然后可以用系数描述这些形状，并且可以记住它们的相对位置。 紧凑的签名将由此产生。 当必须进行比较时，将对存储的每个图像以及每个查询图像执行该处理。 这听起来像一个有效和可实现的算法？ 为了说明这个想法： 删除了死的ImageShack链接 我知道这是一个不成熟的研究领域，我已经阅读了关于这个主题的维基百科，我会请你提出你对这种算法的想法。

用于查找2个字符串之间任意长度的所有共享子串的算法，然后计算字符串2中的出现次数？

我遇到了一个不同寻常的挑战，到目前为止，我无法确定最有效的攻击方法。 给定以下2个字符串作为示例，查找任意长度的2个字符串之间的所有共享子字符串，并计算字符串2中所有这些共享子字符串的出现次数。您的算法还需要能够计算之间的共享子字符串包含最大100MB或更大的字符串的文件。 例： 字符串1：ABCDE512ABC361EG51D 字符串2：ADE5AHDW4131EG1DG5C 给定这2个字符串，该算法将找到以下共享子串：A，C，D，E，5,1,3，G，DE，E5，EG，G5,1D，DE5,1EG 然后从这些共享的子串中，我们可以发现字符串2中每个子串的出现次数。 答：字符串2中出现2次 C：字符串2中出现1次 D：字符串2中出现3次 等等.. 我用来解决这个问题的第一种方法是粗暴地强迫我使用2个嵌套for循环来计算公共共享子串 – 显然效率最低但是这是一种快速而肮脏的方式来了解预期的输出应该使用较小的测试输入和最慢的运行时间，大约2分钟来计算包含ascii字符串，大小为50kb的2个文件之间的所有常见共享子字符串。 将大小增加到1mb会导致这种情况急剧下降，因为计算此事件时必须进行大量的嵌套迭代。 下一个方法是使用树 – 看看我可以用多少内存来优化计算时间。 这种方法要快得多。 使用蛮力方法花费2分钟的两个50kb文件几乎是即时的。 对1mb文件运行速度非常快（秒）但是当我继续测试越来越大的文件大小时，由于树的大小，我很快就开始遇到内存问题。 注意：字符串文件只包含ASCII字符！ 编辑： 我正在进一步升级，请看： https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc

采访难题：使用有限的内存对一百万个输入进行排序

我尝试使用外部排序来回答这个问题，但是访问者回答说复杂性是高nn（log（n）），即n square * logn。 有没有更好的选择。 简化问题：假设我们有1000个元素要排序，只为100个元素分配空间。 什么是比外部排序花费更少时间的最佳算法。

这种RGB到XYZ色彩空间转换算法有什么问题？

我的目标是将RGB像素转换为CIELab色彩空间，以便在CIELab中进行一些特殊的计算。 为此，我必须首先将RGB转换为XYZ，这是非常困难的部分。 我试图在Objective-C中实现这个算法（虽然大多使用普通的C），但结果是错误的。 我的代码基于easyrgb.com提供的伪实现。 他们有一个在线颜色转换器，工作得很好。 他们说他们的伪代码与他们的转换器中使用的伪代码相同。 这是他们的伪代码： var_R = ( R / 255 ) //R from 0 to 255 var_G = ( G / 255 ) //G from 0 to 255 var_B = ( B / 255 ) //B from 0 to 255 if ( var_R > 0.04045 ) var_R = ( ( var_R + […]

C中的算法

在C中学习算法的最佳位置或链接是什么？ 通过调查问题，您如何知道何时何地使用算法的实现？