algorithm - 组合问题和数值问题有什么区别

Question

请您至少举两个例子。谢谢。

Answer 1

数值问题是计算某个数值量的问题。输入、输出和状态往往在连续集上变化，例如实数。一个例子是：计算这个炮弹的飞行高度，给定它的角度和初始速度。数值问题通常可以通过近似来解决。因为变量是连续的，所以存在“平滑性”假设，即如果 f(xa) 太低，而 f(x+a) 太高，则 f(x) 可能更接近正确。（我可能在这里遗漏了正确的术语。）

组合问题是那些输入、输出和状态倾向于在离散集合上变化的问题。一个例子是：计算这张图中从 a 到 b 有多少条不同的路径。

请注意，很容易将每个方面的各个方面组合在一个问题中。例如，从 a 到 b 的路径的平均长度是多少？或者怎么样：“黎曼 zeta 函数的任何非平凡零的实部是 0.5” http://en.wikipedia.org/wiki/Riemann_hypothesis。

Answer 2

组合问题是有效的计数问题；这些出现在离散数学的研究中。有限集有多少个排列？给定n麦片盒，每个盒子里都有k不同的奖品，有多少种方法可以收集所有k奖品？

数值问题是有效的计算问题；这些通常出现在工程和科学中，试图逼近方程的解（例如，求根或微分方程）或试图逼近数值（例如，定积分或特征值）。