微信号:grzlwx

介绍:光荣之路官方资讯

算法洗洗脑——第六篇 回溯思想

2015-07-20 22:41 光荣之路


记得广告中经常听到过,抱着试试看的态度买了3个疗程,效果不错........ 也经常听人说过什么车到山前必有路,船到桥头自然直。

哈哈,这种思想就是回溯思想,也可称为试探思想。

一: 思想

有时我们要得到问题的解,先从其中某一种情况进行试探,在试探过程中,一旦发现原来的选择是错误的,那么就退回一步重新选择,然后继续向前试探,反复这样的过程直到求出问题的解。

二:场景

回溯思想是一个非常重要的思想,应用场景也是非常广泛。

① “下棋”: 每一次走棋的位置都要考虑到是否是损人利己,如果是害人害己的走法就要回撤,找下一步损人利己的走法。

② “迷宫”: 这种问题用试探法来解决相信我也不用向大家介绍了,其实迷宫问题抽象起来就是“对图的遍历问题“,当然对图的遍历我先前的文章是有的,有兴趣的可以自己看一看。

三:举例

记得我写第一篇文章的时候有园友希望我能找些实际的项目案例,这不,今天就给大家带来了,首先就拿博客园的“网站分类”层级菜单

来说吧,首先上图:

针对这样的层级结构我们设计数据表一般都会设计成无限极分类,如下图:

那么问题来了,针对这样的数据,我们该如何在页面上呈现呢?

码农的做法就是点击一个父节点然后异步去数据库读取子节点,好一点的做法就会有人把数据放在xml里面,但是都逃避不了多次与服务器进行交互,带来比较大的性能问题。

我们这里要讲的当然是减轻服务器的压力,页面呈现的时候直接Load出所有数据,然后序列化为Json,就如上面的图中一样,我们用算法来解剖上面的json数据。

首先上面的json数据是由多个多叉树组成的森林,画图如下:

那么接下来如何遍历这个森林,数据结构中,森林是可以转化为二叉树的,然后采用”先序,中序 或者 后序”,当然对森林遍历也可以采用“深度优先,广度优先”。

好了,分析了这么多,其实也就是二步走:

第一: 将Json数据变成森林的数据结构模型。

第二:对森林进行遍历,这里就采用深度优先。

(作者:一线码农 来源:http://www.cnblogs.com/huangxincheng/archive/2012/02/08/2342111.html)

 
            
 
            
 
            
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           

一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499


 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 Android单元测试(七):Robolectric,在JVM上调用安卓的类 深度调查 iPhone 真的不拼硬件吗?A8 处理器解析 大宝推荐设计师阅读书单,历史上最值得你分享的推荐干货 emoji 表情和QQ/微信表情有什么区别? 让你变懒的 Android Studio Live Templates