0

这是那些困难的算法之一，只是因为有很多选择。想象一个数字“N”和一组小于 10 的素数，即 {2, 3, 5, 7}。目标是不断除以 N 直到我们达到 1。如果在任何步骤 N 都不能被任何给定的素数整除，那么您可以进行以下操作：

i) N= N-1 或 ii) N=N+1

这将确保 N 是偶数，我们可以继续。

应在使用最少操作数的同时实现该目标。

请注意，这听起来可能微不足道，即您可以在算法中实施一个步骤，即“如果 N 可被任何素数整除，则除以它”。但这并不总是产生最佳解决方案

例如，如果 N=134：现在 134 可以被 2 整除。如果你除以 2，你会得到 67。67 不能被任何素数整除，所以你做一个运算，N 将是 66/68，这两个都需要另一个运算。所以总共2次操作。

或者，如果 N=134 并且您执行操作 N=N+1 即 N=135，在这种情况下，达到 1 所需的总操作数为 1。所以这是最佳解决方案

4

1 回答 1

2

除非这个问题有一些数学解决方案（如果您正在寻找数学解决方案，math.SE更适合这个问题） - 您可以将问题简化为最短路径问题。

将问题表示为G=(V,E)（V = N所有自然数）和E = {(u,v) | you can get from u to v in a single step }1的图。

现在，您需要运行从源（输入数字）到目标（数字 1）的经典搜索算法。获得最佳解决方案的一些选择是：

  1. BFS - 由于简化图没有加权，BFS 保证既是完整的（如果存在则找到解决方案）和最优的（找到最短的解决方案）。
  2. 启发式A* - 也是完整且最优的2，如果你有一个好的启发式函数 - 应该比不知情的 BFS 更快。

优化说明：
图形可以“即时”构建，无需将其创建为预处理。为此，您将需要一个next:V->2^V（从一个节点到一组节点）函数，这样next(v) = {u | (v,u) is in E}

PS复杂性评论：BFS 解决方案是伪多项式（在输入数最坏的情况下是线性的），因为您将开发的“最高”顶点是n+1，所以解决方案基本上是O(n)最坏的情况 - 尽管我相信更深入的分析可以将其限制为更好的限制。

(1) 如果您只对 +1/-1 计为 ops 感兴趣，您可以在完成除法后根据目标创建边。
(2) 如果使用了允许的启发式函数。

于 2012-09-21T14:02:41.050 回答