算法的乐趣

发布 : 2019-03-24 浏览 :

“玩”算法就是要能够做到以下三点:

  • 对遇到的特殊问题要能够自己设计出算法实现(可能是一个智力游戏题目,也可能是工作中遇到的实际问题);
  • 对于原理公开的知名算法,要能将算法原理翻译成具体的算法代码(如二部图匹配的匈牙利算法、大整数乘法的 Karatsuba 算法);
  • 对已有具体实现的算法,要能够设计出合适的数学模型,将算法应用到实际问题中(如遗传算法、SIFT 图像识别算法)

想要做到这些,除了熟练掌握各种常用的基础算法外,还需要了解算法设计的常用思想和模式,并且要掌握将题目转换成数据模型,并进一步用数据结构实现数据模型的一般方法

数据模型和建模

建立问题的数据模型实际上是对问题的一种抽象表达,通常也需要伴随着一些合理的假设,其目的就是对问题进行简化,抓住主要因素,舍弃次要因素,逐步用更精确的语言描述问题,最终过渡到用计算机语言的数据结构能够描述问题为止。

数据模型

一个完整的算法实现应该包含三个重要的组成部分,即数据模型、算法逻辑主体和输入输出。这三个组成的核心是数据模型,好的数据模型不仅能准确地描述问题,还能简化算法实现或提高算法的效率,不好的数据模型可能会导致算法的实现困难、效率低下,甚至无法实现算法。

把问题抽象成数据模型

信息数字化

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

类比和转化

你可以设计新的模型,但是有时候也可以像使用模式一样使用那些经典的或常用的模型,或者根据不同对象的某些相似性,借用已知领域的模型。但是,如何将一个未知的问题转化为我们熟知的模型是一个复杂而艰难的过程,完成这个过程需要相当多的经验积累,同时也是算法设计中最有趣味的部分。

数学问题的建模

大部分数学问题的建模,相对比较简单一些,因为大部分的信息其实都已经是数字化或量化的描述,当然,数学问题也有数学问题的特点,比如无穷大和无穷小是无法用计算机表达的,极限和无穷数列也是无法用计算机存储和描述的,对此类问题,就需要对模型进行特殊处理,比如裁剪范围,或者是在不影响问题解决的前提下增加约束条件。

图论算法的建模

图论相关的算法也是非常典型的一类问题,描述图的数据结构最常用的是邻接矩阵和邻接链表两种形式。使用邻接矩阵定义图,优点是顶点之间的边的信息很容易获取,如果你要处理的问题需要频繁地确定顶点之间的连接信息,那么使用邻接矩阵是一个比较好的选择。邻接矩阵的缺点是它是一个稀疏矩阵,当顶点比较多的情况下,对存储空间的浪费比较严重。

一个典型的邻接矩阵数据模型定义:

1
2
3
4
5
6
7
typedef struct
{
int vertex[MAX_VERTEX]; //顶点信息表
int edge[MAX_VERTEX][MAX_VERTEX]; //边信息表
int numV; //顶点数
int numE; //边数
}GRAPH;

邻接表是一种顺序分配和链式分配相结合的数据结构,顶点信息顺序存放,每个顶点相邻的顶点信息,则通过一个链表链接到该顶点的邻接点域。

一个典型的邻接表数据模型如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;

本文作者 : HeoLis
原文链接 : http://ishero.net/算法的乐趣.html
版权声明 : 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!

学习、记录、分享、获得

微信扫一扫, 向我投食

微信扫一扫, 向我投食