如果说学习过《计算导论与C语言基础》，你已经迈入了C语言的殿堂，那么《C程序设计进阶》将帮助你更上一层楼，理解“结构化程序设计的基本思想”，掌握“C程序设计的基本技巧”，养成“良好的编程习惯和编程风格”，编写出“真正具有生命力的计算机程序”。完成这门课的学习，你将能解释C程序设计语言的基本概念与知识，并且使用C语言编写计算机程序解决生活工作中的实际问题。
习题课二：搜索 [较难，选听]
Loading...
來自 Peking University 的課程
C程序设计进阶
607 個評分
從本節課中
指针（一）
本次课我们为大家讲解“指针”“指针变量”“指向变量的指针”等名词的基本含义。在此，需要特别提示大家：请大家务必明确区分上述的基本概念，以便在后面的课程中准确的使用它们。
同时，我们还将向大家阐述一个重要的理解——数组名 与 指向数组首元素的指针 之间的关系，也请大家务必反复印证，以便日后轻松使用：）
與講師見面
Ge Li 李戈, Ph.D.Associate Professor
School of Electronics Engineering and Computer Science
好的，接下来我给大家讲两道稍微难一点的题目，它也是用递归的题目。
但是这两道题目，我们管它，把它分类为搜索题。
所谓的搜索题是什么意思？就是它会在，也是跟枚举题一样，
也是有非常多的状态我们需要去把它排除掉，但搜索不同就是我们在， 并不是一下子把所有的可能性全部给列出来，而是在
不断的往前探索的过程中，不断的探查我们的可能性。
为什么我们要这么做，而不直接枚举呢？因为枚举的话，很多可能性其实是
可以直接被忽略掉了，或者说如果直接去枚举的话，这个状态数量太多了，我们是无法去
完全把它给枚举出来的。像这，拿题目来说事，
像这道搬皇后的题，搬皇后一道非常经典的题。
是一个什么意思呢？我们有一个八乘八的棋盘， 我们有一个
八乘八的棋盘，然后在西方的西洋棋里面，一个皇后 如果在这里的话，那么它可以攻击横的这一
列，横的这一行，然后纵的这一列，然后还有斜着这么一斜溜儿，
都是可以攻击到的。我们所要做的就是说尝试 往这个棋盘里面放 8
个皇后，它是个 8 乘 8 的一个棋盘， 尝试把这个棋盘给里面放
8 个皇后，比如说像是这个样子， 然后呢使得每一个皇后跟另一个皇后之间都不会
它的就是不会被另一个皇后攻击到，不会有两个皇后像这个样子，
在一行内是不可以的，然后在一个纵列像这个样子也是不可以的，这样斜着的 也是不可以的，总之我们要往
8 乘 8 的棋盘里面放 8 个皇后， 使它正好可以和谐相处。我们先考虑一下，人应该怎么去解决这个问题？
人解决问题的方法，如果是不是特别聪明 的人，就是比较笨的人，我们模拟比较笨的人解决它的方法，是怎么样的呢？
首先在可以放的地方先尝试放一个， 然后呢第一个放完之后，在第二列然后看第一行不行，第二行不行，第三行，可以，放一个。
在第三行，看一行不行，二行不行，三行不行，四行不行，五行好像可以，放一个，然后如此- 类推然后一直放到最后。
然后或者说，放到某一步，比如说在这一步放完之后，在下一行应该是
我看还能不能放，这儿还可以放一个，然后再下一行
这里可以放吗？这里也可以放，这里可以放吗？可以放。
然后再下一行，在这里可以放一个，然后最后在这里放一个。
这是一个八皇后的解法，然后已经模拟出来了。但如果第二个
比如说第二个它不是放在这儿，我第二个往下放一个了，然后在
从第三行枚举，可能枚举到某一个地方，比如说在这一行的时候，
我们就发现我们已经每个位置都不能再放皇后了。
那样的话，说明之前的这种放法它是失败的，我们之前不能这么放。
这是一个比较傻的人，他就会这么做。如果聪明的人的话可能会
想到比较好的方法，但我不是个聪明人，所以就不说了。程序怎么去解决这个问题呢？ 我们从第一行开始试，试完第一行，试第二行，
就是再试第三行，一直试下去，如果试到最后，那么我就把这个问题解决了。
如果我们有一个函数 f ，我们递归地去考虑这个 f ， 它输入是一个
n ，代表，我在这里再加一行， fn ，它 fn
输入第 几行它就可以解决从
n 到 7
排布 皇后的问题，返回
可能性的数量。
如果我们有这么一个函数， fn 可以解决 n 到 7
排布皇后的一个问题，那么我们这整个问题 从 0 到 7 ，实际上就是我们需要一个
f0 这样一个数， 这么一个数它是怎么算的呢？
我们是会尝试从 0 先放一个，在这个
0,0 的位置放一个皇后， 然后呢在 0,0
位置放完皇后之后，我们在这个地方放了皇后的前提下， 放 1 到 7
，也就是说这个它等于 在 0,0
放皇后 的情况下，f1
的情况，f1 的返回值，它可能性，
对不对，然后再加上，因为我们要试多种情况， 在
0,1 放皇后
的 f1 再加上
一直加，一直加到 在 0,7
放皇后， 这是 0,7 呗，放皇后，
之后再加上 f1 ，是这样一个步骤。
然后我们首先要注意到一个，我们会枚举出一个 从
0,0 一直放到 0,7 ，这儿是个什么东西呢？这是在搜索问题，
搜索问题的第一步， 枚举可能的
动作，像在这里的话，我们可能的动作就是说在第一个地方放一个皇后，
第二个地方放一个皇后，因为我们一列里面是不能放两个皇后的，所以 我们的动作非常简单，就只能在里面放一个，而且我们必须放一个。
为什么呢？因为我们不可能把 8 个皇后放到 7 乘 8
的一个格子里，这是不可能的，所以我们必须 要利用第一行，第一列，也就是说我们放并且只能放一个皇后。
也就是可能动作在这里面我们就只有八种可能性，第二步 尝试这个动作，
这是什么意思呢？就是在这里面，我们在 0,0
放皇后这个动作就是我们的尝试， 放完这个皇后之后我们就算 f1
， 算完 f1 ，我们再把皇后放到 0,1 处再算 f1 ，然后再放到
0,7 处， 一直放到 0,7 处，然后再算 f1
，把它们的结果全部加起来， 假如这个放皇后的动作就是尝试这个动作，
尝试完之后第三步，就像刚才说的， 计算
递归，递归计算，递归计算 更简单的情况。
第四步，计算完更简单情况之后怎么办呢？ 像
f0 我们是这么考虑的，那么我们 f ，比如说 f1 ， f1
是怎么着呢？f1 的话我就直接说了，比如我们在 1,0 处放皇后，
然后首先看它可不可行，对不对，因为我们在 0 的话是从 0
到 7 都是 可行的，但是如果我们在 0,0 处放了皇后，那么在 1,0 处再放皇后这就是不可行的情况了。
所以说我们在枚举可能的动作的时候，我们需要加一个 判断，具体在程序实现上，我们就是实际上就是一个循环，还是从
0 到 7 的一个循环，我们去探查这里面， 先看这个动作是不是可能的，这个动作如果前面有个皇后了，那它就不可能的，我们直接跳过，
到下一个动作上，下一个动作也是不可能的，我们再跳过，跳到下一个，这个是可行的，可行- 的之后我们像刚才一样，
去尝试这个动作，然后再递归计算后面的 2 到 7 ，如果 2
到 7 的 可能性全部给算出来之后，那么
如果我们第一个放 0,0 ，第二个放 1,0 ，在这个情况下
皇后的摆放的方式的可能性的种数我们就可以知道。
然后我们把这一列所有的可行的可能性全部给加起来， 然后也就是说在这里，于是它就是这样一个
计算，也就是说首先枚举可能的动作，尝试这个动作，计算更简单的情况。
更简单的情况返回之后怎么办呢？如果我们在 0,0 的地方放了皇后了，如果我们再在 0,1 的地方再
放一个皇后，那么这后面的枚举它就不对了，是不是？虽然在这种情况下是对的，如果再放一- 个的话那肯定就不对了。
如果我们在 0,3 处放皇后，那我们需要把前面的之前放的皇后，或者说上一步放的皇后
给撤销掉，我们不能让之前的尝试影响我们之后的搜索。
我们是把之前的拿起来再放下去，所以第四步是
撤销这个动作，注意这个动作 这里的第二步和这个第四步这两个动作是一致的，是一个动作。
然后这就是搜索问题的一个基本的框架，
我们先枚举，枚举完尝试，尝试了计算，计算完了，所谓的递归计算，换句话说就是搜索，
搜索更简单的情况，然后再撤销这个动作，然后最后返回 返回值。
返回值的话就是根据题目来说，像这道题来说就是FN就是解决从 N
到 7， 一共有多少种排布方式，就返回多少个。
好现在我们有这么一个类似于转移方程的一个方程了。
严格来说并不能说算转移方程因为搜索问题它 由于有枚举可能性这个动作所以转移方程并不是很好写。
但我们再处理一下最简单的
情况，也就说我们它搜索到什么情况下我们应该终止呢？ 我们不可能一直搜索下去。我们在搜索F7的时候
就可以决定，F7的时候可能还不太好决定， 但是在搜索F8的时候，也就说我们在搜索最后这一行的时候
就可以决定。它是多少？它是1，这是什么意思呢？我们搜索到F8的时候 意味着前面从0到7这前面这8列
已经全部都放好皇后了，也就说我们正好放了8个皇后，之前放的这 8 个皇后它就是正好是，
算是一种可能性。如果我们搜索到F8了，那么就说明之前已经成功放完了。
对不对？但如果我们 比较正常的去考虑问题我们在F7这去终止，那么F7就是
还是对于每种可能性，
比如说如果从F0到F1的话就像我们刚才第一次那样放的话，
到F7这里的时候我们在枚举的时候枚举完了其实只剩一种情况了。
就是在这里。其实像这道题来说我们完全不用枚举到F8，我们直接在F7的时候直接返回1- 就可以了。
但实际上呢我们为了这个整个搜索问题的算法的 完整性，我们还是写一下。就是说
在 7,7 放皇后，
然后我们再算一下F8，或者说直接在这返回1，
都是可以的。
但如果你在这写了F8的话，就是说在7这里并不终止，你就需要单独处理一下F8，
在F8的地方返回1。最后我们直接调用F0，
就可以知道这个 在8 乘
8的棋盘里面放8个皇后一共有多少种解决办法了。
这就是一道搜索的题目。我们只要记住搜索这个框架，
第一步枚举所有可能性，对于每一个可能性尝试这个动作递归搜索下一步，然后撤销这个动作，
然后最后返回这个返回值。然后其实在这之前还有一个，就是在枚举 之前就是判断，就像所有的递归函数一样，第一步永远是判断
是否达到最简 最简单，最简情况。
就如果是的话那么可以直接返回 我们知道的值，如果不是的话那我们继续搜索。
所有递归函数都是这个样子。
接下来我再说一道递归搜索，另一道递归搜索题叫棋盘跳马。
中国象棋棋盘就是， 比如说我们做一个6 乘
6的一个棋盘，在这里，如果我们规定左下角是S， 然后右上角是E，代表我们有一匹马，棋盘上的马，
马是走日字，就是要么是上两格右一格，或者说往一个方向两格， 然后再往垂直的方向一格这么去移动的一匹马。
这匹马从S走到E，它最短需要跳多少步？
当然这个问题的话其实我们完全可以不用递归去解决问题。而且实际上
我也不建议大家递归真的拿递归去解决这种问题。它确实是可以直接拿数学上
拿公示去算出来的。S我们往右跳一步，再往右跳一步，然后到这里，差一个
目字，目字的话我们往这里左边横的来一步，然后就到了。
那就是1、2、3、4，一共四步正好跳到1。然后我们需要解决的 其实并不是这个问题。因为这个问题比较简单。
我们需要解决的是什么问题呢？我们这个棋盘上它不仅是，它不是一个空棋盘，它上面会有一- 些石头。
我们就叫做，用圈来标出来吧。比如这有三块石头，
然后马碰见这个石头的时候，首先马不能踩到石头上。第二如果马在这里的话，
马在这里的话它不能往上跳因为它会蹩足。
马前面有块石头的话它就不能往这个方向前进两步。
它只能往别的方向前进两步然后再垂直上下移动一个，以那种方式去移动。
就像中国象棋棋盘一样。马，
马碰到一个东西会憋足的，但这里我们不用别的子，我们用一些 石头来代替，一些障碍物。我们怎么去解决这个问题呢？
首先我们要明确一点它是个搜索问题。
为什么它是个搜索问题？我们刚开始有比如说S，现在是在左下角我们只有一个可能性，
但是呢如果我们到中间的某一个地方的时候，比如到这里了，它确实是有多个可能性的。
当然有些可能性还是由于条件的限制就是棋盘的限制它是不能去做的。
啊我们把刚才的这个搜索问题的框架拿上来。首先我们
到了某一步，枚举这个到这一步所有的可能性对于每一个可行的动作
判断它可不可行，就是首先马不能踩石头，第二马不能憋足，
对于每一个可行的可能性，首先尝试这个步骤，跳过去，
跳过去之后我们如果有一个函数F，它可以解决
我们输入一个X，输入一个Y，它可以解决从XY到一点 最少需要多少步。那么我们就知道了
对于在S点的所有可能性。
对于它的所有的可能动作我们去挑一个最小的动作，比如说是
比如跳到Z，Z点。那么我们输入就是XZ和YZ，
然后这个Z点可能有很多，就像刚才说的如果它在中间的话Z点可能比如说
如果初始点在这里，然后在这个完美的情况下，它一共有8种可能性。
但是如果憋足了的话，像是在 比如说在这里，那么它就会少两种可能性，一共6种可能性。
错了，5种可能性，这还有一个地方有石头，马不能跳上去。
像这样一道搜索的问题。这样的话我们这个问题想的基本明白了。
然后我们试一下这个问题跟刚才那个问题到底哪有区别呢？为什么我要单独把这个问题拿- 来说呢？
我们试一下，实现一下这个函数，输入一个X，输入一个Y。
然后呢我们比如说有一个LIST，这个LIST是我们是GET，
GET LEGAL MOVES这个函数就是会返回在 X,Y 这个点它
可以走的所有的动作。然后对于每个动作， FOR
EACH MOVE IN LIST，我这种写法
叫做伪代码，就是说它并不是真正可执行的代码，它只是为了表达意思而写的。
对于这个LIST里面的每一个动作我们去尝试做
做动作，MOVE，
然后再进行下一步的搜索。下一步的搜索是
MOVE 之后
的坐标。
然后最后再撤销动作。
MOVE 然后最后返回，返回是什么呢？
返回是我们要找的是它最快能有多少步到达这个E点结束点，
那么也就是说如果它返回的步数是，我们要在步数里面挑最小的，也就是说返回
在这里我们用一个R来记录它的返回值， 那么就是要找到最小的这个R，或者我们直接写在这里吧。
这个R就是在不断的去比较最小。
刚开始的话，R初值肯定要赋一个比较大的值，比如说 INT的最大值之类的，就是我们能够确保
不可能有比它更差的情况。当我们把函数这样去写完之后， 我们真正去执行它，我们就会发现有个问题就是这个函数好像死掉了，它就永远不动了。
为什么呢？其实我们可以想象。在这个搜索问题中，虽然非常完美的去遵循了这个搜索问题的- 四个步骤，
但是呢它有一个情况没有去考虑。就是我们刚开始马在这里，我们往回跳了，跳在这了。
比如说跳在Z了。然后呢我们在探索这个点的时候又跳回去了。
然后探索这个点的时候又跳回来了，然后又跳回去了。这样的话
它就永远的在这不断的跳来跳去，这个程序就永远结束不了，它就永远也到不了E，
这时候怎么办呢？其实办法有很多。首先我们第一个可以记录一下这个马是不是真的是
经过了这个点，如果说在 探索的过程中，比如说S这个点，在探索周围这5个
可能性的时候，如果有一个可能性在之前的探索过程中已经探索过了， 比如说，有一个它的探索轨迹是这样的，首先第一步跳这了，
第二步再跳这里，第三步没有地方跳了，然后它 返回，返回一个无穷大。然后，比如第二步跳到这里，然后第三步，
跳到这里，然后第四步，然后它又想往回跳的时候，发现这里已经之前跳过了。
然后呢，它又想往这跳，发现这它又是跳过了。我们刚开始这个s就是，
也跳过了，那么呢它只好往这里跳或者往这里跳。
像这，这样我们用一个列表一样的东西去记录，记录它之前所跳过的所有的步骤，
就是一个可行的解决方案。我们
把刚才我们说的这种解决方案实现一下，那么我们就会有一个，
全局的list，叫做TriedPositions。
我们有一个全局的一个尝试过的坐标的一个
列表。排在这个列表里面，每次做动作的时候，我们会把这个动作，
把它可以加进去。
Add move to
TriedPositions，,然后在撤销之后再Remove， move from TriedPositions。
这样的话，有这么一个列表用来记录我们这个整个探索的过程，探索的
之前走过的步数，走过哪些步。这样的话我们就可以 避免在两个点之间来回跳来回跳，以致于我们
程序无法结束。最后我们还差最后一点，就是判断是否达到最简情况。
在这道题里面，最简情况就是说，如果， x,y ==
Xe,Ye， 那么我们直接可以return 0。
那这程序中还有一点小问题，我把这个1+上给加上了。因为我们
每做一步，这个返回的值就应该加1，因为我们每做，多尝试了一步然后就会有一个 加1的返回值。这样的话就会不断尝试，直到尝试到
它正好到达这个结束点，这样的话我们就可以直接返回一个0，代表它正好到了。
这种情况就是，比如说一开始这个s就在这个E点了，那么它肯定就返回一个0，我们需要只- 用0步我就可以到达这个结束的点。
如果我们把程序这么去写的话，你会发现，它虽然可以把结果给算出来，但是它不够高效。
为什么它不够高效呢？啊，很明显的一点原因，可能也 不是特别明显吧。但是如果你仔细想一下这个过程，你就会发现，
如果我s在这个地方，它探索了这，然后它探索了这，
然后它找到E点了，假设它是这么找到了。然后它说嗯，很好，我在跳一步、两步、三步，我- 就正好可以到达这个位置了。
然后在，然后在这个地方的时候，我们计算过， 在这个点是0、1、2、3、4，（4，2）点，
在（4，2）这个点，我们计算过，它只要一步就可以到达了。并且在这个点我们也计算过，
是（2，2）点，错了（2，1）点。（2，1）点我们也 两步就可以到达了。然后s这个点，三步就可以到达了。如果这些都计算过的话，
如果我们还有更近的一条路，嗯， 我觉得这道在这个情况下，应该是三步是最少的。
如果还有两步的情况，那么它可能先跳到某个地方，比如说跳到这里，
下一次，然后程序在 尝试这里的时候，然后又跳回到这里。再跳回到这里的时候，
它实际上就不需要再从这个点再继续往周围搜索了，因为它之前已经搜索过了，
再从这个点到E点最短需要多少步了。这个最短的步数，是不会因为你之前走过
什么路程而去改变的，这个是一个长期的一个过程。只要你 走过这个地方，你算过这个点，那这个点的到
目标点所需要的最少的步数是不会变的。也就是说，我们在这里探索的时候，探索这个点，
这个4，（4，2）点的时候，我们可以，因为它之前直接探索过的 结果是1。那么直接在这里就可以返回1加1等于2。
然后之后再返回。再比如说，我们后来搜索到这个点了。
这个点的时候，如果再往后探索，往后探索这个地方。这个地方由于我们之前也是算过的，
它是到最近的步数是两步，
两步就可以到达这个最后的结束点。那么它也不用再继续从这个点重新搜一遍了，它直接
在这里是2加1等于3就可以啦。像是这样的解决 问题的方法，我们可以认为是它记录了之前计算的结果。
是一种有记忆的搜索。而这种记忆本身就是我们搜索的优化。
我们把它可以加到这个程序里。这个程序是什么意思呢？ 就是说，我们还有一个列表，
或者列，叫列表都不合适了，就是还有一个，比如说数组。
一个history，history数组，它输入一个x坐标，输入一个y坐标，
比如说什么［100，100］之类的。这个棋盘可能没有那么大。
我们全部把它初始化为－1。那么我们在这里计算的时候，我们就可以说，如果
我们之前算过了，x，y点，那么我们直接返回
这个，这个点就可以了。如果没算过，那么我们再算接下来的情况。
在接下来的情况里面，我们就可以在return R之前，
记录一下我们，我们算过的这个点，把x和y
等于R写上。如果我们这样去用一个新的一个数组去保存之前计算的结果，
那么我们这个搜索效率会大大的提升。
虽然我们只加了三，啊四行，但是这个搜索效率会提升非常多。
最后，我们把这个搜索加进去。
这种搜索叫做无状态的搜索，也就是说我们之前搜索的过程并不会影响棋盘的状态。
这种搜索我们就可以加上我们的历史记录。
我们判断最简情况可以放在这之前，判断是否
算过。还是放，为了跟底下程序一致还是写前面，其实都无所谓啊，算过当前状态，
如果算过，直接返回，
然后如果没有算过，那我们接下来继续，如果没有算过，
那我们接下来做接下来的事，判断 是否达到最简情况，枚举可能性，然后剩下最后返回返回值，返回，
返回值之前加一句，记录 这次运算的结果。
然后在刚才这一点的时候，我们还用了一个，用了一个 列表，来保存我们之前走过的那些步数。
然后防止它在两个地方来回跳。
那这个其实是跟具体的问题有关的，它并不是一个， 跟这个搜索算法本身，它并不是
搜索算法本身强制要求有的一个步骤，所以我就不写上去了。
但是像这样一个搜索问题的话，尤其是在下棋这种搜索问题的时候，你绝对是
要考虑一下，你这个棋子儿有没有可能说又跳回到之前这个， 我们上一步想算的情况。
刚才的搬皇后之所以没有这个问题，是因为我们有一个明确的一个方向，就从左往右放皇后。
但在这里的话我们没有一个明确的方向，我们就需要一个列表来记录一下之前算过的东西了。
