1.3 算法设计的过程

进行算法设计之前，必须先弄清楚问题是什么，它有哪些可以用来解题的条件。这并不是对题干的简单阅读，而是设计者要从这一过程中找到足够解题的已知条件和解题思路。也许题干会直接表明已知条件且足够求解问题，或是表述模糊，需要设计者对问题进行分析，找到隐藏的已知条件。所以，问题分析是针对某个具体问题的深入推理过程。

在日常生活，随处可见这样的示例。例如，在电视综艺节目中有一类很有意思的传话游戏，参与者被相互隔离，主持人向第一个被隔离者展示一个动作、一段视频或文字。然后，第一个被隔离者按照自己的理解，通过肢体语言（不能说话）来向第二个人描述所看到的内容。依此类推，第二个人向第三个人传送信息……，直到最后一个人。这时候，主持人会问最后一个人，他对前一个人转述内容的理解。于是，最富戏剧性的一幕出现了，多数结果与原问题大相径庭。在这个游戏当中存在几个问题：

① 每个人对问题的理解和表达可能都是错的；

② 问题的相关信息在理解和传递的过程中存在遗漏；

③ 没有统一规范的表达方式，所展示的内容多数存在二义性；

④ 每个人对于问题的理解不同，表达方式也就不同。

问题①和②是需要我们在问题分析阶段必须解决的，否则没法求解或得不到正确的解。问题分析是对问题进行严格描述（形式化）的前提，它是下一步设计甚至整个求解过程的基石。问题③和④是对问题规范化描述的要求，如果能用数学方式进行形式化描述，将会对排除二义性有很大的帮助。有时候，遇到的问题并不是很简单，而且可能存在多种解法，算法策略的选择也很重要，它会对形式化描述产生影响，相关内容将在后面介绍。数学上的形式化描述，通常被称为数学建模，转换为可进行程序设计的模型称为计算建模。有时候两者能统一，有时候不能，如通过数学建模得到9x2-sin x-1=0，这是一个超越方程，用计算机不能直接进行计算，因此，这就需要进行模型变换。排除二义性的方法除了使用计算/数学建模外，也可以通过计算机程序设计语言来描述，有时候为了强调算法设计的通用性，还会使用流程图、NS流程图、伪代码等方式。在算法描述之后，不要立刻进行编程与实现。因为，算法的正确性不仅仅是能够规范输入，得到理想的结果，还需要考虑其他限制条件，如果超过了规定的时限、存储限制及精度都不能算是正确的。所以，算法分析是必要的。算法分析的另一个重要作用是展示了设计者对于这一问题的贡献（算法效率、精度等方面的提高），所以，可能会有对同一问题不同解法的比较。算法分析在软件工程上也具有非常重要的作用，它可以为降低成本提供重要参考，将所有影响求解的问题尽量在设计阶段解决。接下来是算法的实现与测试，最后，别忘了整理结果与编制设计文档，这是设计人员的职业素养。

总结上述分析，不难得出算法设计的过程大致可以分为以下几个阶段：①问题分析→②算法策略/计算建模→③算法描述→④算法分析[→算法设计与选择]→⑤算法实现→⑥测试→⑦结果整理与文档编制。例1-1就遵照了这个设计过程，下面再举一个例子来进一步说明上述过程。

【例1-2】交通指挥灯问题。一个有五条通路的交叉路口，当允许某些通路上的车辆在交叉路口通行时，必须对其他通路上的车辆加以限制，不允许同时在交叉路口通行，以免发生碰撞。如图1-8（a）所示，按我国的交通规则为右向行驶，其中，E→C为单向行驶。请问至少用几盏不同颜色的灯可以实现这一五岔路口的交通指挥。

问题分析

题目和图1-8（a）中给出的信息，似乎符合图的特点，那么，我们就用图的方式尝试解决该问题。图运算属于集合运算，它的定义包括两部分：顶点集和边集。显然，这两种信息不能从这张图中直接找到。因此，它不能直接用于计算，我们需要对其进行提炼和抽象。

（1）通路。把可以行驶的通路全部描述出来，按图1-8（a）中标注的字母、行驶方向及交通规则，通路可描述为AD、AC、AB、BA、BC、BD、DA、DB、DC、EA、EB、EC、ED共13条通路。

（2）规则。尽管有13条通路，但是按照交通规则，在同一时间段内不是所有道路都可以通行，否则，就有可能会撞车。例如，AD和EA、EB和EC不能同时行驶。不能同时通行的道路不能用同一种灯指挥，如AD是绿灯通行，则EC必然是红灯停止。若把每一条通路看成图中一个节点，把不能同时通行的节点看作相邻节点，用边把相邻节点连接起来，这样，就把交通指挥灯问题转化为了图，可以用图的运算方式进行处理，如图1-8（b）所示。

（3）等价的问题。交通指挥灯主要看的是灯的颜色。若把灯单纯以颜色区分，那么，交通指挥灯问题就是经典的着色问题，有广泛的用途，类似的问题还有行政地图着色等。

计算模型

依据问题分析，对抽象为图的交通指挥灯问题进行模型设计需要经过以下几个步骤。

（1）数据结构

图是一个二元组G=(V, E)，设置结构体Node表示图中的节点V。采用邻接矩阵表示边的关系，两个节点相邻为1，不相邻为0。为了便于运算，将13条通路编码{AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC,ED}={0,1,2,3,4,5,6,7,8,9,10,11,12}，则G表示如下。

V：struct Node{
         char name[10]; //表示道路名称，如AB
         int color;     //表示灯的颜色编号
   }v[13];
E：e[13][13]

矩阵e的值如下所示。

（2）图的遍历

依据题目及问题分析可知，确定至少用几盏不同颜色的灯进行交通指挥，实际上就是对图中节点进行分组，把不相邻的节点分在同一组中，分出的组数就代表灯颜色数目。分组过程需要遍历图中所有节点，其计算过程为：找到一个未着色的节点（v[i].color=0），给它着色，放入集合S（着相同颜色顶点集合，暂设为S）中，然后，通过矩阵e找到所有与S中的顶点不相邻的节点，着同一种颜色。循环这一过程，直到遍历完图中所有节点为止。

算法设计与描述

算法分析

本例中尽管只有13个顶点，但是为了判断任意两个顶点之间是否相邻，还要考察图的边集e。按照算法GCP的设计，每选择一个顶点，都要检测其他顶点是否与之相邻。一般来说，若顶点数为n，则算法主体总计运算次数为，其中，m_i是第i次已检测节点的个数，随着算法的推进，m的个数会越来越大，相应的运算次数会逐步减少。

其实，算法的终结不在于将边集e是否全部考察完毕，而在于是否将13个顶点全部着色。也就是说，我们每选择出一种颜色，需要考察的是没有着色且不相邻的顶点，每选出一个符合要求的顶点，着色后要将其剔除出下次考察的集合。由此，可以得到改进的算法GCP_P（注意斜体加粗部分）。因此，决定算法主体部分运算次数的关键因素有两个：颜色数量和顶点数量。通过这两个因素可以得到总计运算次数f(n)≈k×n-1，其中k为颜色数量，它是算法GCP_P中的最大编号值。实践证明，对类似本题的着色问题，最多用4种颜色就可完成任务。因此，算法GCP_P比GCP效率要高。

算法GCP和GCP_P的特点是每一次检测，都要试图找到最多的符合要求的顶点，这种优化方法被称为贪心算法（Greedy Algorithm，GA）策略。本例使用了图作为数据结构，这里将广度优先（Breadth-First-Search，BFS）算法做了一些改进，成为GA策略的具体实现，使它适合于求解交通指挥灯问题。两者的关系是BFS属于GA。本例除可以使用GA外，还可以使用穷举法。

算法实现

在算法分析中提到算法GCP_P是通过颜色数量k来提高运算效率的，颜色数量是问题的解，可是只有算法运算完毕才能知道，是无法预知的。所以，算法GCP_P是一种启发式算法，在运算过程中一边计算颜色的数量，一边判断算法是否结束。这两种功能由算法GCP_P中斜体加粗部分实现，考察集合要除去已着色的顶点，对于外层循环来说是减少一种颜色，而内层是减少同一种颜色的着色顶点。在实现时，考虑到编程的复杂度，做一个近似算法，设置一个计数器，当着色满13个顶点时结束循环。具体实现如下。