第1-1课：如何“玩”算法

心已赠人 2022-12-09 11:39 158阅读 0赞

> 既然是“玩”算法，首先要会玩，否则只会被算法“玩死”。很多朋友啃完了《算法》、《算法导论》或其他算法书籍，对各种排序、搜索、遍历等常用算法了如指掌，但是遇到实际的问题时还是束手无策，这与智力无关，这其实就是经验和方法集的问题。很多啃过算法书的朋友都知道堆排序和最大最小堆，但是却不能有效地应用到实际问题中。例如，某算法书介绍 Dijkstra 算法时，提到当问题规模比较大时，每次查找 dist 数组中的最小值可能成为效率的瓶颈，可以用一个最小堆来维护 dist 结果，使得每次取最小值的操作变成 O(1) 时间复杂度。看到这，许多读者不知所措，不知道如何将自己掌握的最小堆算法与 Dijkstra 算法结合在一起改进算法的效率。尽管部分人看不起穷举法，但是不可否认，有些人却连基本的穷举算法都设计不出来。
> 
> “玩”算法就是要能够做到以下三点：对遇到的特殊问题要能够自己设计出算法实现（可能是一个智力游戏题目，也可能是工作中遇到的实际问题）；对于原理公开的知名算法，要能将算法原理翻译成具体的算法代码（如二部图匹配的匈牙利算法、大整数乘法的 Karatsuba 算法）；对已有具体实现的算法，要能够设计出合适的数学模型，将算法应用到实际问题中（如遗传算法、SIFT 图像识别算法）。想要做到这些，除了熟练掌握各种常用的基础算法外，还需要了解算法设计的常用思想和模式，并且要掌握将题目转换成数据模型，并进一步用数据结构实现数据模型的一般方法，这一节课我们就来讲讲数据模型和建模。

### 数据模型 ###

如果想要计算机来解决问题，就必须用计算机能理解的方式描述问题。计算机只能用数据描述问题，这就需要一个合理的数据模型用来存储这些数据，这里提到的数据模型不同于大家普遍理解的数学模型，因为数学模型的意义更宽泛、也更抽象，语言、图表和公式都可以用来描述数学模型。数据模型的定义更具体一点，就是用在计算机程序中可以直接使用的，用编程语言直接描述的数学模型，可以将数据模型简单理解为与数学模型相一致的数据结构定义，是数学模型的一种表达形式。

建立问题的数据模型实际上是对问题的一种抽象地表达，通常也需要伴随着一些合理的假设，其目的就是对问题进行简化，抓住主要因素，舍弃次要因素，逐步用更精确的语言描述问题，最终过渡到用计算机语言的数据结构能够描述问题为止。一个完整的算法实现应该包含三个重要的组成部分，即数据模型、算法逻辑主体和输入输出。输入就是把自然语言描述的问题转化成计算机能存储或处理的数据，并存入数据模型中；输出就是将计算机处理后的结果（也在数据模型中定义）转化成人类能理解的方式输出。算法的逻辑主体就是具体承载数据处理的代码流程，负责对数据模型中的输入数据进行处理、转换，并得到结果。这三个组成的核心是数据模型，好的数据模型不仅能准确地描述问题，还能简化算法实现或提高算法的效率，不好的数据模型可能会导致算法的实现困难、效率低下，甚至无法实现算法。

根据问题的描述建立数据模型的能力是“玩”算法的关键。不能对问题进行归纳并抽象出数据模型的，就不能设计出解决问题的算法实现，换句话说，就是缺乏解决实际问题的能力。这种能力的缺乏体现在两个方面，一方面是不能针对特有的问题设计出解决问题的算法实现，而这种特有的问题有可能是其他人没有遇到过的，没有现成的方法可用；另一方面是不能用已有的通用算法解决具体的问题，像遗传算法这样的通用算法，通常需要结合实际问题的数据模型才能真正解决问题。如果不能解决工作和生活中实际面临的问题，学再多的算法又有何用？不过是把别人做过的事情再做一遍而已。

建模是个很抽象的话题，这世界上的问题纷繁复杂，不存在能解决一切问题的通用建模方法，一个人也不可能看了几篇文章就能全面掌握各种问题的建模方法。前面提到过，这种能力其实就是经验和方法集的问题，多练习、多思考，学会总结和归纳，是提高建模能力的关键。话题抽象并不表示这个问题是毫无章法可言的，实际上，在某些方面还是有一些规律可循。接下来的内容是我总结出来的一些惯用方法，给大家提供一个建模时的思考方向。

### 把问题抽象成数据模型 ###

#### 信息数字化 ####

信息数字化就是把自然语言描述的信息，转化成方便代码数据模型表达的数字化信息，这是各种问题建模的一个通用思考方向，比如当问题中出现用“甲、乙、丙、丁”或“A、B、C、D”来标识物品或人物的序列时，就可以考虑用数字 1、2、3、4 来表达它们；还有很多其他的非量化属性，也可以转化成数字信息，比如判断结果“大于、等于和小于”时，可以用正数、0 和负数来表示；布尔值的真和假，可以用 1 和 0 表示，一些表示“有”和“无”的状态，也可以用 1 和 0 来表示。

在“爱因斯坦的思考题”这个题目中（在第 3-4 课中会详细介绍），题目描述了四个人的各种属性，都可以用数字来代替，如四种牌子的香烟，就可以用数字 1~4 来描述，这样对于“第二个人喝啤酒”之类的信息，就可以用数据模型描述为：

people[2].drink = 1;

再来看一个完整的例子：警察抓了 A、B、C、D 四名罪犯，其中一名是小偷，审讯的时候：

A说：“我不是小偷。”    x !=0
    B说：“C 是小偷。”     x = 2
    C说：“小偷肯定是 D。”  x = 3 
    D说：“C 是在冤枉人。”  x != 3

现在已经知道四个人中三个人说的是真话，一个人说了假话，请判断一下到底谁是小偷？

对这个问题分析，首先对 A、B、C、D 四个人分别用 0~3 四个数字进行编号，接着将四个人的描述结果用数字量化，如果描述是真，则结果是 1，如果是假，则结果是 0。我们假设小偷的编号是 x，对于四个人的描述，数字化的结果是：

int dis_a = (x != 0) ? 1 : 0;
        int dis_b = (x == 2) ? 1 : 0;
        int dis_c = (x == 3) ? 1 : 0;
        int dis_d = 1 - dis_c;

依次假设 x 是 A、B、C、D（0~3 的编号数值），对每次假设对应的 dis\_a、dis\_b、dis\_c 和 dis\_d 的值求和，若结果是 3，则表示假设是对的，x 对应的值就是小偷的编号。如此将自然语言的信息数子化后，算法就可以非常简单地实现了：

void who_is_thief()
    {
        for (int x = 0; x < 4; x++)
        {
            int dis_a = (x != 0) ? 1 : 0;
            int dis_b = (x == 2) ? 1 : 0;
            int dis_c = (x == 3) ? 1 : 0;
            int dis_d = 1 - dis_c;
    
            if ((dis_a + dis_b + dis_c + dis_d) == 3)
            {
                char thief = 'A' + x;
                std::cout << "The thief is " << thief << std::endl;
                break;
            }
        }
    }

很多情况下，信息数字化是建立数据模型的基础。数字化后的数据和数据模型是相辅相成的两个东西，先要知道有什么数据，才能设计相应的数据模型存储和表达这些数据，而好的数据模型不仅有利于数据的存储和访问，也有利于算法的高效实现。

#### 类比和转化 ####

你可以设计新的模型，但是有时候也可以像使用模式一样使用那些经典的或常用的模型，或者根据不同对象的某些相似性，借用已知领域的模型。当我们解决未知的问题时，常常把已知的旧问题当作基础或经验来源。正如艾萨克 · 牛顿说的那样：“如果我看的比别人远，那是因为我站在巨人的肩膀上。”从根本上讲，把未知的问题转化成已知问题，然后再用已知的方法解决已知问题，是解决未知问题的基础手段。但是，如何将一个未知的问题转化为我们熟知的模型是一个复杂而艰难的过程，完成这个过程需要相当多的经验积累，同时也是算法设计中最有趣味的部分。

**下面来看一个算法几何的例子。**

判断 n 个矩形之间是否存在包含关系是经典的算法几何问题，按照一般的思路，应该是 n 个矩形两两进行包含判断，但是很显然，这个简单的方法需要 n(n-1) 次矩形包含判断，时间复杂度是 O(n2)，如果知道区间树的概念，就可以将这个问题转化为区间树的查询问题。首先根据矩形的几何位置，利用水平边和垂直边分别构造两棵区间树（根据矩形的几何特征，只需要处理一条水平边和一条垂直边即可），然后将 n 个矩形的水平边作为被查找元素，依次在水平边区间树中查找，如果找到其他矩形的水平边完整覆盖被查找矩形的水平边，则在垂直边区间树上进一步判断该矩形的垂直边被覆盖的情况；如果存在被查找矩形的水平边和垂直边都被同一个矩形的水平边和垂直边覆盖，则说明这两个矩形存在包含关系。采用区间树的算法复杂度是 O(nlg(n))，额外的开销是建立区间树的开销，但是只要 n 足够大，这个算法仍然比简单的比较法高效。

**再来看一个项目管理问题的例子。**

一个工程项目经过层层结构分解最终得到一系列具体的活动，这些活动之间往往存在复杂的依赖关系，如何安排这些活动的开始顺序，使得项目能够顺利完成是个艰巨的任务。但是如果能把这个问题转化成有向图，图的顶点就是活动，顶点之间的有向边代表活动之间的前后关系，则只需要使用简单的有向图拓扑排序算法就可以解决这个问题。一个工程分解出的这么多活动，每个活动的时间都不一样，如何确定工程的最短完工时间？工程的最短完工时间取决于这些活动中时间最长的那条关键活动路径，从成百上千个活动中找出关键路径看似是个无法入手的问题，但是如果将问题转化为有向图，顶点代表事件，边代表活动，边的权代表活动时间，则可以利用有向图的关键路径算法来解决问题。

#### 数学问题的建模 ####

大部分数学问题的建模，相对比较简单一些，因为大部分的信息其实都已经是数字化或量化的描述，并且很多问题都可以归纳为一组不等式作为约束条件，或者几个函数表达式作为目标函数。数学中的很多数据类型，比如列表、树和图等问题，都可以用与之对应的数据结构描述，大大减少了设计数据模型的难度。当然，数学问题也有数学问题的特点，比如无穷大和无穷小是无法用计算机表达的，极限和无穷数列也是无法用计算机存储和描述的，对此类问题，就需要对模型进行特殊处理，比如裁剪范围，或者是在不影响问题解决的前提下增加约束条件。

计算几何的问题范围都是整个坐标系，比如直线是向两端无限延伸的，但是对于计算机来说，即便有大数计算库的支持，它能表达的最大范围也是有限的。通常会根据实际应用场景裁剪规模，以便于计算机算法的建模和处理。比如某绘图仪的最大坐标范围是 \[-32768,32768\]，那就可以定义一个比 -32768 还小的数作为负无穷大，定义一个比 32768 还大的数作为正无穷大，这样直线就可以作为一个两端超过区间 \[-32768,32768\] 的大线段来建模，对于坐标范围是 \[-32768,32768\] 来说，模型符合直线的特征，对于计算机来说，这是一条数据模型能表达和存储的线段。

对于涉及数学公式的建模，相对比较简单，只要定义的数据结构能表达公式描述的各项属性即可。需要注意的是，很多公式是隐含着无穷数列的特征的，在建模时需要增加约束条件，使得问题能在某个范围内用算法解决。

**下面以求 n 次二项式的展开式系数问题为例来讲解一下对这个问题建模时需要的考量。**

n 次二项式的展开公式如下所示：

![gif.latex?(a&plus;b)^\{n\}=C\_\{n\}^\{0\}a^\{n\}&plus;C\_\{n\}^\{1\}a^\{n-1\}b&plus;C\_\{n\}^\{2\}a^\{n-2\}b^\{2\}&plus;……&plus;C\_\{n\}^\{n-1\}ab^\{n-1\}&plus;C\_\{n\}^\{n\}b^\{n\}][gif.latex_a_plus_b_n_C_n_0_a_n_plus_C_n_1_a_n-1_b_plus_C_n_2_a_n-2_b_2_plus_plus_C_n_n-1_ab_n-1_plus_C_n_n_b_n]

从这个展开式可以看出展开后的多项式项数与 n 相关（n+1 项），受制于存储空间的限制，在考虑数据模型的时候需要限制 n 的最大值。再观察每个展开项可知，需要存储的数据有多项式系数、a 的幂和 b 的幂三个属性，因此，定义的数据结构要有相对应的条目这些属性，可以这么定义每一项的数据结构：

typedef struct
    {
        int c;
        int am;
        int bm;
    }ITEM;

根据展开式的特点，需要一个列表存储各项的数据，显然这个列表不存在频繁删除和插入操作，可以选择用数组作为数据模型。这个例子模型限制 n 的最大值是 32，当然，这个值可以根据问题域和存储空间的限制来综合考虑，最终定义的数据模型就是：

ITEM items[N];

![enter image description here][]

图1 杨辉三角递推计算示意图

item 中系数 c 的计算采用杨辉三角的递推公式计算，避免使用 ![gif.latex?\\inline&space;C\_\{n\}^\{k\}][gif.latex_inline_space_C_n_k] 公式计算，这样做的话计算量太大了。杨辉三角的递推关系如图1所示，第 n 阶系数的首项和末项都是 1，其他 n-2 项系数可以从第 n-1 阶的系数递推 i 计算出来，其递推计算关系是：

![gif.latex?C\_\{n\}&space;=&space;C'\_\{n\}&space;&plus;&space;C'\_\{n-1\}&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;\\;&space;&&space;n=2,3,…,n-1][gif.latex_C_n_space_space_C_n_space_plus_space_C_n-1_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_n_2_3_n-1]

am 和 bm 则比较简单，一个是从 n 到 0 递减，一个是从 0 到 n 递增。

根据我们定义的数据模型 items，求二项式展开式各项系数和幂的算法实现也就水到渠成了：

if (n == 0)
        {
            items[0] = {1, 0, 0};
            return;
        }
        for (unsigned int i = 1; i <= n; i++) //从第1阶开始递推到第n阶
        {
            unsigned int nc = i + 1; //每一阶的项数
            items[nc - 1] = { 1, 0, i }; //末项
            //倒着递推第2项到第n-1项的值，实际下标范围是[1, nc-2],不需要额外的存储空间转存items数组
            for (unsigned int j = nc - 2; j > 0; j--)
            {
                unsigned int c = items[j].c + items[j - 1].c;
                items[j] = {c, i - j, j};
            }
            items[0] = { 1, i, 0 }; //首项
        }

计算机也无法直接表示大小和不等于这样的关系，对于不等式的建模，通常是转换成减法，然后对结果进行正、负的判断。对于方程也是一样的，通常将方程转换成 f(x)=0 的形式建模，模型会比较简单。

#### 图论算法的建模 ####

图论相关的算法也是非常典型的一类问题。描述图的数据结构最常用的是邻接矩阵和邻接链表两种形式，这两种数据结构的介绍资料有很多，这里只是讲一下在实际使用它们设计数据模型时需要考虑的其他方面的内容。先来说说临界矩阵，临界矩阵一般由一个一维的顶点信息表和一个二维的邻接关系表组成，根据实际问题的情况，还可以增加其他属性，如顶点个数和边的个数等。

**请看一个典型的临界矩阵数据模型定义：**

typedef struct
    { 
        int vertex[MAX_VERTEX];  //顶点信息表
        int edge[MAX_VERTEX][MAX_VERTEX]; //边信息表
        int numV; //顶点数
        int numE; //边数
    }GRAPH;

如果你使用的编程语言中数组的属性中包含元素个数，那么表示定点数的 numV 属性就没有必要，同样，表示边数的 numE 属性也不是必须的。如果问题中关于顶点信息除了编号，还有其他信息，那么顶点信息表的元素类型就不能简单用 int 类型了，而是要根据题目给出的信息做相适应的修改。比如与地图有关的问题，通常作为顶点的每个城市有很多属性，如城市名称、公路出口个数和入口个数等，就需要定义相关的顶点数据结构，比如包含了城市名称的顶点信息：

typedef struct
    {
        std::string name;
        int node;
    }VERTEX
    
    VERTEX vertex[MAX_VERTEX];  //顶点信息表

表示边信息的矩阵，每个元素是边的权重，对于不相邻的顶点，权重一般是一个特殊值。如果边的信息除了权重，若还有其他信息，则需要定义与之相适应的数据结构来描述边的信息。比如有个求最优解的规划类题目，城市之间除了距离，还有交通困难指数，比如是水路、山路还是平地等信息，此时边的定义就可以改成如下代码：

typedef struct
    {
        int weight;
        int traffic_type;
    }EDGE
    
    EDGE edge[MAX_VERTEX][MAX_VERTEX]; //边信息表

使用邻接矩阵定义图，优点是顶点之间的边的信息则很容易获取，如果你要处理的问题需要频繁的确定顶点之间的连接信息，那么使用邻接矩阵是一个比较好的选择。邻接矩阵的缺点是它是一个稀疏矩阵，当顶点比较多的情况下，对存储空间的浪费比较严重。邻接表是一种顺序分配和链式分配相结合的数据结构，顶点信息顺序存放，每个顶点相邻的顶点信息，则通过一个链表链接到该顶点的邻接点域。一个典型的邻接表数据模型如下：

typedef struct EDGE
    {
        int node;  //边的对应顶点
        int weight;
        EDGE *nextEdge;  //下一条边的信息
    }EDGE;
    
    typedef struct
    {
        int node;
        EDGE *firstEdge; //第一个边的信息
    }VERTEX;
    
    typedef struct 
    {
        VERTEX vertex[MAX_VERTEX]; //顶点列表
        int numV; //顶点数
        int numE; //边数
    }GRAPH;

如果题目需要顶点和边来描述更多的信息的话，则在此基础上扩展 EDGE 和 VERTEX 的定义，增加相应的属性即可。

### 总结 ###

“玩”算法的目的不是学会一种算法或很多种算法，而是学会用算法来解决问题，掌握解决问题的能力是关键。这一课，我们介绍了这种能力的核心内容——如何建立与算法相适应的数据模型。建模能力的提高是一个长期的积累过程，这里提到的只是最常见的思路和方法。除此之外，提高建模能力还需要熟悉各种常见的数据结构的特点和使用方法，需要多做、多练、多思考，善于把别人的经验变成自己的经验。

[gif.latex_a_plus_b_n_C_n_0_a_n_plus_C_n_1_a_n-1_b_plus_C_n_2_a_n-2_b_2_plus_plus_C_n_n-1_ab_n-1_plus_C_n_n_b_n]: /images/20221123/e376757d78d148df871596a5c90efec4.png
[enter image description here]: /images/20221123/fc9f01afc2db4b40a2e5be15ea17a4ef.png
[gif.latex_inline_space_C_n_k]: /images/20221123/59c5edd41b2b4c95ba80ad4ddfb98e78.png
[gif.latex_C_n_space_space_C_n_space_plus_space_C_n-1_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_space_n_2_3_n-1]: /images/20221123/b03ffafabdac47f79f8549f3339d3c60.png