新算法程序的开发初探

2022-09-11

算法程序是用可执行程序设计语言或抽象程序设计语言描述的算法。开发正确、高效率的算法是计算机科学的核心。这种开发工作包括新算法的设计与描述:对已有算法的解释和证明。目前, 用于设计和证明的主要方法是非形式化的。为了提高算法程序的可靠性和生产效率, 人们正在追求算法程序开发的形式化和自动化。由于涉及到创造性工作, 开发算法程序仍然是计算机领域中最具挑战性的问题之一。

1 常见算法设计方法

为了获得一个有效的算法, 必须了解一些解题的基本思想和方法。有许多问题, 只要对数据对象进行仔细分析, 处理的方法就有了。下面我们对一些常见的算法设计方法作一介绍。

1.1 枚举法

枚举法亦称穷举法, 它的基本思想是:首先依据题目的部分条件确定答案的大致范围, 然后在此范围内对所有可能的情况逐一验证, 直到全部情况验证完。若某个情况使验证符合题目的条件, 则为本题的一个答案;若全部情况验证完后均不符合题目的条件, 则问题无解。枚举的优点是设计算法容易, 但得到的算法往往效率很低。

1.2 分治法

这种设计求解的思想就是将要求解的整个问题分成若干个小问题后, 分而治之。通常, 由分治法所得到的子问题与原问题具有相同的结构。如果得到的子问题相对来说还太大, 则可反复使用分治策略, 将这些子问题分成更小的同类型子问题, 直至产生出不用进一步细分就可求解的子问题。

1.3 贪心法

在现实世界中, 有这样一类问题, 它有n个输入, 而它的解由这n个输入的某个子集组成, 只是这个子集必须满足某些事先给定的条件。我们把这些必须满足的条件称为约束条件, 而把满足约束条件的子集称为该问题的可行解。显然, 满足约束条件的子集可能不止一个, 因此, 可行解一般来说不是唯一的。为了衡量可行解的优劣, 事先也给出了一定的标准, 这些标准一般以函数形式给出, 这些函数称为目标函数。那些使目标函数取极值 (极大或极小) 的可行解, 称为最优解。某些求最优解的问题可用贪心法求解。

1.4 动态规划法

在实际生活中, 有这么一类问题, 它们的活动过程可以分为若干个阶段, 而且在任一阶段i, 过程在阶段i以后的行为, 仅以来与i阶段的过程状态, 而与i之前过程如何达到这种状态的方法无关, 这样的过程就构成一个多阶段决策过程。在50年代, 贝尔曼等人根据这类问题的多阶段决策的特性, 提出了解决这类问题的“最优性原理”, 从而创建了最优化问题的一种新的算法设计方法——动态规划法。

1.5 回溯法

在那些设计到寻找一组解或者满足某些约束条件的最优解的问题中, 往往可以用回溯法来求解。回溯法的基本做法是搜索, 或者是一种组织得井井有条的, 能避免不必要搜索的穷举式搜索方法。因此这种方法设计的算法的效率较低。

2 新算法设计方法

新的算法设计方法是一种基于分划和递推的算法程序设计方法, 它涉及下列主要设计思想和关键技术。

2.1 算法程序设计中的创造性和非创造性成份

正确区分算法程序设计中的创造性和非创造性成份, 并通过揭示算法程序设计的固有规律和科学原理, 将其中尽可能多的创造性劳动转变为非创造性劳动, 是程序设计方法研究的重要课题。

分析数学发展史, 可以找到许多将创造性工作变成机械的非创造性工作的实例, 实际上一部分数学发展史就是不断创造性地给出解决实际问题的方法, 又进而不断地将这些创造性劳动变为非创造性劳动的历史。把科学研究中的创造性劳动变成非创造性劳动的过程就是不断寻找普遍规律, 建立科学基础和新兴学科的过程。从初等数学发展成为解析几何就是一个典型实例。我们都有这样的亲身体验, 解初等几何问题最具有挑战性, 最需要技巧和创造性的劳动, 解析几何的诞生, 将几何证明问题变成了代数计算问题, 将本来需各种特殊技巧才能解决的问题, 变成使用系统单一的方法就能解决。由初等数学上升为高等数学也是一个很好的例子。计算机科学本身也有十分成功的实例, 比如, 为了用计算机解决各种各样的实际问题, 人们提出很多翻译程序, 由于形式语言和自动机的发明和运用, 找到了形式描述和构造各类语言翻译程序的统一方法, 最终可以用计算机自动地生成各类语言的翻译程序。“软件危机”的出现, 迫使人们去研究程序设计的普遍规律, 形成了程序设计方法学, 进而提出了程序设计科学的概念, 但现有程序设计方法学中提出的方法还只能用形式化的方法解一些玩具式的小程序, 程序设计的普遍规律尚未找到, 可续基础尚未建立, 极需在这方面进行深入研究, 建立软件开发和算法程序设计的科学基础。

2.2 一种统一的算法设计方法和新的算法表示方法

算法程序开发方法的普遍适用性是我们追求的目标。算法的产生已有数千年历史, 而算法设计方法的提出则是最近几十年的事。事实上人们最初设计算法时并没有具体方法的指导。随着计算机的广泛运用, 人们设计的方法越来越多。Hopcroft等人对当时存在的大量算法进行了分类, 分治、动态规划、贪心等算法设计策略, 并写出了世界上第一本算法设计与分析的著作。此后, 人们又提出了各种各样算法设计的策略, 使算法程序设计从无方法变成有方法。然而, 由于难以精确刻画各种开发策略的适用范围, 在设计新算法时, 就很难做出用何种方法的选择。这给算法设计带来了难以克服的困难, 促使人们重新考察算法程序设计的本质特征。我们确信任何一种具体事物都是个别和一般、个性和共性的统一。个性中包含共性, 特殊性中包含普遍性, 个性一定与共性相联结而存在。在这些形式各异的设计策略之间一定存在一种统一的东西。

2.3 充分运用功能抽象和数据抽象

事实充分证明, 抽象是对付复杂性的最有效的手段。为了简化算法设计过程, 得到简单的算法表达形式, 我们必须充分利用功能抽象和数据抽象的语言机制。即利用自顶向下逐步求精的程序开发方法, 先基于抽象的功能和数据, 设计抽象的算法;再逐步将抽象功能细化, 直至可用可执行语言的语句描述;再将抽象算法中的抽象数据类型用某一可执行语言中具体的数据类型实现。我们定义的算法设计语言Radl有效地实现了数据抽象和功能抽象, 提供了描述递推关系的语言机制, 成为一种新型实用的算法描述语言。

摘要：算法程序是用可执行程序设计语言或抽象程序设计语言描述的算法, 开发正确、高效率的算法是计算机科学的核心, 为了提高算法程序的可靠性和生产效率, 人们正在追求算法程序开发的形式化和自动化。

关键词：算法程序,程序,设计,创造性,新算法程序