常用算法设计方法5

发布时间：2006-07-25 12:02 点击：

分页:上一页 1 [2] 3 4 5 6 7 8 9 10 下一页 后10页

i+2，

j-1），实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序的同意处理，可以引入两个数组，分别存储各种可能走法对当前位置的纵横增量。

对于本题，一般可以采用回溯法，这里采用

Warnsdoff策略求解，这也是一种贪婪法，其选择下一出口的贪婪标准是在那些允许走的位置中，选择出口最少的那个位置。如马的当前位置（

i，

j）只有三个出口，他们是位置（

i+2，

j+1）、（

i-2，

j+1）和（

i-1，

j-2），如分别走到这些位置，这三个位置又分别会有不同的出口，假定这三个位置的出口个数分别为

4、

2、

3，则程序就选择让马走向（

i-2，

j+1）位置。

由于程序采用的是一种贪婪法，整个找解过程是一直向前，没有回溯，所以能非常快地找到解。但是，对于某些开始位置，实际上有解，而该算法不能找到解。对于找不到解的情况，程序只要改变

8种可能出口的选择顺序，就能找到解。改变出口选择顺序，就是改变有相同出口时的选择标准。以下程序考虑到这种情况，引入变量

分页:上一页 1 [2] 3 4 5 6 7 8 9 10 下一页 后10页

版权申明:未经书面授权请勿转载本站信息!!作品版权归所属媒体与作者所有!!

发表评论：

匿名发表

用户名:

查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任
留言板管理人员有权保留或删除其管辖留言中的任意内容
本站提醒：不要进行人身攻击。谢谢配合。