pascal-算法例题 - 图文

中山纪念中学信息学奥林匹克算法设计题选

i:=l;

n:=findobject; until (n>0) or (i=j);

if n>0 then begin {打印结果} repeat

writeln(water[n].w[1]:3,water[n].w[2]:3,water[n].w[3]:3,' <-- '); n:=water[n].father; until n=1;

writeln(water[n].w[1]:3,water[n].w[2]:3,water[n].w[3]:3); end else writeln('No Answer!'); end.

2、八数码问题：如下图左在3X3的方格棋盘中放有1—8八个数字，中间是空的；目标状态如图右，每次移动只能把一个在空格同一行或同一列的数字移到空格中。求最少移动次数的方案把初始状态移成目标状态。初始状态由键盘输入。 2 8 3 1 2 3 1 4 8 4 7 6 5 7 6 5 分析：

（1）要以最少步数获得结果，毫无疑问应采用宽度优先搜索。

（2）第一层只有一个节点，就是初始状态，由此状态可展开所有第二层节点。

（3）展开下一层节点的过程就是每个数字移动后产生的新状态。因此，8个数字中任一个数字都有四种移动方向：上、下、左、右。这样，展开下一层共有32种情况进行判断（中间有许多移动是不能进行的）。实际上，此题的移动可变通地用空格来表示，每次移动都看成是空格移动，这样，每次空格只有四个移动方式，每次展开下一层最多只能产生四个节点。

（4）如果产生的新节点与已产生的节点重复，则应舍去不要。 （5）如果产生的新节点中有目标状态，则结果已经搜索到。

3、在下列所示的10个格子中，前两个是空的，后8个中放置了4个A和4个B，现在每次只能移动相邻的两个字母到空格中，要求移成4个A在一起，4个B在一起。 A B A B A B A B 分析：这是典型的宽度优先搜索问题，请大家自己编写程序解决。

十三、等代价搜索法

1、假设A、B、C、D、E各个城市之间旅费如下表所列（第一列为起点，第一行为终点，注意：两个城市之间来回的旅费是不同的）。某人想从一个城市出发游览各城市一遍，再回到出发地，而所用费用最少。试编程序输出结果。 A B C D E A 0 7 3 10 15 B 6 0 5 13 12 C 4 8 0 5 10 D 9 11 6 0 11 E 17 14 9 8 0 分析： 第 29 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选

（1）因为是要游览所有城市一遍，因而以任何一个城市为起点效果都是相同的，我们不妨就以A为起点。以A为起点也就是说根节点就是A，并且当前未展开的节点只有一个A。 （2）把A展开可得4个新节点，分别是：AB，AC，AD，AE。此时把A节点标志为已经展开，而未展开的节点有AB、AC、AD、AE四个（第二层）。如果此时把这4个节点也全部展开，则这种算法就是宽度优先搜索！等代价搜索法的特殊这处在于，此时应从未展开的所有节点中找出一个代价最小（旅费最少）的节点，然后把它展开，得到一些新的节点。这样每次从未展开的节点中找旅费最少的节点展开，直到得到目标节点为止。 （3）展开节点时要注意的是，不能出现重复到某个城市的情况。 （4）目标节点是怎样判断得到的呢？每个节点的状态我们可以就用字符串来存放，例如：ADEC表示之节点是从A到D再到E最后到C。这样，如果某个节点的字符个数为6的话，这就是目标节点。 此题如果不规定要回到起点呢？请编程序解决这个问题。 2、有一批军用物资由A1哨所运往A2、A3、A4、A5、A6、A7各哨所，各哨所之间的运费如下图。试编一程序计算从A1出发，去到各个哨所一遍应怎么走？最少运费是多少？ A2 11 A5 12 16 15 13 A1 18 A3 11 A6 11 17 12 14 A4 19 A7 分析：与上题相似，此题因为规定了起点，所以从此点开始用等代价搜索法即可。

3、挖地雷：在一个地图上有N个地窖（N<=20），每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路线。

例如： V4 V5 V1 V2 V3 V6 V1，V2，V3??表示地窖

题目要求：当地窖及其连线的数据给出之后，某人可以从任一处开始挖地雷，然后可以沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式：N 表示地窖个数 W1 W2 W3??WN 表示每个地窖中地雷的个数 A12 ?? A1N A23? A2N A N-1 N 表示地窖之间连接路径，AIJ表示I到J之间有否路相通，通时AIJ=1，不通时AIJ=0。

输出格式：K1-K2-??KV 挖地雷时地窖的的顺序 MAX 所挖地雷的数量

分析：采用等代价搜索，此题没有明显的起点与终点，可把所有点轮流作为起点，以此点为起点找出挖地雷数最多的一条路径，最后在所有的地雷数最多的路径中找出最多的。 请大家思考：等代价搜索法与动态规划法是不是同一种算法呢？我们在两种算法中所举的几个例子是不是同一类呢？动态规划中的图与等代价搜索法中的图有什么区别吗？ 答案是很明显的：动态规划的图中我们能够很容易地分清路径的段，即可固定地认为整个过程是经过哪些段，每个段中有很多节点，我们只需通过其中的一个节点！而等代价搜索则不然，整个图是网状的，无法分清段。而且题目的要求也不同，是要求走遍每一个节点！只不过是要最小代价的那一种方案！

十四、A*算法

A*算法的实质也是宽度优先搜索，只不过在宽度优先搜索的基础上增加条件控制，并不是每次把一层的所有节点都展开，而是根据某个特定的条件（估价函数）把某些或某个节点打开，以尽快找到目标节点。 对于未展开的所有节点，到底哪一个节点是值得先展开呢？我们不妨把每一个节点都增加一个数值化的数据，通过这个数据的大小来判断这个节点是否最接近目标节点，以便找到应该最优先展开的节点。

第 30 页 共 31页

中山纪念中学信息学奥林匹克算法设计题选

每个节点的这种数据就是通过估价函数来计算得到的。估价函数就是自己定义的，用来计算某个节点相对于目标节点来说的数值化概念。一般的，我们定义一个节点如果估价函数的值越大就说明这个节点越接近目标节点，也就具有最优先的被展开权。实际上，我们已经接触过这样的概念——在等代价搜索法中，我们不是每次展开所有未展开节点，而是展开那个代价最小（大）的节点，这里的代价就是估价函数的简化形式之一。 那么，估价函数到底应该个什么函数呢？我们知道，一个函数最重要的是自变量有哪些。同样，对于宽度优先搜索来说，那些节点到底有哪些因素表示与目标节点的接近呢？毫无疑问，层是一个重要因素，如果两个节点与目标节点的距离相同，但层数不同，则层数少的节点是占优的，这就如：在第3层和第6层都能一步到达目标点了，你会选哪个点呢？ 另外，一个节点与目标节点相比，怎样才是接近呢？这是一个具体的问题，应该根据具体题目来确定这一点。 假定估价函数为g(x)，层函数为c(x)，与目标节点距离函数为m(x)，我们可以得到这样一个等式：g(x)=c(x)+K*m(x) （K为某一常数）。当然，估价函数也可考虑为：层数与所花代价为自变量。 下面我们以具体题目进行分析： 1、有一个NXN的迷宫，每一格或者是空，或者是实，如果有一人位于迷宫（x,y）格中，则他仅能到达相邻的空格（即上、下、左、右）。

现有一人从（1，1）出发，目标是（N，N），他随身带有K（o<=K<=N）个炸弹，一个炸弹的威力能把与他相邻的一个实格炸成空格。

编一程序，求出R个被炸的实格点（格）位置（0<=R<=K）和此人从起始点到目标点的路径，并要求R是满足条件中的最小值。 输入格式： （1）键盘输入N，K； （2）键盘输入如下NXN的迷宫，如下图（N=5时，1表示实点，0表示空点）： 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 1 0 0 1 0 左上角座标为（1，1），右下角为（N，N），因此，（1，1）必须为空点。

输出格式（用“-”号表示路径，用“*”号表示被炸的点），如下是一种路径： - - - - 1 0 1 1 - 0 0 1 - - 1 0 1 - 1 1 1 0 - * 0 分析：该题初看似乎无从下手，其实可这样考虑： （1）从任一位置走到另一位置，如果走向空位，可认为所花代价为1；如果走向实位，则要花掉一个炸弹，可认为所花代价为1*100。这样，估价函数就是：g(x)=从起点起已用炸弹数*100+从起点起已走空位数。每次从未展开的节点中找到代价最小的节点再展开即可，当找到目标节点时，搜索结束。 （2）这个过程可简单描述如下：从（1，1）开始，可往下、右展开两个节点，此两个节点代价相等，任取一个展开，又可得到两个新节点（注意不要走回头路），加上原来一个未展开的节点共3个，找到其中代价最小的继续展开，??，这样，当目标节点（N，N）出现时，结束搜索，并打印答案。 （3）由上可知，每个节点不仅要存放自己的座标，还要存放其父节点的位置，以及代价。 2、讨论以下积木游戏：B B B W W W E 。表示黑子（B）三个，白子（W）三个，空格一个（E），走法如下： （1）一个棋子移入相邻的空格代价是1； （2）一个棋子最多跳过两个其他棋子进入空格，其代价等于跳过棋子的数目。 目标上所有白棋移到黑棋左边，并且代价最小。 分析：毫无疑问，估价函数应该与代价及当前状态与目标状态距离有关。而当前状态与目标状态距离可认为是：所有B的右边的W总数和。例如状态：BWWBWEB，三个B的右边的W分别有3、1、0个，和为4。 这样，我们把估价函数定义为g(x)=已花代价+当前状态与目标状态距离，g(x)越小则应该越先展开。 3、请利用A*算法解决8数码问题。

第 31 页 共 31页