algorithm - 困难的算法 : Optimal Solution to 1

Question

这是那些困难的算法之一，因为有太多的选择。想象一个数字“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。因此这是最优解

Answer 1

除非这个问题有一些数学解决方案(如果您正在寻找数学解决方案，math.SE 更适合这个问题)- 您可以将问题简化为 shortest path problem .

将问题表示为图 G=(V,E)，其中 V = N(所有自然数)和 E = {(u,v ) |你可以一步从 u 到 v ¹。

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

1. BFS - 由于缩减图没有加权，BFS 保证是完整的(找到一个解决方案，如果存在的话)和最优的(找到最短的解决方案)。
2. 启发式 A* - 这也是完整且最优的²，如果你有一个很好的启发式函数 - 应该比不知情的 BFS 更快。

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

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

---

(1) 如果您只对+1/-1 算作ops 感兴趣，您可以在完成除法后根据目标创建边。
(2) 如果一个admissible heuristic function被使用。