注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

DJun的网络花园

2007-6-10, 下午, 博客诞生

 
 
 

日志

 
 
关于我

我很懒,什么都没有留下…… ----2007-6-10, 下午, 博客诞生... 名字“2xhx”为胡老师的“zxhx”的化用,为了纪念他和他的多媒体教学课件……

网易考拉推荐

我的马踏棋盘优化算法  

2011-07-03 14:14:02|  分类: 编程园地 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
根据网上的“贪心算法”改进而成,不知道算不算是原创的呢,百度谷歌到的资料好像没有我这种思路的,嘻嘻~
转载 使用 请注明 DJun,http://2xhx.blog.163.com

数据结构课程设计作业。首先因为数据结构题集里写的是要用非递归算法,因此要先写出一个完整的栈类型和相关操作,
接着定义一个用来存放棋盘各个格子的权值的二维数组,比如weight[8][8],权值的含义是 该格子上八个方向不可访问的方向数量,
栈元素类型 原包含 坐标类型变量、序号变量、方向序号变量,在栈元素类型中加入定义 一个一维数组,用来存放判断该格子八个方向上的权值排序后的序号顺序(“方向”已定义为一个坐标类型的常量数组),

在开始进行遍历之前,先初始化权值数组weight为0,用一个双重循环,每个格子判断八个方向是否可通过,不可通过则权值+1或-1,
在遍历过程中,每当踏入一个新格子,便获取八个方向上每个格子的权值排序并存入栈元素中的那个一维数组中(只需计算一次,因为遍历过程是回溯的),并修改八个方向上格子的权值+1或-1表示那些格子的可通过方向数量减少1,接着取权值最大(对应权值+1)或最小(对应权值-1)的方向踏入,回溯到此格子的时候按一维数组中存放的顺序选取下一个方向踏入,无可踏入的方向则再回溯,
这样便能很快得出第一个解(一定要按照这个顺序,原因请继续阅读下面的内容)。

如果要计算出全部的解,因为每个方向都需尝试一遍,所以上面的方法所花费的时间跟未优化过的直接回溯的方法是一样的。
再优化:观察到求出解时,二维数组weight的每一个元素值都为8或-8,且在遍历过程中,不会出现 未踏入的格子的权值>=8或<=-8的情况(某一格子符合“未踏入”且“权值>=8或<=-8”的条件,表明该格子是“死点”,在它的八个方向上没有格子可以借助以踏入该格子),如果出现这样的情况,后续的搜索是无必要的,因为不可能一次踏遍整个棋盘的每一格子。因此可在“修改八个方向上的格子的权值”的时候,加入判断是否有权值>=8或<=-8,如果有,则直接回溯。
此方法未经过验证,不过,与未再次优化的算法产生的部分结果利用“文件校验”进行验证比较,结果是一样的;效率上,由同时限产生的结果文件体积比较来看似乎的确是快了一点,也不可能马上得出结果,因为全部解实在是太多太多太多啦!
  评论这张
 
阅读(923)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017