pascal-算法例题 - 图文(7)

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

每个节点的这种数据就是通过估价函数来计算得到的。估价函数就是自己定义的，用来计算某个节点相对于目标节点来说的数值化概念。一般的，我们定义一个节点如果估价函数的值越大就说明这个节点越接近目标节点，也就具有最优先的被展开权。实际上，我们已经接触过这样的概念——在等代价搜索法中，我们不是每次展开所有未展开节点，而是展开那个代价最小（大）的节点，这里的代价就是估价函数的简化形式之一。 那么，估价函数到底应该个什么函数呢？我们知道，一个函数最重要的是自变量有哪些。同样，对于宽度优先搜索来说，那些节点到底有哪些因素表示与目标节点的接近呢？毫无疑问，层是一个重要因素，如果两个节点与目标节点的距离相同，但层数不同，则层数少的节点是占优的，这就如：在第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页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库pascal-算法例题 - 图文(7)在线全文阅读。