pascal中级教程第一章回溯法

1.10关路灯

源程序名 power.???（pas, c, cpp） 可执行文件名 power.exe 输入文件名 power.in 输出文件名 power.out 【问题描述】 某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。 【输入】

文件第一行是两个数字n(0

接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。 【输出】 一个数据，即最少的功耗(单位：J，1J＝1W·s)。 【样例】 power.in power.out 5 3 270 {此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序} 2 10 3 20 5 20 6 30 8 10

【算法分析】

设老张开始所在位置为c，以起始点c为分界点，算出左右两部分总的功率p_left和p_right，再来分别看向左与向右的情况。

向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_left+w[i])*t，增加的功为p_right*2t。

向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点(一盏路灯处)所要时间为t，减少的功为(p_righ+w[i])*t，增加的功为p_left*2t。

比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，但

不能求出所有情况下最佳的解。

对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变化都跟上面所述一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左与向右的情况，在所有可能的情况中找出最优解。 【思考与提高】

上面的程序运算的范围很有限，当n比较大时就会栈溢出，如n>30时速度就比较慢了。实际情况调头的次数并不会多的，到底在什么时候掉头根据情况而定。我们可以从最后一步来思考：

最后一次关的可能是第一个灯也可能是最后一个灯，哪种情况所费的功小就选哪种； 最后一次关的是第一个灯的话，说明最后的方向是从最后到最前(右边到左边)，最后倒数第二次的方向为从左到右，起点可能是原始起点(此时是第一趟)，也可能是原始起点左边的点(此时至少是第二趟)，一个个地试过去，先设拐一次弯，有可能拐的点都试过去，再试有两次拐弯换方向的情况，当再多的拐弯超过已有的解时就不要再向下试了。采用这种回溯方法，效率更高。

如果n再大一些，如到300以上，上述方法也有它的局限性，此时最好从动态规划法或贪心法的角度去思考。

1.5 走迷宫

源程序名 maze.???（pas, c, cpp） 可执行文件名 maze.exe 输入文件名 maze.in 输出文件名 maze.out 【问题描述】

有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可以走，文件读入这m*n个数据和起始点、结束点(起始点和结束点都是用两个数据来描述的，分别表示这个点的行号和列号)。现在要你编程找出所有可行的道路，要求所走的路中没有重复的点，走时只能是上下左右四个方向。如果一条路都不可行，则输出相应信息(用-l表示无路)。

【输入】

第一行是两个数m，n(1

【输出】 所有可行的路径，描述一个点时用(x，y)的形式，除开始点外，其他的都要用“一>”表示方向。 如果没有一条可行的路则输出-1。 【样例】 maze.in 5 6 1 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 5 6 maze.out

(1,2)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6) (1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

【算法分析】

用一个a数组来存放迷宫可走的情况，另外用一个数组b来存放哪些点走过了。每个点用两个数字来描述，一个表示行号，另一个表示列号。对于某一个点(x，y)，四个可能走的方向的点描述如下表：

4 1 x,y 3 2 对应的位置为：(x-1, y)，(x, y+1)，(x+1, y)，(x, y-1)。所以每个点都要试探四个方向，如果没有走过(数组b相应的点的值为0)且可以走(数组a相应点的值为1)同时不越界，就走过去，再看有没有到达终点，到了终点则输出所走的路，否则继续走下去。 这个查找过程用search来描述如下：

procedure search(x, y, b, p)；{x，y表示某一个点，b是已经过的点的情况，p是已走过的路} begin

for i:＝1 to 4 do{分别对4个点进行试探} begin

先记住当前点的位置，已走过的情况和走过的路； 如果第i个点(xl，y1)可以走，则走过去；

如果已达终点，则输出所走的路径并置有路可走的信息， 否则继续从新的点往下查找search(xl，y1，b1，p1)； end； end；

【思考与提高】 该程序通过引进新的变量和数组来继续新的查找，如果不引进新的变量和数组，那么每一次返回时要将原来的值还原才行，如果那样，程序应如何修改?其实那样更加符合回溯的思想——换条路再试。这类问题也可以归为搜索的问题，如果m和n的值相对比较大，则解可能很多，若题目只要找到一条路就结束程序时，在程序的输出部分后面加上一个halt就行了。

有些情况很明显是无解的，如从起点到终点的矩形中有一行或一列都是为0的，明显道路不通，对于这种情况要很快地“剪掉”多余分枝得出结论，这就是搜索里所说的“剪枝”。从起点开始往下的一层层的结点，看起来如同树枝一样，对于其中的“枯枝”——明显无用的节点可以先行“剪掉”，从而提高搜索速度。