计算机就不能胜任,故以其在计算上难于对付而闻名,被称为NP- Complete问题,例如旅行售货员 问题、时间表问题等等。数学家强烈的认为(但并未证明):人们不可能找出一个有效算法这一事实 是NP- Complete问题的固有性质,他们相信,不会有有效算法存在(如其一具有有效算法,余者皆 然),因此,对这类问题,寻找近似解的有效算法便自然成为人们追求的方向。 然而对算法的认识并未到此完结,人们很快发现上述复杂性概念只涉及到算法在最坏情况下的 性态,而这种最坏情况在实际中发生的概率究竟有多大,并未予以考虑,以致出现了多项式算法反 倒不如非多项式算法在实算中有效的奇怪现象。例如,单纯形算法已被实践证明是普遍实用和非常 有效的,但人们也举例证明了它不是多项式算法,哈奇杨算法已被证明是多项式算法,但在许多实 践中,其计算速度反比单纯形算法慢得多。这说明用算法在最坏情况下的性态来区别好坏不是最科 学的,而算法的平均性态才是衡量算法好坏的最有说服力、最重要的标志。因此那种仅凭一、两个 并不具有代表性的例子来肯定或否定一种算法的思想和行为是不可取的。 对于解决同一类问题的各种算法,优劣立判的并不常见,往往是尺短寸长,各有特点。方法一 可能在解决A子类问题上更有效,方法二可能在解决B子类问题上更优越,应当实事求是地进行具 体分析,不宜简单的肯定一种而否定另一种。那种认为某类问题已有有效算法,从而对新提出的一 些算法一概采取轻视过于挑剔甚至排斥态度,这于算法的发展是有害的。对算法亦应采取“百花齐 放,推陈出新”的方针,特别是对比较成熟领域的基本算法,哪怕是稍有些微改进,也可能产生较 大的经济效益,因此更加不能忽视 算法的发展是没有穷尽的,人们对算法的认识也在逐步深入,我们期待着有更多的好算法出现, 为社会服务,为人类造福4 计算机就不能胜任，故以其在计算上难于对付而闻名，被称为 NP-Complete 问题，例如旅行售货员 问题、时间表问题等等。数学家强烈的认为（但并未证明）：人们不可能找出一个有效算法这一事实 是 NP-Complete 问题的固有性质，他们相信，不会有有效算法存在（如其一具有有效算法，余者皆 然），因此，对这类问题，寻找近似解的有效算法便自然成为人们追求的方向。 然而对算法的认识并未到此完结，人们很快发现上述复杂性概念只涉及到算法在最坏情况下的 性态，而这种最坏情况在实际中发生的概率究竟有多大，并未予以考虑，以致出现了多项式算法反 倒不如非多项式算法在实算中有效的奇怪现象。例如，单纯形算法已被实践证明是普遍实用和非常 有效的，但人们也举例证明了它不是多项式算法，哈奇杨算法已被证明是多项式算法，但在许多实 践中，其计算速度反比单纯形算法慢得多。这说明用算法在最坏情况下的性态来区别好坏不是最科 学的，而算法的平均性态才是衡量算法好坏的最有说服力、最重要的标志。因此那种仅凭一、两个 并不具有代表性的例子来肯定或否定一种算法的思想和行为是不可取的。 对于解决同一类问题的各种算法，优劣立判的并不常见，往往是尺短寸长，各有特点。方法一 可能在解决 A 子类问题上更有效，方法二可能在解决 B 子类问题上更优越，应当实事求是地进行具 体分析，不宜简单的肯定一种而否定另一种。那种认为某类问题已有有效算法，从而对新提出的一 些算法一概采取轻视过于挑剔甚至排斥态度，这于算法的发展是有害的。对算法亦应采取“百花齐 放，推陈出新”的方针，特别是对比较成熟领域的基本算法，哪怕是稍有些微改进，也可能产生较 大的经济效益，因此更加不能忽视。 算法的发展是没有穷尽的，人们对算法的认识也在逐步深入，我们期待着有更多的好算法出现， 为社会服务，为人类造福