[2407] Depth and Breadth

Title Text:A death-first search is when you lose your keys and travel to the depths of hell to find them, and then if they’re not there you start checking your coat pockets.

Origin:https://xkcd.com/2407/

https://www.explainxkcd.com/wiki/index.php/2407:_Depth_and_Breadth

深度与广度

死亡优先搜索指的是你丢了钥匙的时候,先跑到地狱最深处去找,要是钥匙不在那儿,你再摸摸大衣口袋。

http://xkcd.in/comic?lg=cn&id=2407

树结构是计算机科学中最常用的数据结构之一。枚举排列在树中的项目的常见方法是深度优先宽度优先,这在漫画中已准确描述。Randall幽默地组合了这些单词,以产生“先行先行”,“先行先死”,“先行先行”和“先行先死”搜索算法。

深度优先搜索先探查树的整个分支,然后再返回更高的层次。在761:DFS中已经讨论了这种类型的树结构不能满足人类的需求。与之相反的是广度优先搜索,它一次浏览树的每个级别。

在“深度优先”算法中,深度优先搜索和广度优先搜索混合在一起,其中最左边的节点比右边的节点更频繁地被访问,但是右边的节点仍然被访问。这对于探索松散但未严格加权到左侧的数据或在较深的节点中的数据需要花费一些时间才能使用之前加载的数据可能是好的。就像761:DFS所暗示的那样,这可能是人类采用的最佳算法,在该算法中,人们可以短暂地探索几个主题,然后再决定要深入研究哪个主题,而不是盲目地跟随第一个兔子洞得出荒谬的结论。明智的搜索算法,例如A *搜索Beam搜索和其他Best-first搜索算法通过扩展当前集中最有希望的节点(在某些适当的指标下)来显示这种行为。

“死先”算法的性质尚不清楚且效率低下,因为它在移动到树的完全不同区域之前会多次搜索相同的节点。在检查节点很有可能返回嘈杂或错误结果的情况下(例如搜索可能被忽略的小对象),这可能很有用。

面包优先搜索从字面上进行。首先搜索面包。由于计算机用户现在已经满足了他们寻找面包的需求,因此计算机根本没有理由探索这棵树。[需要引用]

标题文本引入了“先死先死”搜索,在此搜索中,用户在考虑其他任何问题之前先探究死亡的感觉。具体来说,标题文字是指地狱,它让人想起但丁·阿利吉耶里(Dante Alighieri)在他的地狱中的冒险经历,而且比人的大衣口袋[钥匙需要]遗留钥匙的可能性更低。2021年(该漫画出版的那年)有纪念但丁逝世700周年的纪念活动。预计这些活动只会在人们中间发生,而不会在地狱中发生。[需要引用] 一种更令人愉快的“死亡优先”算法可能是跳过地狱和炼狱并首先搜索天堂,也许是多次(这本身就是“致命优先”方法的使用)。

Leave a Reply

Your email address will not be published. Required fields are marked *

Categories