驱车寻宝活动

来自计算思维百科
跳转至: 导航搜索
驱车寻宝活动1.jpg

欧洲的一个慈善委员会组织了一次寻宝活动,寻找一桶藏在Z村的啤酒。所有的车先在A村集合,然后寻宝者们分头去其他9个村子搜索。最后把这些线索集中在一起研究,才会知道那桶啤酒藏在Z村的什么地方。最先回来并宣布找到啤酒桶是约翰。他巧妙地安排了自己的路线,他从A村出发,经过其他9个村庄,最后到达Z村,途获得了所有线索,却没有重复走进任何一个村子,而其余的人则或多或少地走了弯路。

下面是11个村子的分布图,村子与村子之间只有唯一的一条道路。你知道约翰是怎么走的?

驱车寻宝活动2.png

解决方案

方案一:图的深度优先查找

深度优先查找从A村出发,把A村标记为已访问。在每次迭代的时候,该方法紧接着处理与当前村庄邻接的未访问的村庄。

第一步:从A村庄出发,根据字母顺序,走到B;(A,B已访问)

驱车寻宝活动3.png

第二步:从B出发,走到D;(A,B,D已访问)

驱车寻宝活动4.png

第三步:从D出发,访问M;(A,B,D,M已访问)

驱车寻宝活动5.png

第四步:从M出发,访问G;(A,B,D,M,G已访问)

驱车寻宝活动6.png

第五步:如果从G继续往下走,那就只能访问Z了,但是Z村庄是必须最后访问的,所以说明之前的路线有误,回到上一步;

驱车寻宝活动7.png

第六步:从D出发,重新找下一个村庄; ……

如此下去,我们可以找到最后的路线:

A→G→M→D→F→B→R→W→H→P→Z

驱车寻宝活动8.png

运用的计算思维

深度优先查找方法是一种减治法,每次查找到一个村庄,那么下次查找就少了一个村庄,然后再进行同样方法的查找,将大问题转变成了与之相似的小规模问题,运用了“转化”的计算思维,同时,在查找过程中将这个问题层层递进,体现了“递归”、“回溯”的计算思维。

方案二:决策树-广度优先搜索

驱车寻宝活动9.png

从A村庄出发,将下一个可能访问的村庄链接在A的下方,对每个村庄都用这个方法,最后找到一条路线是符合的。

运用的计算思维

决策树是一种帮助我们选择最好的线路的方法,在建立树的过程中可以将不可能情况所对应的枝裁剪,最后剩下的就是最终方案。在此过程中,我们将图抽象成了搜索树,也就是将问题转化成了树的搜索问题,运用了“抽象”和“转化”的计算思维。

参考文献

[1]闵于思.风靡世界500强的思维训练题[M].武汉:华中科技大学出版社,2012

[2]于雷.逻辑思维游戏500题=Logic[M].北京:中央编译出版社,2009