如果我有一台带有多个处理器的机器并试图解决一个巨大的问题，哪种算法最适合解决这个问题？
动态规划，贪心算法还是分而治之算法？
最佳答案
这是一个非常广泛的问题，很多事情都取决于您要解决的具体问题，但您要寻找的是算法是否可以并行运行其步骤。只有当一个步骤的结果不依赖于另一步骤的结果时，才能这样做。
- 我们不能在这里谈论贪心算法。他们仅被定义为采取本地最好的下一步。
- 分而治之将问题分成不同的部分，每个部分都可以单独解决，因此这通常是并行运行事物的好选择。
- 动态编程可以被视为一种分而治之的方法，但现在，您正在解决问题的一小部分，然后用它来解决更大的部分，依此类推。例如，背包问题经常被用作动态规划的用例。您可以从一个非常小的背包开始解决问题，然后从那里构建您的解决方案。这里的问题是每个解决方案都取决于较小问题的解决方案。除非各个步骤可以在线程之间划分，否则无法并行化。
所以一般来说，分而治之似乎是并行运行事物的最佳选择。
关于algorithm - 使用并行处理器运行时哪种算法最好？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41236049/