大家好,我们开始数据结构与算法的学习
这一讲我们首先来介绍一下数据结构与算法中特别重要的一个概念就是问题求解
整个数据结构与算法就是围绕着问题求解而进行的
首先我们编写计算机程序它的目标是什么呢
这个目标主要是要解决在我们的实际的生活中或者是说科研中的一些问题
这个问题是怎么表达的呢
一般来说,我们会给你一定的数据输入,然后经过你的程序处理以后得到相应的结果
这个问题的描述要怎么进行呢
我们需要通过一个数据模型来描述这个问题的数据之间的一些联系
在得到这样的一个数据模型其实也就是数学模型以后我们能够采用计算机里面相应的算法对这些数据进行合理的操作最后能够得到相应的一个解
这个过程就是我们从问题到数据到算法的一个过程
而具体的编程实现其实是通过数据结构和算法两者之间的相互作用
也就是说其实很多时候，数据的定义里面是可以包含算法的
例如在面向对象的描述里，我们对数据操作的一些具体的方法可以在对象里面用成员函数来表达
而我们的数据结构也离不开算法
数据结构有逻辑、存储和运算这三个方面
这个运算呢，其实从广义的角度来说就是我们的算法
我们来看一个例子从这个例子来理解一下整个问题求解的过程
农夫过河问题呢，它的描述是这样的：
就是在一条河的两岸最开始的时候一个岸是空的，另外一个岸有三个物品就是狼 羊和菜
农夫他划着一条小船，这个船只能坐一个乘客也就是一个物品，当然包括农夫在内总共只有两个位置
农夫每次带着一个物品过河然后再返回来
他可以带物品返回也可以是空船返回
这个农夫他对这三个物品有一个制约的作用
也就是说如果农夫在的时候，这几个物品在一起是安全的，但是他不在的时候呢，狼和羊不能够单独共处，羊和菜也不能够单独共处
这样的一个问题，我们把它描述出来就是首先要对它进行一些限定，也就是说对这个问题的一些约束我们都要把它描述出来
我们怎么描述这个数据模型呢
我可以站在这个原始的岸边这样的一个角度来思考这个问题
那也就是说我要从这个起始的岸从一个人羊狼菜的一个状态变到最后是空的
也就是说包括农夫在内所有的东西都成功的搬到了对岸
这个搬运的过程里面，它两边的状态都会发生一些改变，那哪些状态是合理的哪些是不合理的呢
我们的人羊狼菜因为它有一个约束的条件也就是狼羊和羊菜它是肯定不能在一起的
那它的一个补集也就是说人菜还有人狼也是不能在一起的
另外人不在的时候狼羊菜它也是不能在一起的
这样的话呢我们就得到了六种不合理的状态
还有就是起始状态和终结状态，另外的这些组合呢都是合理的
总共得到了十种状态，然后这十种状态之间是怎么样发生关联的呢
那就是通过农夫来搬运东西或者是农夫划着空船，来或者去来发生关联的
因此我们每一次合理的渡河就可以使得这些状态之间发生相应的关联
例如人羊狼菜如果农夫先把羊给搬到对岸，剩下狼菜
在对面只有狼菜的情况下，然后人搬了羊过去了，接着他划着空船过来，起始岸的状态就变成了人狼菜，这也是合理的
我们所有的合理的迁移呢就把这些相应的节点之间给关联起来
这里我们颜色加重的这些线连起来就是我们这个问题的解
也就是说人羊狼菜是一个起始状态
然后人带着羊过去，它这边剩下了狼菜
然后人再划着空船回来，这个岸又变成了人狼菜
然后他再带着狼过去，把羊带回来，把狼留下，然后就变成了起始岸是人羊菜
接着把菜给运过去，羊留下，然后对岸又变成了人狼菜
然后接着他单独过来，把起始岸的羊给搬过去，最后就完成了这个搬运的工作
我们这个数据结构是可以采用一个相邻矩阵来描述
也就是把这所有的合理的节点当做我们这个矩阵的每一行的一个位置，也可以当做它每一列的位置
行列交错的这个位置就是表示这两个状态之间发生了一个关联
例如我们这里的排的这个编号顺序呢，这是第一个节点2 3 4 5 6
人羊狼菜呢它是第一个节点,跟狼菜这第六个节点,它是有一条边关联的
相应的就是在这个第一行里面的第六列是有一个数值1
如果是没有关联就是数值0
那我们就建立了这么一个数据结构
这个结构在我们计算机的内存里面是能够很好的表达的
然后对这个数据结构呢我们要来进行一个求解
这个求解的过程其实就是对这个图结构呢，我们求一个从起始状态到终结状态的一个可达路径
这么一个问题在我们计算机的数据结构里面很多情况下是求最优解，那也就是说最短路径
在图的那一章会有一个Dijkstra算法来求解最短路径。我们这里就不展开介绍了
通过这个例子，我们主要是给大家来看一下，遇到一个问题以后，我们怎么样来分析这个问题模型本身，建立一个合理的数据结构来描述这个问题的数据之间的关联关系
然后再寻找一个经典的算法或者是说我们重新设计一个适合这个问题的算法来求解这个问题，最后才是编码实现这么一个过程
大家可以思考一下对农夫过河的这个问题，我们是怎么样来对它进行问题抽象、数据抽象还有算法抽象这样的一个过程而且可以编码来实现
另外呢对于这么一个问题其实你用不同的观点从不同的角度来组织它是可以得到不同的数据模型
而且也就相应的需要不同的算法模型来对它求解的
大家也可以想想还有没有其他的方法
谢谢大家